Kyselyt

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 gen(1337);

int getrand(int a, int b){
	uniform_int_distribution<int> d(a, b);
	return d(gen);
}

int x[202020];

map<int, vector<int>> pos;

int ds(int a, int b, int t){
	int need = (b-a+3)/2;
	auto fi=lower_bound(pos[t].begin(), pos[t].end(), a);
	if (fi == pos[t].end()) return 0;
	auto la=lower_bound(pos[t].begin(), pos[t].end(), b+1);
	return (la-fi) >= need;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	for (int i=1;i<=n;i++){
		cin>>x[i];
		pos[x[i]].push_back(i);
	}
	for (int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		int f=0;
		map<int,int> lol;
		for (int j=0;j<100;j++){
			int p=getrand(a,b);
			lol[x[p]]++;
		}
		for (auto t : lol){
			if (t.S > 34){
				if (ds(a,b,t.F)){
					cout<<t.F<<endl;
					f=1;
					break;
				}
			}
		}
		if (!f){
			cout<<-1<<endl;
		}
	}
}

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: WRONG ANSWER

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: WRONG ANSWER

Test 14

Group: 4

Verdict: WRONG ANSWER

Test 15

Group: 4

Verdict: WRONG ANSWER

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED