#include <bits/stdc++.h>
using namespace std;
#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int x) {
n = x;
tree.resize(n + 1, 0);
}
void add(int k, int x) {
for (int i = k + 1; i <= n; i += (i & (-i))) {
tree[i] += x;
}
}
int pref(int r) {
int sum = 0;
for (int i = r; i > 0; i -= (i & (-i))) {
sum += tree[i];
}
return sum;
}
int quer(int l, int r) {
return pref(r + 1) - pref(l);
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n), at(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
at[a[i]] = i;
}
vector<int> nl(n);
stack<int> sta;
for (int i = n - 1; i >= 0; i--) {
while (!sta.empty() && a[sta.top()] < a[i]) {
sta.pop();
}
if (sta.empty()) {
nl[i] = n;
} else {
nl[i] = sta.top();
}
sta.push(i);
}
parr(nl);
vector<array<int, 3>> quer(q);
for (int i = 0; i < q; i++) {
cin >> quer[i][0] >> quer[i][1];
quer[i][1]--;
quer[i][2] = i;
}
sort(quer.begin(), quer.end());
vector<int> ans(q);
vector<int> sz(n, 0);
int pmx = -1;
for (int i = 0; i < n / 2; i++) {
if (a[i] > pmx) {
pmx = a[i];
}
sz[pmx]++;
}
pmx = -1;
for (int i = n / 2; i < n; i++) {
if (a[i] > pmx) {
pmx = a[i];
}
sz[pmx]++;
}
FenwickTree fenw(n);
for (int i = 0; i < n; i++) {
fenw.add(i, sz[i]);
}
int ptr = 0; bool done = false;
while (ptr < q && quer[ptr][0] == 0) {
ans[quer[ptr][2]] = a[quer[ptr][1]];
ptr++;
}
parr(sz);
for (int it = 1; ptr < q; it++) {
// perform updates
int l = 0, r = n - 1;
while (r > l) {
int m = (l + r) / 2;
if (fenw.quer(0, m) >= n / 2) {
r = m;
} else {
l = m + 1;
}
}
int k = r;
int cnt = fenw.quer(0, k), prev = fenw.quer(0, k - 1);
if (cnt == n / 2) {
done = true;
}
while (ptr < q && (done == true || quer[ptr][0] == it)) {
parr(quer[ptr]);
l = 0, r = n - 1;
while (r > l) {
int m = (l + r) / 2;
if (fenw.quer(0, m) >= quer[ptr][1] + 1) {
r = m;
} else {
l = m + 1;
}
}
pv(l);
int prv = fenw.quer(0, l - 1);
pv(prv);
ans[quer[ptr][2]] = a[at[l] + quer[ptr][1] - prv];
pv(ans[quer[ptr][2]] + 1);
// find the quer[ptr][1]th elem in the array
ptr++;
}
if (done) break;
fenw.add(k, -(cnt - n / 2));
for (int i = at[k] + n / 2 - prev; i < at[k] + cnt - prev; i = nl[i]) {
fenw.add(a[i], nl[i] - i);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] + 1 << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
378 ms |
27548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
474 ms |
39508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
6224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
378 ms |
27548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
