Submission #1123464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123464		12345678	Collider (IZhO11_collider)	C++20	100 / 100	151 ms	48308 KiB

collider

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(time(0));

int n, q, x, y;
string s;
char c;

struct treap
{
    struct node
    {
        char c;
        int sz, key;
        node *l, *r;
        node(char c): c(c), sz(1), key(rng()), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt;
    int sz(pnode x)
    {
        return x?x->sz:0;
    }
    void update(pnode x)
    {
        if (x) x->sz=sz(x->l)+sz(x->r)+1;
    }
    void merge(pnode l, pnode r, pnode &k)
    {
        if (!l) return k=r, void();
        if (!r) return k=l, void();
        if (l->key>=r->key) merge(l->r, r, l->r), k=l;
        else merge(l, r->l, r->l), k=r;
        update(k);
    }
    void split(pnode &l, pnode &r, pnode k, int key)
    {
        if (!k) return l=r=0, void();
        if (1+sz(k->l)<=key) split(k->r, r, k->r, key-(1+sz(k->l))), l=k;
        else split(l, k->l, k->l, key), r=k;
        update(l); update(r); 
    }
    void swap(int x, int y)
    {
        pnode p1, p2, p3;
        split(p1, rt, rt, x-1);
        split(p2, p3, rt, 1);
        merge(p1, p3, rt);
        split(p1, p3, rt, y-1);
        merge(p1, p2, rt);
        merge(rt, p3, rt);
    }
    void query(int x)
    {
        pnode p1, p2, p3;
        split(p1, rt, rt, x-1);
        split(p2, p3, rt, 1);
        cout<<p2->c<<'\n';
        merge(p1, p2, rt);
        merge(rt, p3, rt);
    }
    void show(pnode x)
    {
        if (!x) return;
        show(x->l);
        cout<<x->c;
        show(x->r);
    }
} t;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q>>s;
    for (int i=1; i<=n; i++) 
    {
        t.merge(t.rt, new treap::node(s[i-1]), t.rt);
        //t.show(t.rt);
        //cout<<'\n';
    }
    for (int i=1; i<=q; i++)
    {
        cin>>c;
        if (c=='a') cin>>x>>y, t.swap(x, y);
        else cin>>x, t.query(x);
    }
}

• Subtask 1: 100 / 100