512021-01-09 15:46:13mraronHáromszögekcpp11Elfogadva 40/4076ms32216 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/01ms1756 KiB
2Elfogadva0/01ms1784 KiB
3Elfogadva0/06ms2068 KiB
4Elfogadva4/42ms1984 KiB
5Elfogadva2/22ms2024 KiB
6Elfogadva1/156ms4968 KiB
7Elfogadva1/137ms6716 KiB
8Elfogadva2/239ms8460 KiB
9Elfogadva2/237ms10204 KiB
10Elfogadva1/157ms11372 KiB
11Elfogadva1/163ms12524 KiB
12Elfogadva2/259ms13568 KiB
13Elfogadva2/254ms14708 KiB
14Elfogadva1/171ms16640 KiB
15Elfogadva1/161ms18304 KiB
16Elfogadva1/161ms19936 KiB
17Elfogadva1/175ms21740 KiB
18Elfogadva1/164ms23316 KiB
19Elfogadva2/268ms24868 KiB
20Elfogadva2/265ms26572 KiB
21Elfogadva3/371ms28360 KiB
22Elfogadva5/559ms30324 KiB
23Elfogadva5/576ms32216 KiB