#include <bits/stdc++.h>
using namespace std;
int n, q, arr[202020];
int ans[1010101];
int res[202020];
int qnum = 0;
struct query {
int time, idx, ord;
bool operator<(const query &other) const {
if (time == other.time) return idx < other.idx;
return time > other.time;
}
} queries[1010101];
struct segment {
int first, st, ed, sz;
bool operator<(const segment &other) const {
return first > other.first;
}
};
set<segment> segs;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= q; i++) {
cin >> queries[i].time >> queries[i].idx;
queries[i].ord = i;
}
sort(queries + 1, queries + q + 1);
while (1) {
if (queries[qnum].time > 0) break;
ans[queries[qnum].ord] = arr[queries[qnum].idx];
qnum++;
}
int v = arr[1], s = 1;
for (int i = 2; i <= n/2; i++) {
if (v < arr[i]) {
segs.insert({v, s, i - 1, i - s});
v = arr[i];
s = i;
}
}
segs.insert({v, s, n/2, n/2 - s + 1});
v = arr[n/2 + 1], s = n/2 + 1;
for (int i = n/2 + 2; i <= n; i++) {
if (v < arr[i]) {
segs.insert({v, s, i - 1, i - s});
v = arr[i];
s = i;
}
}
segs.insert({v, s, n, n - s + 1});
int cnt = 0, p = n;
for (int t = 1; t <= queries[q].time; t++) {
if (queries[qnum].time == t) {
for (set<segment>::iterator iter = segs.begin(); iter != segs.end(); iter++) {
for (int i = iter->ed; i >= iter->st; i--) {
res[p--] = arr[i];
}
}
}
while (1) {
if (queries[qnum].time != t) break;
ans[queries[qnum].ord] = res[queries[qnum].idx];
qnum++;
}
while (1) {
if (cnt + segs.begin()->sz > n/2) break;
cnt += segs.begin()->sz;
for (int i = segs.begin()->ed; i >= segs.begin()->st; i--) {
res[p--] = arr[i];
}
segs.erase(segs.begin());
}
if (cnt == n/2) continue;
segment div = *segs.begin();
segs.erase(segs.begin());
segs.insert({div.first, div.st, div.st + cnt + div.sz - n/2 - 1, cnt + div.sz - n/2});
s = div.st + cnt + div.sz - n/2; v = arr[s];
for (int i = s; i <= div.ed; i++) {
if (v < arr[i]) {
segs.insert({v, s, i - 1, i - s});
v = arr[i];
s = i;
}
}
segs.insert({v, s, div.ed, div.ed - s + 1});
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
13992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
13336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
1992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
13992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
