Submission #1226275

#TimeUsernameProblemLanguageResultExecution timeMemory
1226275slivajanAbracadabra (CEOI22_abracadabra)C++20
10 / 100
3095 ms36412 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 vel; vuc zac; vuc A; pair<un, un> dostat_pozicy(un i){ i++; un prefSum = 0; un ptr = 0; while (prefSum + vel[ptr] < i) { prefSum += vel[ptr++]; } return {ptr, i - prefSum - 1}; } un dostat(un i){ auto [a, b] = dostat_pozicy(i); return A[zac[a] + b]; } bool doStep(){ auto [a, b] = dostat_pozicy(N/2); if (b == 0) return true; un nej = -1; REP(i, zac[a]+b, zac[a]+vel[a]){ if (A[i] > nej) nej = A[i]; vel[nej]++; } vel[a] = b; return false; } int main(){ un Q; cin >> N >> Q; A = vuc(N); FEAC(a, A) cin >> a; FEAC(a, A) a--; vel = vuc(N, 0); 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 nej = -1; REP(i, 0, N){ zac[A[i]] = i; if (A[i] > nej) nej = A[i]; vel[nej]++; } 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++; 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...