#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 2e5 + 25;
array <int, 3> v[MAXN << 2];
const int MAXQ = 1e6 + 25;
int n, q;
array <int, 3> queries[MAXQ];
int a[MAXN], nxt[MAXN];
int cnt = 0;
int ans[MAXQ];
int get (array <int, 3> z) {
return lower_bound(v + 1, v + cnt + 1, z) - v;
}
struct SegmentTree {
int tree[MAXN << 3];
void update (int l, int r, int a, int b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] += b;
return;
}
update(l, mid, a, b, tl); update(mid + 1, r, a, b, tr);
tree[node] = tree[tl] + tree[tr];
}
int get (int l, int r, int a, int node) {
if (l == r) return l;
if (tree[tl] >= a) return get(l, mid, a, tl);
return get(mid + 1, r, a - tree[tl], tr);
}
int query (int l, int r, int a, int b, int node) {
if (a > b) return 0;
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
return query(l, mid, a, b, tl) + query(mid + 1, r, a, b, tr);
}
} cur;
void ins (array <int, 3> x) {
int z = get(x);
cur.update(1, cnt, z, x[2] - x[1] + 1, 1);
}
void rem (array <int, 3> x) {
int z = get(x);
cur.update(1, cnt, z, -(x[2] - x[1] + 1), 1);
}
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
stack <int> cur2;
for (int i = 1; i <= n; i++) {
while (!cur2.empty() && a[cur2.top()] < a[i]) {
nxt[cur2.top()] = i;
cur2.pop();
}
cur2.push(i);
}
for (int i = 1; i <= q; i++) {
cin >> queries[i][0] >> queries[i][1]; queries[i][2] = i;
queries[i][0] = min(queries[i][0], n);
}
sort(queries + 1, queries + q + 1);
int sum = 0;
priority_queue <array <int, 3>> pq;
for (int i = 1; i != 0; i = nxt[i]) {
if (nxt[i] == 0) pq.push({a[i], i, n}), v[++cnt] = {a[i], i, n};
else pq.push({a[i], i, nxt[i] - 1}), v[++cnt] = {a[i], i, nxt[i] - 1};
}
int cnttt = 0;
while (!pq.empty()) {
if (sum == n / 2) break;
auto z = pq.top(); pq.pop();
cnttt++;
if (cnttt == 10) break;
if (sum + z[2] - z[1] + 1 <= n / 2) {
sum += z[2] - z[1] + 1; continue;
}
int s = n / 2 - sum, l = z[2] - z[1] + 1;
int dd = l - s;
pq.push({a[z[1]], z[1], z[1] + dd - 1}); v[++cnt] = {a[z[1]], z[1], z[1] + dd - 1};
z[1] += dd;
for (int i = z[1]; i && i <= z[2]; i = nxt[i]) {
if (nxt[i]) {
pq.push({a[i], i, min(nxt[i] - 1, z[2])}); v[++cnt] = {a[i], i, min(nxt[i] - 1, z[2])};
} else {
pq.push({a[i], i, z[2]}); v[++cnt] = {a[i], i, z[2]};
}
}
}
sort(v + 1, v + cnt + 1);
while (!pq.empty()) pq.pop();
sum = 0;
for (int i = 1; i != 0; i = nxt[i]) {
if (nxt[i] == 0) pq.push({a[i], i, n}), ins({a[i], i, n});
else pq.push({a[i], i, nxt[i] - 1}), ins({a[i], i, nxt[i] - 1});
}
int ptr = 1;
while (ptr <= q && queries[ptr][0] == 0) {
int u = cur.get(1, cnt, queries[ptr][1], 1);
int g = queries[ptr][1] - cur.query(1, cnt, 1, u - 1, 1);
ans[queries[ptr][2]] = v[u][1] + g - 1;
ptr++;
}
for (int i = 1; i <= n; i++) {
while (!pq.empty()) {
if (sum == n / 2) break;
auto z = pq.top(); pq.pop();
if (sum + z[2] - z[1] + 1 <= n / 2) {
sum += z[2] - z[1] + 1; continue;
}
rem(z);
int s = n / 2 - sum, l = z[2] - z[1] + 1;
int dd = l - s;
pq.push({a[z[1]], z[1], z[1] + dd - 1}); ins({a[z[1]], z[1], z[1] + dd - 1});
z[1] += dd;
for (int i = z[1]; i && i <= z[2]; i = nxt[i]) {
if (nxt[i]) {
pq.push({a[i], i, min(nxt[i] - 1, z[2])}); ins({a[i], i, min(nxt[i] - 1, z[2])});
} else {
pq.push({a[i], i, z[2]}); ins({a[i], i, z[2]});
}
}
break;
}
while (ptr <= q && queries[ptr][0] == i) {
int u = cur.get(1, cnt, queries[ptr][1], 1);
int g = queries[ptr][1] - cur.query(1, cnt, 1, u - 1, 1);
ans[queries[ptr][2]] = v[u][1] + g - 1;
ptr++;
}
}
for (int i = 1; i <= q; i++) cout << a[ans[i]] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
289 ms |
32456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
43456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
15820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
289 ms |
32456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
