Submission #1226311

#TimeUsernameProblemLanguageResultExecution timeMemory
1226311slivajanAbracadabra (CEOI22_abracadabra)C++20
35 / 100
3097 ms49260 KiB
#include <bits/stdc++.h> using namespace std; using un = long long; using vuc = vector<un>; using vol = vector<bool>; #define REP(i, a, b) for (un i = (un)a; i < (un)b; i++) #define FEAC(i, a) for (auto&& i : a) #define vec vector #define ALL(x) (x).begin(), (x).end() un N; vuc zac; vuc A; vuc vel_iv; un M; void init_iv(){ M = N; while(M&(M-1)) M++; vel_iv = vuc(2*M); } un get_iv(un i) {return vel_iv[M+i];} void set_iv(un i, un v){ i += M; vel_iv[i] = v; i/= 2; while(i > 0) { vel_iv[i] = vel_iv[2*i] + vel_iv[2*i + 1]; i /= 2; } } pair<un, un> dostat_pozicy(un i){ i++; un ptr = 1; while(ptr < M){ if (i <= vel_iv[2*ptr]) { ptr = 2*ptr; } else{ i -= vel_iv[2*ptr]; ptr = 2*ptr + 1; } } return {ptr-M, i-1}; } unordered_map<un, un> cache; un dostat(un i){ if (cache.find(i) == cache.end()){ auto [a, b] = dostat_pozicy(i); cache[i] = A[zac[a] + b]; } return cache[i]; } bool doStep(){ auto [a, b] = dostat_pozicy(N/2); if (b == 0) return true; un nej = -1; un val = 0; REP(i, zac[a]+b, zac[a]+get_iv(a)){ if (A[i] > nej){ if (nej != -1) set_iv(nej, val); nej = A[i]; val = 0; } val++; } set_iv(nej, val); set_iv(a, b); return false; } int main(){ un Q; cin >> N >> Q; init_iv(); A = vuc(N); FEAC(a, A) cin >> a; FEAC(a, A) a--; zac = vuc(N, -1); vec<tuple<un, un, un>> queries; REP(i, 0, Q){ un a, b; cin >> a >> b; b--; queries.emplace_back(a, b, i); } sort(ALL(queries)); un val = 0; un nej = -1; REP(i, 0, N){ zac[A[i]] = i; if (A[i] > nej){ if(nej != -1) set_iv(nej, val); nej = A[i]; val = 0; } val++; } set_iv(nej, val); vuc rets(Q, -1); un qIndex = 0; un t = 0; while(qIndex < Q){ while((qIndex < Q) and (get<0>(queries[qIndex]) == t)){ auto [ignore, i, j] = queries[qIndex]; rets[j] = dostat(i); qIndex++; } bool hotovo = doStep(); t++; cache = unordered_map<un, un>(); if (hotovo) break; } while(qIndex < Q){ auto [ignore, i, j] = queries[qIndex]; rets[j] = dostat(i); qIndex++; } FEAC(ret, rets) cout << ret+1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...