Submission #1007422

#TimeUsernameProblemLanguageResultExecution timeMemory
1007422aykhnAbracadabra (CEOI22_abracadabra)C++17
100 / 100
588 ms41940 KiB
#include <bits/stdc++.h> using namespace std; #define inf 0x3F3F3F3F const int MXN = 2e5 + 5; int n; int a[MXN]; int st[MXN << 2]; int nxt[MXN], ind[MXN]; void make(int l, int r, int x, int ind, int val) { if (l == r) { st[x] = val; return; } int mid = (l + r) >> 1; if (ind <= mid) make(l, mid, 2*x, ind, val); else make(mid + 1, r, 2*x + 1, ind, val); st[x] = st[2*x] + st[2*x + 1]; } int get(int l, int r, int x, int lx, int rx) { if (lx > rx) return 0; if (l > rx || r < lx) return 0; if (l >= lx && r <= rx) return st[x]; int mid = (l + r) >> 1; return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx); } int findval(int l, int r, int x, int lx, int rx, int val) { if (lx > rx) return -1; if (l > rx || r < lx) return -1; if (l >= lx && r <= rx && st[x] < val) return -1; if (l == r) return l; int mid = (l + r) >> 1; int A = findval(l, mid, 2*x, lx, rx, val); if (A == -1) return findval(mid + 1, r, 2*x + 1, lx, rx, val - st[2*x]); else return A; } int getind(int i) { int x = findval(1, n, 1, 1, n, i); int ext = i - get(1, n, 1, 1, x - 1); return ind[x] + ext - 1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int Q; cin >> n >> Q; for (int i = 1; i <= n; i++) { cin >> a[i]; ind[a[i]] = i; } vector<int> v; for (int i = n; i >= 1; i--) { while (!v.empty() && a[v.back()] < a[i]) v.pop_back(); nxt[i] = (v.empty() ? n + 1 : v.back()); v.push_back(i); } int cur = 1; while (cur < n + 1) { make(1, n, 1, a[cur], nxt[cur] - cur); cur = nxt[cur]; } array<int, 3> q[Q]; for (int i = 0; i < Q; i++) { cin >> q[i][0] >> q[i][1]; q[i][2] = i; } sort(q, q + Q); int ans[Q]; int j = 0, f = 1; for (array<int, 3> &i : q) { while (f && j < i[0]) { int m = findval(1, n, 1, 1, n, n / 2); if (get(1, n, 1, 1, m) == n / 2) { f = 0; break; } int cur = getind(n / 2 + 1); int tmp = cur; while (cur < nxt[ind[m]]) { nxt[cur] = min(nxt[cur], nxt[ind[m]]); make(1, n, 1, a[cur], nxt[cur] - cur); cur = nxt[cur]; } nxt[ind[m]] = tmp; make(1, n, 1, m, nxt[ind[m]] - ind[m]); j++; } ans[i[2]] = a[getind(i[1])]; } for (int i = 0; i < Q; i++) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...