Submission #754582

#TimeUsernameProblemLanguageResultExecution timeMemory
754582MilosMilutinovicCollider (IZhO11_collider)C++14
100 / 100
171 ms49400 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(time(0)); struct Node { char val; int prior; int sz; Node *left; Node *right; Node(char c) { val = c; prior = rng(); sz = 1; left = nullptr; right = nullptr; } } *root; int get_sz(Node *nd) { return nd == nullptr ? 0 : nd->sz; } void upd(Node *&nd) { nd->sz = get_sz(nd->left) + get_sz(nd->right) + 1; } void Merge(Node *&treap, Node *left, Node *right) { if (left == nullptr) { treap = right; return; } if (right == nullptr) { treap = left; return; } if (left->prior < right->prior) { Merge(left->right, left->right, right); treap = left; } else { Merge(right->left, left, right->left); treap = right; } upd(treap); } void Split(Node *treap, Node *&left, Node *&right, int val) { if (treap == nullptr) { left = nullptr; right = nullptr; return; } if (get_sz(treap->left) < val) { Split(treap->right, treap->right, right, val - get_sz(treap->left) - 1); left = treap; } else { Split(treap->left, left, treap->left, val); right = treap; } upd(treap); } void dfs(Node *nd) { if (nd == nullptr) return; dfs(nd->left); cout << nd->val; dfs(nd->right); } const int N = 1e6 + 10; int n, q; string s; char Query(int idx) { Node *a, *b; Split(root, a, b, idx - 1); Node *c, *d; Split(b, c, d, 1); char res = c->val; Merge(b, c, d); Merge(root, a, b); return res; } int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cin >> n >> q; cin >> s; for (int i = 0; i < n; i++) { Merge(root, root, new Node(s[i])); } while (q--) { char c; cin >> c; if (c == 'a') { int i, j; cin >> i >> j; if (i == j) { continue; } if (i < j) { Node *pre_i, *od_i; Split(root, pre_i, od_i, i - 1); Node *na_i, *posle_i; Split(od_i, na_i, posle_i, 1); Node *do_j, *posle_j; Split(posle_i, do_j, posle_j, j - i); Node *a, *b; Merge(a, pre_i, do_j); Merge(b, a, na_i); Merge(root, b, posle_j); } else { Node *pre_j, *od_j; Split(root, pre_j, od_j, j - 1); Node *pre_i, *od_i; Split(od_j, pre_i, od_i, i - j); Node *na_i, *posle_i; Split(od_i, na_i, posle_i, 1); Node *a, *b; Merge(a, pre_j, na_i); Merge(b, a, pre_i); Merge(root, b, posle_i); } } else { int i; cin >> i; cout << Query(i) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...