#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int Q = 1e6 + 10;
int n, in[N], a[N], xi[N], yi[N], nxt[N], q, px = 1, py = 1, po[N], ans[Q];
array<int, 3> qry[Q];
struct SegTree {
int size = 1;
vector<int> seg;
void init(int _n) {
while (size < _n) size *= 2;
seg.assign(2 * size + 10, 0);
}
void update(int pos, int v, int l, int r, int id) {
if (l == r) {
seg[id] += v;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(pos, v, l, mid, id * 2);
else update(pos, v, mid + 1, r, id * 2 + 1);
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
int query(int ql, int qr, int l, int r, int id) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return seg[id];
int mid = (l + r) / 2;
return query(ql, qr, l, mid, id * 2) + query(ql, qr, mid + 1, r, id * 2 + 1);
}
int find(int l, int r, int sum, int id) {
if (l == r) return l;
int mid = (l + r) / 2;
if (seg[id * 2] >= sum) return find(l, mid, sum, id * 2);
else return find(mid + 1, r, sum - seg[id * 2], id * 2 + 1);
}
} ST;
int get_next(int value, int dist) {
return a[po[value] + dist];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> in[i];
if (i <= n / 2) xi[i] = in[i];
else yi[i - n / 2] = in[i];
}
for (int i = 1; i <= n; i++) {
if (px > n / 2) a[i] = yi[py++];
else if (py > n / 2) a[i] = xi[px++];
else if (xi[px] < yi[py]) a[i] = xi[px++];
else a[i] = yi[py++];
po[a[i]] = i;
}
stack<int> st;
for (int i = 1; i <= n; i++) nxt[i] = 1e9;
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
if (!st.empty()) nxt[i] = st.top() - i;
st.push(i);
}
// for (int i = 1; i <= n; i++) cout << nxt[i] << ' '; cout << '\n';
vector<pair<int, int>> piv;
for (int i = 1; i <= n; i++) {
if (piv.empty() || piv.back().first < a[i]) piv.push_back({a[i], 1});
else piv.back().second++;
}
for (int i = 1; i <= q; i++) {
cin >> qry[i][0] >> qry[i][1];
qry[i][2] = i;
}
sort(qry + 1, qry + q + 1, [] (auto x, auto y) {
return x[0] < y[0];
});
ST.init(n + 1);
for (auto& [pi, pj] : piv) ST.update(pi, pj, 1, n, 1);
int cur = 1;
bool firm = 0;
// for (int i = 1; i <= n; i++) cout << ST.query(i, i, 1, n, 1) << ' ';
// cout << '\n';
for (int i = 1; i <= q; i++) {
int t = qry[i][0], id = qry[i][1];
if (!t) {
ans[qry[i][2]] = in[id];
continue;
}
if (t == 1) {
ans[qry[i][2]] = a[id];
continue;
}
while (cur < t && !firm) {
int rt = ST.find(1, n, n / 2, 1);
int actl = ST.query(1, rt, 1, n, 1);
int pdist = ST.query(1, rt - 1, 1, n, 1);
if (actl == n / 2) {
firm = 1;
break;
}
int ex = actl - n / 2, elapsed = 0;
ST.update(rt, -ex, 1, n, 1);
while (ex > 0) {
int hd = get_next(rt, n / 2 + elapsed - pdist);
// cout << "hd: " << hd << '\n';
int len = min(nxt[po[hd]] - 1, ex);
// cout << "len: " << nxt[po[hd]] - 1 << " " << ex << '\n';
ST.update(hd, len + 1, 1, n, 1);
ex -= len + 1, elapsed += len + 1;
}
cur++;
// for (int j = 1; j <= n; j++) cout << ST.query(j, j, 1, n, 1) << ' ';
// cout << '\n';
}
int cutoff = ST.find(1, n, id, 1); // >=
int actl = ST.query(1, cutoff - 1, 1, n, 1);
int dista = id - actl - 1;
ans[qry[i][2]] = a[po[cutoff] + dista];
}
// for (int i = 1; i <= n; i++) cout << ST.query(i, i, 1, n, 1) << ' ';
// cout << '\n';
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
258 ms |
30592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
43532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
12872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
258 ms |
30592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
