Submission #739646

#TimeUsernameProblemLanguageResultExecution timeMemory
739646danikoynovAbracadabra (CEOI22_abracadabra)C++14
40 / 100
710 ms48368 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 2e5 + 10, maxq = 1e6 + 10; int n, q, a[maxn], ans[maxq], nxt_pos[maxn], nxt_val[maxn]; vector < pair < int, int > > ask[maxn]; void shuffle_array() { deque < int > d1, d2; for (int i = 1; i <= n / 2; i ++) d1.push_back(a[i]); for (int i = n / 2 + 1; i <= n; i ++) d2.push_back(a[i]); deque < int > res; while(!d1.empty() && !d2.empty()) { if (d1.front() < d2.front()) { res.push_back(d1.front()); d1.pop_front(); } else { res.push_back(d2.front()); d2.pop_front(); } } while(!d1.empty()) { res.push_back(d1.front()); d1.pop_front(); } while(!d2.empty()) { res.push_back(d2.front()); d2.pop_front(); } for (int i = 1; i <= n; i ++) a[i] = res[i - 1]; } struct block { int val, left, right; block(int _val, int _left, int _right) { val = _val; left = _left; right = _right; } bool operator < (const block &bk) const { return val < bk.val; } }; set < block > act; int fin[maxn], to, sz; void shuffle_smart() { while(true) { block cur = *act.rbegin(); if (sz - (cur.right - cur.left + 1) + 1 > n / 2) { ///cout << "remove " << sz << " " << cur.left << " " << cur.right << endl; for (int i = cur.right; i >= cur.left; i --) fin[to --] = a[i]; act.erase(cur); sz -= (cur.right - cur.left + 1); } else { break; } } if (sz == n / 2) return; /** for (block cur : act) { cout << "here " << cur.val << " " << cur.left << " " << cur.right << endl; }*/ block cur = *act.rbegin(); act.erase(cur); block fr = cur; fr.right = cur.right - (sz - n / 2); act.insert(fr); int idx = cur.right - (sz - n / 2) + 1, svd = idx; int sum_size = 0; //cout << idx << " : " << cur.right << endl; while(idx <= cur.right) { int gt = nxt_pos[idx]; gt = min(gt, cur.right + 1); sum_size += (gt - idx); act.insert(block(a[idx], idx, gt - 1)); ///cout << idx << " -- " << gt << " " << sum_size << endl; idx = gt; } /**if (sum_size != (sz - n / 2)) { cout << "wtf " << (sz - n / 2) << " "<< sum_size << endl; for (block cur : act) { cout << "here " << cur.val << " " << cur.left << " " << cur.right << " " << svd << endl; } }*/ // cout << "------------" << endl; } void solve() { cin >> n >> q; for (int i = 1; i <= n; i ++) { cin >> a[i]; } int tp = 0; for (int i = 1; i <= q; i ++) { int t, v; cin >> t >> v; t = min(t, n); tp = t; if (t == 0) ans[i] = a[v]; else ask[t].push_back({v, i}); } shuffle_array(); /**for (int i = 1; i <= n; i ++) cout << a[i] << " "; cout << endl;*/ stack < int > st; for (int i = 1; i <= n; i ++) { while(!st.empty() && a[st.top()] < a[i]) { nxt_pos[st.top()] = i; st.pop(); } st.push(i); } while(!st.empty()) { nxt_pos[st.top()] = n + 1; st.pop(); } int i = 1; while(i <= n) { act.insert(block(a[i], i, nxt_pos[i] - 1)); i = nxt_pos[i]; } to = n; sz = n; for (int f = 1; f < tp; f ++) { shuffle_smart(); } while(!act.empty()) { block cur = *act.rbegin(); ///cout << to << " " << sz << " " << (cur.right - cur.left + 1) << endl; for (int i = cur.right; i >= cur.left; i --) fin[to --] = a[i]; act.erase(cur); sz -= (cur.right - cur.left + 1); } for (pair < int, int > cur : ask[tp]) ans[cur.second] = fin[cur.first]; for (int i = 1; i <= q; i ++) cout << ans[i] << endl; } int main() { ///speed(); //freopen("test.txt", "r", stdin); ///freopen("output.txt", "w", stdout); solve(); return 0; } /** 10 0 3 8 2 4 9 5 10 1 6 7 */

Compilation message (stderr)

Main.cpp: In function 'void shuffle_smart()':
Main.cpp:114:45: warning: unused variable 'svd' [-Wunused-variable]
  114 |     int idx = cur.right - (sz - n / 2) + 1, svd = idx;
      |                                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...