Submission #656789

#TimeUsernameProblemLanguageResultExecution timeMemory
656789TheEvilBirdCollider (IZhO11_collider)C++17
100 / 100
356 ms2628 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)((x).size()) typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; //typedef __int128_t int128; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const char en = '\n'; const int INF = 1e9 + 7; const ll INFLL = 1e18; //mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937 rnd(1); #ifdef __APPLE__ #include "debug.h" //#define debug(...) 42 #else #define debug(...) 42 #endif struct Node { int val; int prior; int size; Node *l, *r; Node() = default; Node(int _val) : val(_val), prior(rnd()), size(1), l(nullptr), r(nullptr) {} }; typedef Node* pnode; int get_size(pnode root) { return (root == nullptr ? 0 : root->size); } void update(pnode root) { if (root == nullptr) { return; } root->size = 1 + get_size(root->l) + get_size(root->r); } pair<pnode, pnode> split(pnode root, int k) { if (root == nullptr) { return {nullptr, nullptr}; } int siz = get_size(root->l) + 1; if (siz <= k) { auto [l, r] = split(root->r, k - siz); root->r = l; update(root); return {root, r}; } else { auto [l, r] = split(root->l, k); root->l = r; update(root); return {l, root}; } } pnode merge(pnode l, pnode r) { if (l == nullptr) { return r; } if (r == nullptr) { return l; } if (l->prior > r->prior) { l->r = merge(l->r, r); update(l); return l; } else { r->l = merge(l, r->l); update(r); return r; } } void solve() { int n, q; string s; cin >> n >> q >> s; // pnode root = nullptr; // for (int i = 0; i < n; ++i) { // root = merge(root, new Node(s[i] - 'x')); // } for (int w = 0; w < q; ++w) { char t; cin >> t; if (t == 'a') { int i, j; cin >> i >> j; if (i == j) { continue; } string ss; --i; --j; char c = s[i]; s.erase(s.begin() + i); s.insert(s.begin() + j, c); // if (i < j) { // auto [L, R] = split(root, j - 1); // auto [l1, l2] = split(L, i - 1); // auto [x, l3] = split(l2, 1); // assert(x != nullptr); // root = merge(merge(merge(l1, l3), x), R); // } else { // auto [L, R] = split(root, i - 1); // auto [x, R1] = split(R, 1); // assert(x != nullptr); // auto [l1, l2] = split(L, j - 1); // root = merge(merge(merge(l1, x), l2), R1); // } } else { // t = 'q' int pos; cin >> pos; cout << s[pos - 1] << en; // auto [l, r] = split(root, pos); // auto [l1, m] = split(l, pos - 1); // assert(m != nullptr); // cout << (char)('x' + m->val) << en; // root = merge(merge(l1, m), r); } } } int main() { #ifdef __APPLE__ freopen("input.txt", "r", stdin); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...