322021-01-08 19:58:18mraronHáromszögekcpp11Elfogadva 40/4068ms24520 KiB
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	vector<int> a(n);
	for(int i=0;i<n;++i) cin>>a[i];
	sort(a.begin(), a.end());
	a.push_back({(int)2e9});
	int blksz=500;
	for(int i=0;i<q;++i) {
		int b,c;
		cin>>b>>c;
		int mn=abs(b-c), mx=b+c;
		int L=0, R=n;
		
		while(L<=n && a[L]<=mn) L+=blksz;
		if(L>n || a[L]>mn) {
			if(L>n || (L>=blksz && a[L]>mn)) L-=blksz;
			while(L<=n && a[L]<=mn) L++;
		}
		while(R>=0 && a[R]>=mx) R-=blksz;
		if(R<0 || a[R]<mx) {
			if(R<0 || (R<n && a[R]<mx)) R+=blksz;
			while(R>=0 && a[R]>=mx) R--;
		}
		//~ cerr<<L<<" "<<R<<"\n";
		cout<<max(0,R-L+1)<<"\n";
	}	
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/02ms1756 KiB
2Elfogadva0/01ms1780 KiB
3Elfogadva0/06ms2068 KiB
4Elfogadva4/42ms2016 KiB
5Elfogadva2/22ms2016 KiB
6Elfogadva1/150ms4964 KiB
7Elfogadva1/139ms6732 KiB
8Elfogadva2/237ms8380 KiB
9Elfogadva2/239ms10212 KiB
10Elfogadva1/156ms11344 KiB
11Elfogadva1/161ms12488 KiB
12Elfogadva2/257ms13548 KiB
13Elfogadva2/252ms13600 KiB
14Elfogadva1/161ms15108 KiB
15Elfogadva1/164ms16704 KiB
16Elfogadva1/164ms18280 KiB
17Elfogadva1/161ms20048 KiB
18Elfogadva1/163ms20744 KiB
19Elfogadva2/261ms21648 KiB
20Elfogadva2/265ms23256 KiB
21Elfogadva3/356ms24504 KiB
22Elfogadva5/559ms24520 KiB
23Elfogadva5/568ms24508 KiB