Kyselyt

#include <iostream>
using namespace std;
const int MN = 200<<10;
int vs[MN];
int ds[MN];

#if 1
int tree[2*MN];
void add(int i, int v) {
	for(i+=MN; i; i/=2) {
		tree[i] = max(tree[i],v);
	}
}
int get(int a, int b) {
	int r=0;
	for(a+=MN,b+=MN; a<=b; a>>=1,b>>=1) {
		if (a&1) r=max(r,tree[a++]);
		if (!(b&1)) r=max(r,tree[b--]);
	}
	return r;
}
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int n,q;cin>>n>>q;
	for(int i=0; i<n; ++i) {
		cin>>vs[i];
	}
	for(int i=0, j=0; i<n; ++i) {
		while(j<n && vs[j]<2*vs[i]) ++j;
		ds[i] = j-i;
		add(i+1,ds[i]);
	}
	while(q--) {
		int a,b;cin>>a>>b;
		int n = b-a+1;
		int low=0;
		int hi=n/2+1;
		//cout<<"range "<<a<<' '<<b<<" ; "<<n<<' '<<hi<<'\n';
		while(hi-low>1) {
			int m = (low+hi)/2;
			int x = get(a,a+m-1);
			//cout<<"get "<<a<<' '<<a+low-1<<" = "<<x<<" ; "<<m<<'\n';
			if (x <= n-m) low=m;
			else hi=m;
		}
		cout<<low<<'\n';
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED