CSES - Putka Open 2025 – 3/5

Submission details
Task:	Kyselyt
Sender:	Laakeri
Submission time:	2025-10-18 00:55:19 +0300
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	30
#4	ACCEPTED	40

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 3, 4	details
#2	ACCEPTED	0.00 s	1, 2, 3, 4	details
#3	ACCEPTED	0.00 s	1, 3, 4	details
#4	ACCEPTED	0.24 s	2, 3, 4	details
#5	ACCEPTED	0.25 s	2, 3, 4	details
#6	ACCEPTED	0.25 s	2, 3, 4	details
#7	ACCEPTED	0.35 s	3, 4	details
#8	ACCEPTED	0.48 s	4	details
#9	ACCEPTED	0.54 s	4	details
#10	ACCEPTED	0.76 s	4	details
#11	ACCEPTED	0.30 s	3, 4	details
#12	ACCEPTED	0.63 s	4	details
#13	ACCEPTED	0.26 s	3, 4	details
#14	ACCEPTED	0.54 s	4	details
#15	ACCEPTED	0.52 s	4	details
#16	ACCEPTED	0.43 s	4	details

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 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

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 ...` view save

correct output
`2 1 1 2 1 ...` view save

user output
`2 1 1 2 1 ...` Truncated

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

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

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

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 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

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 ...` view save

correct output
`1 1 2 1 1 ...` view save

user output
`1 1 2 1 1 ...` Truncated

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 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 7

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 141307 493258596 365539511 222...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 8

Group: 4

Verdict: ACCEPTED

input
`200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 9

Group: 4

Verdict: ACCEPTED

input
`200000 200000 1 2 2 2 1 2 2 1 1 1 1 1 1 1 1 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` Truncated

Test 10

Group: 4

Verdict: ACCEPTED

input
`200000 200000 286470749 280175209 741317063 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 11

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 613084013 1000000000 411999902...` view save

correct output
`-1 -1 -1 -1 1000000000 ...` view save

user output
`-1 -1 -1 -1 1000000000 ...` Truncated

Test 12

Group: 4

Verdict: ACCEPTED

input
`200000 200000 613084013 1000000000 411999902...` view save

correct output
`1000000000 1000000000 -1 1000000000 -1 ...` view save

user output
`1000000000 1000000000 -1 1000000000 -1 ...` Truncated

Test 13

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 663307073 663307073 663307073 ...` view save

correct output
`329574367 965067805 768744535 691214891 21873594 ...` view save

user output
`329574367 965067805 768744535 691214891 21873594 ...` Truncated

Test 14

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`107596959 249558965 679275202 760593154 725418770 ...` view save

user output
`107596959 249558965 679275202 760593154 725418770 ...` Truncated

Test 15

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`211070558 49212342 651109313 264549124 651109313 ...` view save

user output
`211070558 49212342 651109313 264549124 651109313 ...` Truncated

Test 16

Group: 4

Verdict: ACCEPTED

input
`200000 200000 2 2 2 1 2 1 1 2 2 1 1 1 1 2 1 ...` view save

correct output
`1 2 1 1 1 ...` view save

user output
`1 2 1 1 1 ...` Truncated

Putka Open 2025 – 3/5

Kyselyt

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Laakeri)