#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
int tree[4*MAXN];
void upd(int node, int l, int r, int pos, int val){
if(r<pos || l>pos)
return;
if(l==r){
tree[node]=val;
return;
}
int mid=(l+r)/2;
upd(node*2, l, mid, pos, val);
upd(node*2+1, mid+1, r, pos, val);
tree[node]=tree[node*2]+tree[node*2+1];
}
pii search(int node, int l, int r, int val){
if(l==r)
return {l, tree[node]};
int mid=(l+r)/2;
if(tree[node*2]>=val)
return search(node*2, l, mid, val);
pii resp=search(node*2+1, mid+1, r, val-tree[node*2]);
return {resp.fi, resp.se+tree[node*2]};
}
void solve(){
int n, q; cin >> n >> q;
vector<int> arr(n);
for(int i=0;i<n;i++)
cin >> arr[i];
vector<pair<pii, int>> query(q);
for(int i=0;i<q;i++)
cin >> query[i].fi.fi >> query[i].fi.se, query[i].se=i;
sort(all(query));
vector<int> ans(q);
vector<int> rev(n+1);
for(int i=0;i<n;i++)
rev[arr[i]]=i;
int cnt=0;
bool foi=0;
vector<int> nx(n+1);
set<pii> act;
for(int i=0;i<n;i++){
auto curr=act.begin();
while(curr!=act.end() && curr->fi<arr[i]){
nx[curr->fi]=i-curr->se;
curr=act.erase(curr);
}
act.insert({arr[i], i});
}
for(auto u : act)
nx[u.fi]=n-u.se;
vector<int> sz(n+1, 0);
for(int i=0;i<n;i++){
sz[arr[i]]=nx[arr[i]];
upd(1, 1, n, arr[i], nx[arr[i]]);
i+=(nx[arr[i]]-1);
}
for(int i=0;i<q;i++){
while(!foi && cnt<query[i].fi.fi){
pii curr=search(1, 1, n, n/2+1);
if(curr.se-sz[curr.fi]>=n/2){
foi=1;
break;
}
// cout << cnt << ":\n";
// for(int i=1;i<=n;i++)
// cout << i << " -> " << sz[i] << "\t\n"[i==n];
int nwsize=n/2-curr.se+sz[curr.fi];
// cout << "nwsize= " << nwsize << "\t" << " " << curr.fi << "\n";
upd(1, 1, n, curr.fi, nwsize);
int ptr=rev[curr.fi]+nwsize;
while(ptr<n && rev[curr.fi]+sz[curr.fi]-ptr>0){
int at=nx[arr[ptr]];
// if(ptr+at<n && arr[ptr+at]>curr.fi) at--;
upd(1, 1, n, arr[ptr], min(at, rev[curr.fi]+sz[curr.fi]-ptr));
sz[arr[ptr]]=min(at, rev[curr.fi]+sz[curr.fi]-ptr);
ptr+=nx[arr[ptr]];
}
sz[curr.fi]=nwsize;
cnt++;
}
pii resp=search(1, 1, n, query[i].fi.se);
// cout << "resp.fi = " << resp.fi << "\n";
ans[query[i].se]=arr[rev[resp.fi]+query[i].fi.se-(resp.se-sz[resp.fi]+1)];
}
// cout << cnt << ":\n";
// for(int i=1;i<=n;i++)
// cout << i << " -> " << sz[i] << "\t\n"[i==n];
for(int i=0;i<q;i++)
cout << ans[i] << "\n";
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int tt=1;
// cin >> tt;
while(tt--)
solve();
}
/*
4 3
3 1 2 4
0 2
1 3
2 2
2 3 1 4 -> 1°
1 2 3 4 -> 2°
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
19876 KB |
Output is correct |
2 |
Correct |
284 ms |
27220 KB |
Output is correct |
3 |
Correct |
278 ms |
26468 KB |
Output is correct |
4 |
Correct |
271 ms |
25212 KB |
Output is correct |
5 |
Correct |
282 ms |
27016 KB |
Output is correct |
6 |
Correct |
266 ms |
25328 KB |
Output is correct |
7 |
Correct |
281 ms |
26964 KB |
Output is correct |
8 |
Correct |
276 ms |
25472 KB |
Output is correct |
9 |
Correct |
271 ms |
25168 KB |
Output is correct |
10 |
Correct |
280 ms |
25860 KB |
Output is correct |
11 |
Correct |
271 ms |
25700 KB |
Output is correct |
12 |
Correct |
263 ms |
24652 KB |
Output is correct |
13 |
Correct |
274 ms |
25420 KB |
Output is correct |
14 |
Correct |
276 ms |
26428 KB |
Output is correct |
15 |
Correct |
282 ms |
26244 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
263 ms |
24844 KB |
Output is correct |
18 |
Correct |
289 ms |
24916 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
370 ms |
32456 KB |
Output is correct |
2 |
Correct |
314 ms |
42840 KB |
Output is correct |
3 |
Correct |
275 ms |
38228 KB |
Output is correct |
4 |
Correct |
283 ms |
33688 KB |
Output is correct |
5 |
Correct |
293 ms |
34508 KB |
Output is correct |
6 |
Correct |
259 ms |
33008 KB |
Output is correct |
7 |
Correct |
306 ms |
40948 KB |
Output is correct |
8 |
Correct |
291 ms |
39368 KB |
Output is correct |
9 |
Correct |
274 ms |
34132 KB |
Output is correct |
10 |
Correct |
283 ms |
38352 KB |
Output is correct |
11 |
Correct |
280 ms |
32588 KB |
Output is correct |
12 |
Correct |
248 ms |
32336 KB |
Output is correct |
13 |
Correct |
272 ms |
37800 KB |
Output is correct |
14 |
Correct |
268 ms |
33360 KB |
Output is correct |
15 |
Correct |
308 ms |
39760 KB |
Output is correct |
16 |
Correct |
25 ms |
7004 KB |
Output is correct |
17 |
Correct |
312 ms |
35920 KB |
Output is correct |
18 |
Correct |
257 ms |
39132 KB |
Output is correct |
19 |
Correct |
67 ms |
12628 KB |
Output is correct |
20 |
Correct |
74 ms |
14312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
8580 KB |
Output is correct |
2 |
Correct |
59 ms |
8668 KB |
Output is correct |
3 |
Correct |
61 ms |
10068 KB |
Output is correct |
4 |
Correct |
45 ms |
7720 KB |
Output is correct |
5 |
Correct |
54 ms |
8016 KB |
Output is correct |
6 |
Correct |
44 ms |
7660 KB |
Output is correct |
7 |
Correct |
54 ms |
8020 KB |
Output is correct |
8 |
Correct |
46 ms |
7764 KB |
Output is correct |
9 |
Correct |
50 ms |
7852 KB |
Output is correct |
10 |
Correct |
43 ms |
7596 KB |
Output is correct |
11 |
Correct |
42 ms |
7748 KB |
Output is correct |
12 |
Correct |
40 ms |
7760 KB |
Output is correct |
13 |
Correct |
42 ms |
7608 KB |
Output is correct |
14 |
Correct |
53 ms |
8016 KB |
Output is correct |
15 |
Correct |
40 ms |
7572 KB |
Output is correct |
16 |
Correct |
12 ms |
4700 KB |
Output is correct |
17 |
Correct |
45 ms |
7488 KB |
Output is correct |
18 |
Correct |
48 ms |
11864 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
19876 KB |
Output is correct |
2 |
Correct |
284 ms |
27220 KB |
Output is correct |
3 |
Correct |
278 ms |
26468 KB |
Output is correct |
4 |
Correct |
271 ms |
25212 KB |
Output is correct |
5 |
Correct |
282 ms |
27016 KB |
Output is correct |
6 |
Correct |
266 ms |
25328 KB |
Output is correct |
7 |
Correct |
281 ms |
26964 KB |
Output is correct |
8 |
Correct |
276 ms |
25472 KB |
Output is correct |
9 |
Correct |
271 ms |
25168 KB |
Output is correct |
10 |
Correct |
280 ms |
25860 KB |
Output is correct |
11 |
Correct |
271 ms |
25700 KB |
Output is correct |
12 |
Correct |
263 ms |
24652 KB |
Output is correct |
13 |
Correct |
274 ms |
25420 KB |
Output is correct |
14 |
Correct |
276 ms |
26428 KB |
Output is correct |
15 |
Correct |
282 ms |
26244 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
263 ms |
24844 KB |
Output is correct |
18 |
Correct |
289 ms |
24916 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
370 ms |
32456 KB |
Output is correct |
22 |
Correct |
314 ms |
42840 KB |
Output is correct |
23 |
Correct |
275 ms |
38228 KB |
Output is correct |
24 |
Correct |
283 ms |
33688 KB |
Output is correct |
25 |
Correct |
293 ms |
34508 KB |
Output is correct |
26 |
Correct |
259 ms |
33008 KB |
Output is correct |
27 |
Correct |
306 ms |
40948 KB |
Output is correct |
28 |
Correct |
291 ms |
39368 KB |
Output is correct |
29 |
Correct |
274 ms |
34132 KB |
Output is correct |
30 |
Correct |
283 ms |
38352 KB |
Output is correct |
31 |
Correct |
280 ms |
32588 KB |
Output is correct |
32 |
Correct |
248 ms |
32336 KB |
Output is correct |
33 |
Correct |
272 ms |
37800 KB |
Output is correct |
34 |
Correct |
268 ms |
33360 KB |
Output is correct |
35 |
Correct |
308 ms |
39760 KB |
Output is correct |
36 |
Correct |
25 ms |
7004 KB |
Output is correct |
37 |
Correct |
312 ms |
35920 KB |
Output is correct |
38 |
Correct |
257 ms |
39132 KB |
Output is correct |
39 |
Correct |
67 ms |
12628 KB |
Output is correct |
40 |
Correct |
74 ms |
14312 KB |
Output is correct |
41 |
Correct |
73 ms |
8580 KB |
Output is correct |
42 |
Correct |
59 ms |
8668 KB |
Output is correct |
43 |
Correct |
61 ms |
10068 KB |
Output is correct |
44 |
Correct |
45 ms |
7720 KB |
Output is correct |
45 |
Correct |
54 ms |
8016 KB |
Output is correct |
46 |
Correct |
44 ms |
7660 KB |
Output is correct |
47 |
Correct |
54 ms |
8020 KB |
Output is correct |
48 |
Correct |
46 ms |
7764 KB |
Output is correct |
49 |
Correct |
50 ms |
7852 KB |
Output is correct |
50 |
Correct |
43 ms |
7596 KB |
Output is correct |
51 |
Correct |
42 ms |
7748 KB |
Output is correct |
52 |
Correct |
40 ms |
7760 KB |
Output is correct |
53 |
Correct |
42 ms |
7608 KB |
Output is correct |
54 |
Correct |
53 ms |
8016 KB |
Output is correct |
55 |
Correct |
40 ms |
7572 KB |
Output is correct |
56 |
Correct |
12 ms |
4700 KB |
Output is correct |
57 |
Correct |
45 ms |
7488 KB |
Output is correct |
58 |
Correct |
48 ms |
11864 KB |
Output is correct |
59 |
Correct |
0 ms |
348 KB |
Output is correct |
60 |
Correct |
0 ms |
348 KB |
Output is correct |
61 |
Correct |
445 ms |
46368 KB |
Output is correct |
62 |
Correct |
441 ms |
42580 KB |
Output is correct |
63 |
Correct |
422 ms |
44224 KB |
Output is correct |
64 |
Correct |
396 ms |
39440 KB |
Output is correct |
65 |
Correct |
421 ms |
41044 KB |
Output is correct |
66 |
Correct |
373 ms |
39248 KB |
Output is correct |
67 |
Correct |
418 ms |
40528 KB |
Output is correct |
68 |
Correct |
363 ms |
39092 KB |
Output is correct |
69 |
Correct |
384 ms |
39264 KB |
Output is correct |
70 |
Correct |
360 ms |
38712 KB |
Output is correct |
71 |
Correct |
358 ms |
37904 KB |
Output is correct |
72 |
Correct |
342 ms |
38484 KB |
Output is correct |
73 |
Correct |
361 ms |
38248 KB |
Output is correct |
74 |
Correct |
359 ms |
39516 KB |
Output is correct |
75 |
Correct |
358 ms |
39508 KB |
Output is correct |
76 |
Correct |
24 ms |
6996 KB |
Output is correct |
77 |
Correct |
335 ms |
36092 KB |
Output is correct |
78 |
Correct |
362 ms |
45140 KB |
Output is correct |
79 |
Correct |
0 ms |
348 KB |
Output is correct |
80 |
Correct |
0 ms |
472 KB |
Output is correct |