#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
struct segtree{
int sz; vi sm;
void init(int n){
sz=n; sm.assign(4*n,0);
}
void update(int v, int tl, int tr, int pos, int val){
if (tl==tr) {sm[v]=val; return;}
int tm=(tl+tr)/2;
if (pos<=tm) update(2*v,tl,tm,pos,val);
else update(2*v+1,tm+1,tr,pos,val);
sm[v]=sm[2*v]+sm[2*v+1];
}
void update(int pos, int val) {update(1,0,sz-1,pos,val);}
ii get(int v, int tl, int tr, int val){
if (tl==tr) {return {tl,val};}
int tm=(tl+tr)/2;
if (sm[2*v]<val) return get(2*v+1,tm+1,tr,val-sm[2*v]);
return get(2*v,tl,tm,val);
}
ii get(int val){return get(1,0,sz-1,val);}
};
struct segtree2{
int sz; vi mx, a;
void init(int n, vi A){
sz=n; mx.assign(4*n,-1); a=A;
}
void build(int v, int tl, int tr){
if (tl==tr){mx[v]=tl; return;}
int tm=(tl+tr)/2;
build(2*v,tl,tm); build(2*v+1,tm+1,tr);
if (a[mx[2*v]]>a[mx[2*v+1]]) mx[v]=mx[2*v];
else mx[v]=mx[2*v+1];
}
int get(int v, int tl, int tr, int l, int r){
if (tl==l && tr==r) return mx[v];
if (l>r) return -1;
int tm=(tl+tr)/2;
int L=get(2*v,tl,tm,l,min(r,tm)); int R=get(2*v+1,tm+1,tr,max(l,tm+1),r);
if (L==-1) return R;
if (R==-1) return L;
if (a[L]<a[R]) return R;
return L;
}
int get(int l, int r){return get(1,0,sz-1,l,r);}
};
struct que{
int id, pos, t;
};
void solve(){
int n,q; cin>>n>>q;
vi a(n); FOR(i,0,n){ cin>>a[i]; a[i]--;}
segtree2 st2; st2.init(n,a); st2.build(1,0,n-1);
vi pos(n); FOR(i,0,n) pos[a[i]]=i;
vi sz(n);
vector<que> Q[n]; vi ans(q);
FOR(i,0,q){
que qr; cin>>qr.t>>qr.pos; qr.id=i; qr.pos--;
if (qr.t>=n) qr.t=n-1;
Q[qr.t].pb(qr);
}
segtree st; st.init(n);
vi used(n);
ROF(i,n-1,0){
if (used[i]) continue;
int L = pos[i]; int cnt=0;
while (L < n){
if (used[a[L]]) break;
cnt++; used[a[L]]=1; L++;
}
st.update(i,cnt); sz[i]=cnt;
//cout<<i<<" "<<cnt<<'\n';
}
FOR(i,0,n){
for (que qr : Q[i]){
ii val = st.get(qr.pos+1);
ans[qr.id] = a[pos[val.fi]+val.se-1];
}
ii val = st.get(n/2+1);
if (val.se == 1) continue;
int L=pos[val.fi]+val.se-1, R=pos[val.fi]+sz[val.fi]-1;
while(st2.get(L,R) != -1){
int mx = st2.get(L,R);
sz[a[mx]]=R-mx+1; st.update(a[mx],sz[a[mx]]);
R=mx-1;
}
sz[val.fi]=val.se-1; st.update(val.fi, sz[val.fi]);
}
FOR(i,0,q) cout<<ans[i]+1<<"\n";
}
int main(){
//MOD=MOD1;
ios::sync_with_stdio(false);
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int TC = 1;
//cin >> TC;
FOR(i, 1, TC+1){
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
31052 KB |
Output is correct |
2 |
Correct |
221 ms |
29008 KB |
Output is correct |
3 |
Correct |
219 ms |
28556 KB |
Output is correct |
4 |
Correct |
184 ms |
25840 KB |
Output is correct |
5 |
Correct |
190 ms |
30956 KB |
Output is correct |
6 |
Correct |
176 ms |
31356 KB |
Output is correct |
7 |
Correct |
202 ms |
32320 KB |
Output is correct |
8 |
Correct |
174 ms |
29608 KB |
Output is correct |
9 |
Correct |
173 ms |
27988 KB |
Output is correct |
10 |
Correct |
175 ms |
27112 KB |
Output is correct |
11 |
Correct |
176 ms |
27904 KB |
Output is correct |
12 |
Correct |
183 ms |
24740 KB |
Output is correct |
13 |
Correct |
181 ms |
26148 KB |
Output is correct |
14 |
Correct |
189 ms |
30456 KB |
Output is correct |
15 |
Correct |
186 ms |
26544 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
204 ms |
25044 KB |
Output is correct |
18 |
Correct |
169 ms |
24920 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
320 ms |
51604 KB |
Output is correct |
2 |
Correct |
318 ms |
50688 KB |
Output is correct |
3 |
Correct |
258 ms |
42632 KB |
Output is correct |
4 |
Correct |
215 ms |
42828 KB |
Output is correct |
5 |
Correct |
222 ms |
43804 KB |
Output is correct |
6 |
Correct |
217 ms |
42100 KB |
Output is correct |
7 |
Correct |
262 ms |
50392 KB |
Output is correct |
8 |
Correct |
250 ms |
48280 KB |
Output is correct |
9 |
Correct |
229 ms |
43768 KB |
Output is correct |
10 |
Correct |
241 ms |
47204 KB |
Output is correct |
11 |
Correct |
201 ms |
41840 KB |
Output is correct |
12 |
Correct |
194 ms |
41304 KB |
Output is correct |
13 |
Correct |
223 ms |
46684 KB |
Output is correct |
14 |
Correct |
209 ms |
42528 KB |
Output is correct |
15 |
Correct |
230 ms |
48536 KB |
Output is correct |
16 |
Correct |
27 ms |
16324 KB |
Output is correct |
17 |
Correct |
254 ms |
45088 KB |
Output is correct |
18 |
Correct |
173 ms |
39212 KB |
Output is correct |
19 |
Correct |
64 ms |
22020 KB |
Output is correct |
20 |
Correct |
76 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
12624 KB |
Output is correct |
2 |
Correct |
57 ms |
12412 KB |
Output is correct |
3 |
Correct |
62 ms |
12008 KB |
Output is correct |
4 |
Correct |
40 ms |
11980 KB |
Output is correct |
5 |
Correct |
59 ms |
12352 KB |
Output is correct |
6 |
Correct |
43 ms |
11892 KB |
Output is correct |
7 |
Correct |
59 ms |
12348 KB |
Output is correct |
8 |
Correct |
49 ms |
11936 KB |
Output is correct |
9 |
Correct |
52 ms |
12184 KB |
Output is correct |
10 |
Correct |
35 ms |
11604 KB |
Output is correct |
11 |
Correct |
38 ms |
12124 KB |
Output is correct |
12 |
Correct |
36 ms |
11692 KB |
Output is correct |
13 |
Correct |
36 ms |
11512 KB |
Output is correct |
14 |
Correct |
36 ms |
12032 KB |
Output is correct |
15 |
Correct |
34 ms |
11728 KB |
Output is correct |
16 |
Correct |
13 ms |
8156 KB |
Output is correct |
17 |
Correct |
42 ms |
10852 KB |
Output is correct |
18 |
Correct |
31 ms |
10796 KB |
Output is correct |
19 |
Correct |
0 ms |
320 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
201 ms |
31052 KB |
Output is correct |
2 |
Correct |
221 ms |
29008 KB |
Output is correct |
3 |
Correct |
219 ms |
28556 KB |
Output is correct |
4 |
Correct |
184 ms |
25840 KB |
Output is correct |
5 |
Correct |
190 ms |
30956 KB |
Output is correct |
6 |
Correct |
176 ms |
31356 KB |
Output is correct |
7 |
Correct |
202 ms |
32320 KB |
Output is correct |
8 |
Correct |
174 ms |
29608 KB |
Output is correct |
9 |
Correct |
173 ms |
27988 KB |
Output is correct |
10 |
Correct |
175 ms |
27112 KB |
Output is correct |
11 |
Correct |
176 ms |
27904 KB |
Output is correct |
12 |
Correct |
183 ms |
24740 KB |
Output is correct |
13 |
Correct |
181 ms |
26148 KB |
Output is correct |
14 |
Correct |
189 ms |
30456 KB |
Output is correct |
15 |
Correct |
186 ms |
26544 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
204 ms |
25044 KB |
Output is correct |
18 |
Correct |
169 ms |
24920 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
320 ms |
51604 KB |
Output is correct |
22 |
Correct |
318 ms |
50688 KB |
Output is correct |
23 |
Correct |
258 ms |
42632 KB |
Output is correct |
24 |
Correct |
215 ms |
42828 KB |
Output is correct |
25 |
Correct |
222 ms |
43804 KB |
Output is correct |
26 |
Correct |
217 ms |
42100 KB |
Output is correct |
27 |
Correct |
262 ms |
50392 KB |
Output is correct |
28 |
Correct |
250 ms |
48280 KB |
Output is correct |
29 |
Correct |
229 ms |
43768 KB |
Output is correct |
30 |
Correct |
241 ms |
47204 KB |
Output is correct |
31 |
Correct |
201 ms |
41840 KB |
Output is correct |
32 |
Correct |
194 ms |
41304 KB |
Output is correct |
33 |
Correct |
223 ms |
46684 KB |
Output is correct |
34 |
Correct |
209 ms |
42528 KB |
Output is correct |
35 |
Correct |
230 ms |
48536 KB |
Output is correct |
36 |
Correct |
27 ms |
16324 KB |
Output is correct |
37 |
Correct |
254 ms |
45088 KB |
Output is correct |
38 |
Correct |
173 ms |
39212 KB |
Output is correct |
39 |
Correct |
64 ms |
22020 KB |
Output is correct |
40 |
Correct |
76 ms |
23132 KB |
Output is correct |
41 |
Correct |
75 ms |
12624 KB |
Output is correct |
42 |
Correct |
57 ms |
12412 KB |
Output is correct |
43 |
Correct |
62 ms |
12008 KB |
Output is correct |
44 |
Correct |
40 ms |
11980 KB |
Output is correct |
45 |
Correct |
59 ms |
12352 KB |
Output is correct |
46 |
Correct |
43 ms |
11892 KB |
Output is correct |
47 |
Correct |
59 ms |
12348 KB |
Output is correct |
48 |
Correct |
49 ms |
11936 KB |
Output is correct |
49 |
Correct |
52 ms |
12184 KB |
Output is correct |
50 |
Correct |
35 ms |
11604 KB |
Output is correct |
51 |
Correct |
38 ms |
12124 KB |
Output is correct |
52 |
Correct |
36 ms |
11692 KB |
Output is correct |
53 |
Correct |
36 ms |
11512 KB |
Output is correct |
54 |
Correct |
36 ms |
12032 KB |
Output is correct |
55 |
Correct |
34 ms |
11728 KB |
Output is correct |
56 |
Correct |
13 ms |
8156 KB |
Output is correct |
57 |
Correct |
42 ms |
10852 KB |
Output is correct |
58 |
Correct |
31 ms |
10796 KB |
Output is correct |
59 |
Correct |
0 ms |
320 KB |
Output is correct |
60 |
Correct |
0 ms |
212 KB |
Output is correct |
61 |
Correct |
535 ms |
59596 KB |
Output is correct |
62 |
Correct |
471 ms |
58680 KB |
Output is correct |
63 |
Correct |
514 ms |
56628 KB |
Output is correct |
64 |
Correct |
361 ms |
56552 KB |
Output is correct |
65 |
Correct |
374 ms |
58896 KB |
Output is correct |
66 |
Correct |
361 ms |
56364 KB |
Output is correct |
67 |
Correct |
324 ms |
56052 KB |
Output is correct |
68 |
Correct |
316 ms |
53720 KB |
Output is correct |
69 |
Correct |
351 ms |
57220 KB |
Output is correct |
70 |
Correct |
291 ms |
51604 KB |
Output is correct |
71 |
Correct |
263 ms |
53752 KB |
Output is correct |
72 |
Correct |
286 ms |
52344 KB |
Output is correct |
73 |
Correct |
280 ms |
53132 KB |
Output is correct |
74 |
Correct |
307 ms |
55940 KB |
Output is correct |
75 |
Correct |
285 ms |
53320 KB |
Output is correct |
76 |
Correct |
27 ms |
16332 KB |
Output is correct |
77 |
Correct |
312 ms |
45408 KB |
Output is correct |
78 |
Correct |
259 ms |
45212 KB |
Output is correct |
79 |
Correct |
0 ms |
212 KB |
Output is correct |
80 |
Correct |
0 ms |
212 KB |
Output is correct |