// heiy ... ye rooze jadid ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;
int sum[maxnt], a[maxn5], rev[maxn5], out[maxn5], per[maxn5];
int rig[maxn5], sz[maxn5], t[maxn5], ind[maxn5];
bool mark[maxn5];
vector <int> av;
inline bool cmp(int i, int j){return t[i] < t[j];}
void upd(int l, int r, int id, int val, int v){
if(r - l == 1){
sum[v] = val;
return;
}
int mid = (l + r) >> 1;
if(id < mid)
upd(l, mid, id, val, v * 2);
else
upd(mid, r, id, val, v * 2 + 1);
sum[v] = sum[v * 2] + sum[v * 2 + 1];
}
pair<int, int> find_first(int l, int r, int val, int v){
if(r - l == 1)
return {l, sum[v]};
int mid = (l + r) >> 1;
if(sum[v * 2] >= val)
return find_first(l, mid, val, v * 2);
auto ans = find_first(mid, r, val - sum[v * 2], v * 2 + 1);
return {ans.fi, ans.se + sum[v * 2]};
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q; cin >> n >> q;
for(int i = 0; i < n; i++){
cin >> a[i];
a[i]--;
rev[a[i]] = i;
}
for(int i = 0; i < q; i++){
cin >> t[i] >> ind[i];
per[i] = i;
}
fill(rig, rig + n + 10, n);
for(int i = n - 1; i >= 0; i--){
while(av.size() && a[av.back()] < a[i])
av.pop_back();
if(av.size())
rig[i] = av.back();
av.pb(i);
}
for(int i = 0; i != n; i = rig[i]){
upd(0, n, a[i], rig[i] - i, 1);
sz[i] = rig[i] - i;
mark[i] = true;
//cout << "ok " << i << ' ' << rig[i] << ' ' << sz[i] << endl;
}
sort(per, per + q, cmp); // bar hasbe t[i]
int done = 0;
bool re = false;
for(int i = 0; i < q; i++){
while(done < t[per[i]] && !re){
done++;
auto tmp = find_first(0, n, n / 2, 1);
int p = tmp.fi, r = tmp.se - n / 2;
if(r == 0){
re = true;
break;
}
int v = rev[p] + sz[rev[p]] - r;
//cout << "now " << done << ' ' << p << ' ' << r << ' ' << v << ' ' << rev[p] << ' ' << sz[rev[p]] << ' ' << tmp.se << endl;
sz[rev[p]] -= r;
upd(0, n, p, sz[rev[p]], 1);
for(; !mark[v] && v != n ; v = rig[v]){
mark[v] = true;
sz[v] = rig[v] - v;
upd(0, n, a[v], sz[v], 1);
}
}
auto tmp = find_first(0, n, ind[per[i]], 1);
int p = tmp.fi, r = tmp.se - ind[per[i]];
r = sz[rev[p]] - r - 1;
out[per[i]] = a[rev[p] + r] + 1;
}
for(int i = 0; i < q; i++)
cout << out[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
356 ms |
19788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
344 ms |
39536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
4788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
356 ms |
19788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
