Submission #784661

#TimeUsernameProblemLanguageResultExecution timeMemory
784661boris_mihovAbracadabra (CEOI22_abracadabra)C++17
0 / 100
3090 ms33996 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <cstring> #include <vector> #include <cmath> #include <stack> typedef long long llong; const int MAXN = 200000 + 10; const int MAXQ = 1000000 + 10; const llong INF = 1e18; const int INTINF = 1e9; int n, q; int total; int a[MAXN]; int b[MAXN]; int output[MAXQ]; std::vector <std::pair <int,int>> v[MAXN]; void riffle() { int pos = 1; int lPtr = 1, rPtr = n / 2 + 1; while (lPtr < n / 2 + 1 || rPtr < n + 1) { if (lPtr == n / 2 + 1) { b[pos++] = a[rPtr++]; total = std::max(total, pos); continue; } if (rPtr == n + 1) { b[pos++] = a[lPtr++]; continue; } if (a[lPtr] < a[rPtr]) { b[pos++] = a[lPtr++]; } else { b[pos++] = a[rPtr++]; total = std::max(total, pos); } } for (int i = 1 ; i <= n ; ++i) { a[i] = b[i]; } } void solve() { int bucketSize = sqrt(n) + 5; for (int i = 0 ; i <= bucketSize ; ++i) { for (const auto &[pos, idx] : v[i]) { output[idx] = a[pos]; } riffle(); } total = 0; for (int i = bucketSize + 1 ; i <= n ; ++i) { for (const auto &[pos, idx] : v[i]) { output[idx] = a[pos]; } riffle(); } assert(total <= bucketSize); } void print() { for (int i = 1 ; i <= q ; ++i) { std::cout << output[i] << '\n'; } } void input() { std::cin >> n >> q; for (int i = 1 ; i <= n ; ++i) { std::cin >> a[i]; } for (int i = 1 ; i <= q ; ++i) { int t, idx; std::cin >> t >> idx; v[std::min(t, (int)sqrt(n))].push_back({idx, i}); } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); print(); 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...