#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
const int MAXQ = 1e6;
typedef pair<int, int> pii;
int nxt[MAXN];
int sz[MAXN];
int bit[2*MAXN];
int n_round;
int arr[MAXN];
int inv[MAXN];
int queries[MAXQ];
int ans[MAXQ];
pii sorted[MAXQ];
int n, q;
void upd(int x, int v) {
for (; x < n_round; x|=(x+1)) bit[x] += v;
}
pii get_pos(int l = 0, int r = n_round, int v = n/2) { // first pos such that including it is greater than v, along with how much v left
if (r == l+1) return pii(l, v);
if (bit[(l+r)/2-1] > v) return get_pos(l, (l+r)/2, v);
return get_pos((l+r)/2, r, v-bit[(l+r)/2-1]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> q;
n_round = 1<<(32-__builtin_clz(n-1));
vector<int> stck;
for (int i = 0; i < n; i++) {
cin >> arr[i]; arr[i]--;
inv[arr[i]] = i;
while (!stck.empty() && arr[i] > arr[stck.back()]) {
nxt[stck.back()] = i;
stck.pop_back();
}
stck.push_back(i);
}
for (int v: stck) nxt[v] = n;
int cur = 0;
while (cur != n) {
sz[arr[cur]] = nxt[cur]-cur;
upd(arr[cur], sz[arr[cur]]);
cur = nxt[cur];
}
for (int i = 0; i < q; i++) {
int p, t; cin >> t >> p;
queries[i] = p;
sorted[i] = pii(t, i);
}
sort(sorted, sorted+q);
int t = 0;
int j = 0;
while (j < q) {
while (j < q && sorted[j].first == t) {
pii p = get_pos(0, n_round, queries[sorted[j].second]-1);
ans[sorted[j].second] = (1+arr[inv[p.first]+p.second]);
j++;
}
t++;
pii p = get_pos();
if (p.second == 0) break; // stabilized
upd(p.first, -sz[p.first]+p.second);
sz[p.first] = p.second;
int cur = inv[p.first]+p.second;
while (cur < nxt[inv[p.first]]) {
// assert(sz[arr[cur]] == 0);
sz[arr[cur]] = nxt[cur]-cur;
upd(arr[cur], sz[arr[cur]]);
cur = nxt[cur];
}
nxt[inv[p.first]] = inv[p.first]+p.second;
}
while (j < q) {
pii p = get_pos(0, n_round, queries[sorted[j].second]-1);
ans[sorted[j].second] = 1+arr[inv[p.first]+p.second];
j++;
}
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
348 ms |
19712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
291 ms |
25160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3047 ms |
3984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
348 ms |
19712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
