Submission #996033

#TimeUsernameProblemLanguageResultExecution timeMemory
996033IBoryAbracadabra (CEOI22_abracadabra)C++17
0 / 100
230 ms36532 KiB
#include <bits/stdc++.h> #define pii pair<int, int> using namespace std; const int SZ = 1 << 18; int A[SZ], B[SZ], IB[SZ], ans[SZ]; struct Seg { int T[SZ << 1]; void Update(int i, int v) { T[i += SZ - 1] = v; while (i >>= 1) T[i] = T[i * 2] + T[i * 2 + 1]; } pii Query(int k) { int sL = 1, sR = SZ, n = 1; while (sL != sR) { int mid = (sL + sR) >> 1; if (k <= T[n * 2]) sR = mid, n = n * 2; else sL = mid + 1, k -= T[n * 2], n = n * 2 + 1; } return {sL, k}; } } T; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, Q; cin >> N >> Q; for (int i = 1; i <= N; ++i) cin >> A[i]; map<int, vector<pii>> P; for (int i = 1; i <= Q; ++i) { int a, b; cin >> a >> b; P[a].emplace_back(b, i); } if (P.count(0)) { for (auto [a, b] : P[0]) ans[b] = A[a]; } int a = 1, b = (N / 2) + 1, idx = 1; while (a <= N / 2 || b <= N) { if (N < b) B[idx++] = A[a++]; else if (N / 2 < a) B[idx++] = A[b++]; else B[idx++] = A[(A[a] < A[b] ? a : b)++]; } for (int i = 1; i <= N; ++i) IB[B[i]] = i; priority_queue<tuple<int, int, int>> PQ; int Z = N, l = 1; for (int i = 1; i <= N; ++i) { if (B[l] < B[i]) { PQ.emplace(B[l], l, i - 1); T.Update(B[l], i - l); l = i; } } PQ.emplace(B[l], l, N); T.Update(B[l], N + 1 - l); int turn = 1; while (1) { if (P.count(turn)) { for (auto [k, id] : P[turn]) { auto [p, off] = T.Query(k); ans[id] = B[IB[p] + off - 1]; } } tuple<int, int, int> last; while (N / 2 < Z) { last = PQ.top(); PQ.pop(); auto [_, a, b] = last; Z -= b - a + 1; } if (Z == N / 2) break; turn++; auto [v, a, b] = last; int m = a + (N / 2 - Z) - 1; PQ.emplace(v, a, m); PQ.emplace(B[m + 1], m + 1, b); T.Update(v, N / 2 - Z); T.Update(B[m + 1], b - m); Z += b - a + 1; } for (auto& [_, v] : P) for (auto [k, id] : v) { if (ans[id]) continue; auto [p, off] = T.Query(k); ans[id] = B[IB[p] + off - 1]; } for (int i = 1; i <= Q; ++i) cout << ans[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...