// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using vi = V<int>;
const int INF = 1e9;
struct BIT {
vi A; int N; void init(int n) { N = n; A = vi(N, 0); }
void upd(int p, int x) { for(++p;p<=N;p+=p&-p) A[p - 1] += x; }
int sum(int r) { int s = 0; for(;r;r-=r&-r) s += A[r - 1]; return s; }
int sum(int l, int r) { return sum(r + 1) - sum(l); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >> Q;
vi A(N); for(auto& x : A) { cin >> x; --x; }
vi pos(N), nxt(N), mx(N), stk = {N};
for(int i = 0; i < N; i++) pos[A[i]] = i;
for(int i = 0; i < N / 2; i++) mx[i] = max(A[i], i != 0 ? mx[i - 1] : -INF); // first half
for(int i = N / 2; i < N; i++) mx[i] = max(A[i], i != N / 2 ? mx[i - 1] : -INF); // second half
for(int i = N - 1; i >= 0; i--) {
while(stk.back() != N && A[stk.back()] < A[i]) stk.pop_back();
nxt[i] = stk.back();
stk.pb(i);
}
V<AR<int, 3>> qry; vi ans(Q);
for(int q = 0; q < Q; q++) {
int t, i; cin >> t >> i; --i;
if (t) qry.pb(AR<int, 3>{t, i, q});
else ans[q] = A[i] + 1;
}
Q = sz(qry);
BIT B; B.init(N);
for(int i = 0; i < N; i++) B.upd(mx[i], 1);
auto find = [&](int x) {
int lo = 0, hi = N - 1;
while(lo < hi) {
int mid = (lo + hi) / 2;
if (B.sum(0, mid) >= x) hi = mid;
else lo = mid + 1;
}
return lo;
};
auto answer = [&](int x, int i) {
int rep = find(x + 1);
int idx = pos[rep] + (x - B.sum(0, rep - 1));
ans[i] = A[idx] + 1;
};
sort(begin(qry), end(qry));
int t = 1, q = 0;
while(q < Q) {
// cout << t << endl;
// for(int i = 0; i < N; i++) cout << i << " => " << B.sum(i, i) << endl;
// cout << endl;
while(q < Q && qry[q][0] <= t) {
answer(qry[q][1], qry[q][2]); q++;
}
int mid = find(N / 2);
int ex = B.sum(0, mid) - N / 2, bnd = B.sum(0, mid); B.upd(mid, -ex);
if (ex == 0) {
t = INF; continue;
}
int x = pos[mid] + B.sum(mid, mid);
while(x <= bnd) {
int nxtx = nxt[x];
int amt = nxtx - x; B.upd(A[x], amt);
x = nxtx;
}
++t;
}
for(auto& x : ans) cout << x << nl;
exit(0-0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
362 ms |
27780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
501 ms |
41392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
6084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
362 ms |
27780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
