Submission #754573

#TimeUsernameProblemLanguageResultExecution timeMemory
754573MilosMilutinovicCollider (IZhO11_collider)C++14
0 / 100
1 ms212 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); printf("%c", 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) j--; Node *a, *b; Split(root, a, b, i - 1); Node *c, *d; Split(b, c, d, 1); Merge(root, a, d); Split(root, a, b, j - 1); Merge(d, a, c); Merge(root, d, b); } else { int i; cin >> i; cout << Query(i) << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...