Task: | Kyselyt |
Sender: | Laakeri |
Submission time: | 2025-10-18 00:55:19 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 20 |
#3 | ACCEPTED | 30 |
#4 | ACCEPTED | 40 |
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 ... |
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 ... |