Submission #856007

#TimeUsernameProblemLanguageResultExecution timeMemory
856007PanndaAbracadabra (CEOI22_abracadabra)C++17
100 / 100
527 ms48224 KiB
#include <bits/stdc++.h> using namespace std; const int LOG = 20; struct Fenwick { int n; vector<int> bit; vector<int> a; Fenwick(int n) : n(n), bit(n + 1, 0), a(n, 0) {} void add(int i, int delta) { a[i] += delta; for (i++; i <= n; i += i & -i) { bit[i] += delta; } } int sum(int i) { int res = 0; for (; i > 0; i -= i & -i) { res += bit[i]; } return res; } int get(int i) { return a[i]; } int kth(int k) { int sum = 0; int cur = 0; for (int i = LOG - 1; i >= 0; i--) { if (cur + (1 << i) <= n && sum + bit[cur + (1 << i)] <= k) { cur += (1 << i); sum += bit[cur]; } } return cur; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> a(n), ia(n); vector<vector<array<int, 2>>> mp(n + 1); vector<int> ans(q); for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; ia[a[i]] = i; } for (int id = 0; id < q; id++) { int t, i; cin >> t >> i; i--; t = min(t, n); mp[t].push_back({ i, id }); } vector<int> dec; vector<int> f(n); for (int i = n - 1; i >= 0; i--) { while (!dec.empty() && a[i] > a[dec.back()]) { dec.pop_back(); } f[i] = dec.empty() ? n : dec.back(); dec.push_back(i); } Fenwick fen(n); for (int i = 0; i < n; i = f[i]) { fen.add(a[i], f[i] - i); } function<void()> cut = [&]() { int head = fen.kth(n / 2); int pos = fen.sum(head); int fromLen = fen.get(head); int toLen = n / 2 - pos; fen.add(head, -fromLen + toLen); int newHead = a[ia[head] + toLen]; int i = ia[newHead]; int k = n / 2; int bound = pos + fromLen; while (k + f[i] - i < bound) { fen.add(a[i], f[i] - i); k += f[i] - i; i = f[i]; } fen.add(a[i], bound - k); }; function<int(int)> kth = [&](int k) { int head = fen.kth(k); int pos = fen.sum(head); int delta = k - pos; return a[ia[head] + delta]; }; for (int t = 0; t <= n; t++) { for (auto [i, id] : mp[t]) { ans[id] = kth(i); } cut(); } for (auto x : ans) { cout << x + 1 << '\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...