#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int a[200005];
int ans[200005];
struct info {
int val, l, r;
bool operator<(info o) const {
return val < o.val;
}
};
set<info> st;
int tree[4 * 200005];
void update(int x, int l, int r, int p, int v) {
if (l == r) {
tree[x] += v;
return;
}
int mid = (l + r) / 2;
if (p <= mid) update(2 * x, l, mid, p, v);
else update(2 * x + 1, mid + 1, r, p, v);
tree[x] = tree[2 * x] + tree[2 * x + 1];
}
int walk(int x, int l, int r, int v) {
if (l == r) return l;
int mid = (l + r) / 2;
if (tree[2 * x] >= v) return walk(2 * x, l, mid, v);
else return walk(2 *x + 1, mid + 1, r, v- tree[2 * x]);
}
int sum(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[x];
if (l > qr || ql > r) return 0;
int mid = (l + r) / 2;
return sum(2 * x, l, mid, ql, qr) + sum(2 * x + 1, mid + 1, r, ql, qr);
}
void add(int val, int l, int r) {
st.insert({val, l, r});
update(1, 1, 200000, val, r - l + 1);
}
void del(int val, int l, int r) {
st.erase({val, l, r});
update(1, 1, 200000, val, -(r - l + 1));
}
int rev[200005];
map<int, vector<pair<int, int>>> queries;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
return 0;
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
rev[a[i]] = i;
}
for (int i = 0; i < q; i++) {
int t, j; cin >> t >> j;
if (t == 0) {
ans[i] = a[j];
} else queries[min(t, n)].emplace_back(pair{i, j});
}
vector<int> big(n + 1, n + 1);
stack<int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.top()] < a[i]) {
big[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
for (int i = 1; i <= n; ) {
add(a[i], i, big[i] - 1);
i = big[i];
}
for (int i = 1; i <= n; i++) {
int idx = walk(1, 1, 200000, n / 2 + 1);
// index of first on RHS
if (sum(1, 1, 200000, 1, idx - 1) < n / 2) {
// need update then
// segment to remove
auto seg = *st.lower_bound({idx, 0, 0});
int lastidx = seg.l + (n / 2 - sum(1, 1, 200000, 1, idx - 1)) - 1;
add(seg.val, seg.l, lastidx);
del(seg.val, seg.l, seg.r);
lastidx++;
while (big[lastidx] <= seg.r) {
add(a[lastidx], lastidx, big[lastidx] - 1);
lastidx = big[lastidx];
}
add(a[lastidx], lastidx, seg.r);
}
for (auto [idx, v] : queries[i]) {
int curidx = walk(1, 1, 200000, v);
int have = sum(1, 1, 200000, 1, curidx - 1);
int delta = v - have - 1;
ans[idx] = a[rev[curidx] + delta];
}
}
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
