Submission #1290131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290131		MinhKien	Collider (IZhO11_collider)	C++20	0 / 100	0 ms	332 KiB

collider

#include <iostream>
#include <string>
#include <chrono>
#include <random>

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution <int> dis(1, (int)2e9);

struct treap {
    char val;
    int sz, prior;
    treap *l, *r;

    treap () {}
    treap (char v) {
        val = v;
        sz = 1;
        prior = dis(rnd);
        l = r = nullptr;
    }
};

int sz(treap *t) {
    return (t ? t->sz : 0);
}

void pull(treap *t) {
    if (!t) return;
    t->sz = sz(t->l) + sz(t->r) + 1;
}

void heapify(treap *t) {
    if (!t) return;

    treap *mx = t;
    if (t->l && t->l->prior > mx->prior) mx = t->l;
    if (t->r && t->r->prior > mx->prior) mx = t->r;

    if (mx != t) {
        swap(t->prior, mx->prior);
        heapify(mx);
    }
}

int n, q;
string s;

treap *build(int x, int k) {
    if (k == 0) return nullptr;

    int m = k >> 1;
    treap *t = new treap(s[x + m]);
    t->l = build(x, m);
    t->r = build(x + m + 1, k - m - 1);
    heapify(t);
    pull(t);

    return t;
}

#define tt pair <treap *, treap *>
tt split(treap *t, int k) {
    tt p = tt(nullptr, nullptr);
    
    if (!t) return p;

    if (sz(t->l) >= k) {
        p = split(t->l, k);
        t->l = p.second;
        pull(t);
        p.second = t;
    } else {
        p = split(t->r, k - sz(t->l) - 1);
        t->r = p.first;
        pull(t);
        p.first = t;
    }

    return p;
}

treap *merge(treap *L, treap *R) {
    if (!L || !R) return (L ? L : R);

    if (L->prior < R->prior) {
        L->r = merge(L->r, R);
        pull(L);
        return L;
    } else {
        R->l = merge(L, R->l);
        pull(R);
        return R;
    }
}

treap *root;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> q >> s;

    root = build(0, n);

    char type;
    int x, y;

    while (q--) {
        cin >> type;

        if (type == 'a') {
            cin >> x >> y;

            tt A = split(root, x - 1);
            tt B = split(A.second, 1);

            if (y < x) {
                tt C = split(A.first, y - 1);
                root = merge(merge(merge(C.first, B.first), C.second), B.second);
            } else {
                tt C = split(B.second, y - x);
                root = merge(merge(merge(A.first, C.first), B.first), C.second);
            }
        } else {
            cin >> x;
            tt A = split(root, x - 1);
            tt B = split(A.second, 1);
            cout << B.first->val << "\n";
            root = merge(merge(A.first, B.first), B.second);
        }
    }

    while (root) {
        tt kk = split(root, 1);
        cout << kk.first->val;
        root = kk.second;
    }

    return 0;
}

• Subtask 1: 0 / 100