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;
}
void collect(int a, int b, vector<int>& v) {
	for(a+=MN,b+=MN; a<=b; a/=2,b/=2) {
		if (a%2==1) v.push_back(tree[a++]);
		if (b%2==0) v.push_back(tree[b--]);
	}
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	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);
	vector<int> v;
	while(q--){
		int a,b;cin>>a>>b;
		v.clear();
		collect(a-1,b-1,v);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		int x=0;
		for(int i:v) {
			int c = count(i,a-1,b);
			if (2*c > b-a+1) {
				x=i;
				break;
			}
		}
		cout<<xc[x]<<'\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: ACCEPTED

Test 9

Group: 4

Verdict: ACCEPTED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: ACCEPTED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED