Submission #656810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
656810	2022-11-08T08:55:43 Z	TheEvilBird	Collider (IZhO11_collider)	C++17	100 / 100	195 ms	48264 KB

collider

#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;
            }
            auto [l, r] = split(root, i - 1);
            auto [x, rx] = split(r, 1);
            auto cur = merge(l, rx);
            auto [l1, r1] = split(cur, j - 1);
            root = merge(merge(l1, x), r1);
        } else { // t = 'q'
            int pos;
            cin >> pos;
            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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	10 ms	380 KB	Output is correct
3	Correct	21 ms	5112 KB	Output is correct
4	Correct	130 ms	38580 KB	Output is correct
5	Correct	130 ms	38576 KB	Output is correct
6	Correct	156 ms	43464 KB	Output is correct
7	Correct	167 ms	48256 KB	Output is correct
8	Correct	145 ms	48144 KB	Output is correct
9	Correct	195 ms	48232 KB	Output is correct
10	Correct	181 ms	48264 KB	Output is correct