Kyselyt

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MN = 1<<19;
int xs[MN];
int xc[MN];

int tree[2*MN];
vector<int> pos[MN];

int count(int y, int p) {
	auto& v = pos[y];
	return lower_bound(v.begin(),v.end(),p)-v.begin();
}
int count(int y, int a, int b) {
	if (y==0) return 0;
	return count(y,b) - count(y,a);
}
int build(int i, int a, int b) {
	if (b-a<=1) return tree[i];
	int m = (a+b)/2;
	int x = build(2*i,a,m);
	int y = build(2*i+1,m,b);
	if (x==y) return tree[i]=x;
	int cx = count(x,a,b);
	int cy = count(y,a,b);
	int res = tree[i] = 2*cx>b-a ? x : 2*cy>b-a ? y : 0;
	return res;
}
int solve(int a, int b, int l, int r, int i) {
	if (l>=a && r<=b) return tree[i];
	if (r<=a || l>=b) return 0;
	int m = (l+r)/2;
	int x = solve(a,b,l,m,2*i);
	int y = solve(a,b,m,r,2*i+1);
	if (x==y) return x;
	int ll = max(l,a);
	int rr = min(r,b);
	int cx = count(x,ll,rr);
	int cy = count(y,ll,rr);
	return 2*cx>rr-ll ? x : 2*cy>rr-ll ? y : 0;
}

int main() {
	int n,q;cin>>n>>q;
	for(int i=0;i<n;++i)cin>>xs[i],xc[i]=xs[i];
	xc[n]=-1;
	sort(xc,xc+n+1);
	int k = unique(xc,xc+n+1)-xc;
	for(int i=0; i<n; ++i) {
		int y = lower_bound(xc,xc+k,xs[i])-xc;
		tree[MN+i]=y;
		pos[y].push_back(i);
	}
	build(1,0,MN);
	while(q--){
		int a,b;cin>>a>>b;
		cout<<xc[solve(a-1,b,0,MN,1)]<<'\n';
	}
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED