Submission #698236

#TimeUsernameProblemLanguageResultExecution timeMemory
698236KahouAbracadabra (CEOI22_abracadabra)C++14
0 / 100
277 ms24948 KiB
/* In the name of God, aka Allah */ // Believe me - Takeshi Abo #include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 2e5 + 50, M = 1e6 + 50, LG = 20; int n, q, par[N], out[M]; vector<pii> vc[N]; int p[N], pp[N]; int fen[N]; void upd(int i, int x) { for (; i <= n; i += i&-i) fen[i] += x; } int get(int i) { int out = 0; for (; i > 0; i -= i&-i) out += fen[i]; return out; } int getpos(int x) { int pos = 0; for (int k = LG-1; k >= 0; k--) { if (pos+(1<<k) <= n && fen[pos+(1<<k)] < x) { pos ^= 1<<k; x -= fen[pos]; } } return pos+1; } void solve() { cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> p[i]; pp[p[i]] = i; } for (int i = 1; i <= q; i++) { int t, k; cin >> t >> k; t = min(t, n); vc[t].push_back({k, i}); } for (pii x:vc[0]) out[x.S] = p[x.F]; for (int i = n; i >= 1; i--) { par[i] = i+1; while (par[i] <= n && p[i] > p[par[i]]) { par[i] = par[par[i]]; } } int pt = 1; while (pt <= n/2) { upd(p[pt], min(n/2+1, par[pt])-pt); pt = par[pt]; } pt = n/2+1; while (pt <= n) { upd(p[pt], par[pt]-pt); pt = par[pt]; } for (int tt = 1; tt <= n; tt++) { for (pii x:vc[tt]) { int id = getpos(x.F); out[x.S] = p[x.F-get(id-1)+pp[id]-1]; } int id = getpos(n/2); if (get(id) <= n/2) continue; int pt = n/2-get(id-1)+pp[id]; int ft = get(id)-get(id-1)+pp[id]-1; upd(id, n/2-get(id)); while (pt <= ft) { upd(p[pt], par[pt]-pt); pt = par[pt]; } } for (int i = 1; i <= q; i++) { cout << out[i] << endl; } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); 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...