Submission details
Task:Kyselyt
Sender:Laakeri
Submission time:2025-10-18 00:55:19 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED20
#3ACCEPTED30
#4ACCEPTED40
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4details
#2ACCEPTED0.00 s1, 2, 3, 4details
#3ACCEPTED0.00 s1, 3, 4details
#4ACCEPTED0.24 s2, 3, 4details
#5ACCEPTED0.25 s2, 3, 4details
#6ACCEPTED0.25 s2, 3, 4details
#7ACCEPTED0.35 s3, 4details
#8ACCEPTED0.48 s4details
#9ACCEPTED0.54 s4details
#10ACCEPTED0.76 s4details
#11ACCEPTED0.30 s3, 4details
#12ACCEPTED0.63 s4details
#13ACCEPTED0.26 s3, 4details
#14ACCEPTED0.54 s4details
#15ACCEPTED0.52 s4details
#16ACCEPTED0.43 s4details

Code

#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;
}

const int N=1<<18;

pair<int,int> st[2*N];

pair<int,int> comb(pair<int,int> a, pair<int,int> b){
	if (a.F == b.F){
		return {a.F, a.S+b.S};
	} else {
		if (a.S > b.S) {
			return {a.F, a.S-b.S};
		} else if (a.S == b.S) {
			return {0,0};
		} else {
			return {b.F, b.S-a.S};
		}
	}
}

void ch(int i, pair<int,int> v){
	st[i+N]=v;
	for (i=(i+N)/2;i;i/=2){
		st[i]=comb(st[i*2], st[i*2+1]);
	}
}

pair<int,int> get(int a, int b) {
	pair<int,int> r={0,0};
	a+=N;
	b+=N;
	while (a<=b){
		if (a%2){
			r=comb(r, st[a]);
			a++;
		}
		if (b%2==0){
			r=comb(r, st[b]);
			b--;
		}
		a/=2;
		b/=2;
	}
	return r;
}

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);
		ch(i, {x[i], 1});
	}
	for (int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		pair<int,int> lol=get(a,b);
		if (ds(a,b,lol.F)){
			cout<<lol.F<<endl;
		} else {
			cout<<-1<<endl;
		}
	}
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
100 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
100 100
2 1 2 2 1 2 2 2 1 2 2 1 1 1 1 ...

correct output
2
1
1
2
1
...

user output
2
1
1
2
1
...

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

input
100 100
5 19 44 88 14 79 50 44 14 99 7...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

input
100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

input
100000 100000
1 1 1 2 1 2 1 1 2 1 1 1 1 2 2 ...

correct output
1
1
2
1
1
...

user output
1
1
2
1
1
...

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

input
100000 100000
8 2 6 1 10 4 9 7 8 10 4 2 8 2 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Test 7

Group: 3, 4

Verdict: ACCEPTED

input
100000 100000
141307 493258596 365539511 222...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Test 8

Group: 4

Verdict: ACCEPTED

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 9

Group: 4

Verdict: ACCEPTED

input
200000 200000
1 2 2 2 1 2 2 1 1 1 1 1 1 1 1 ...

correct output
2
2
2
2
2
...

user output
2
2
2
2
2
...

Test 10

Group: 4

Verdict: ACCEPTED

input
200000 200000
286470749 280175209 741317063 ...

correct output
-1
-1
-1
-1
-1
...

user output
-1
-1
-1
-1
-1
...

Test 11

Group: 3, 4

Verdict: ACCEPTED

input
100000 100000
613084013 1000000000 411999902...

correct output
-1
-1
-1
-1
1000000000
...

user output
-1
-1
-1
-1
1000000000
...

Test 12

Group: 4

Verdict: ACCEPTED

input
200000 200000
613084013 1000000000 411999902...

correct output
1000000000
1000000000
-1
1000000000
-1
...

user output
1000000000
1000000000
-1
1000000000
-1
...

Test 13

Group: 3, 4

Verdict: ACCEPTED

input
100000 100000
663307073 663307073 663307073 ...

correct output
329574367
965067805
768744535
691214891
21873594
...

user output
329574367
965067805
768744535
691214891
21873594
...

Test 14

Group: 4

Verdict: ACCEPTED

input
200000 200000
663307073 663307073 663307073 ...

correct output
107596959
249558965
679275202
760593154
725418770
...

user output
107596959
249558965
679275202
760593154
725418770
...

Test 15

Group: 4

Verdict: ACCEPTED

input
200000 200000
663307073 663307073 663307073 ...

correct output
211070558
49212342
651109313
264549124
651109313
...

user output
211070558
49212342
651109313
264549124
651109313
...

Test 16

Group: 4

Verdict: ACCEPTED

input
200000 200000
2 2 2 1 2 1 1 2 2 1 1 1 1 2 1 ...

correct output
1
2
1
1
1
...

user output
1
2
1
1
1
...