Cod sursa(job #1685956)

Utilizator cojocarugabiReality cojocarugabi Data 11 aprilie 2016 22:46:03
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("secv8.in");
ofstream fo("secv8.out");
struct treap
{
    int key,cnt,pr,id,rv;
    treap *l,*r;
    void upd(void)
    {
        cnt = 1;
        if (l) cnt += l->cnt;
        id = cnt;
        if (r) cnt += r->cnt;
        if (rv)
        {
            rv = 0;
            swap(l,r);
            if (l) l->rv ^= 1;
            if (r) r->rv ^= 1;
        }
    }
    treap(int key) : key(key),pr(rand()+1) {l = r = 0;rv = 0;upd();}
};
typedef treap *tp;
tp Merge(tp a,tp b)
{
    if (a) a->upd();
    if (b) b->upd();
    if (!a) return b;
    if (!b) return a;
    if (a->pr > b->pr)
    {
        a->r = Merge(a->r,b);
        a->upd();
        return a;
    }
    else
    {
        b->l = Merge(a,b->l);
        b->upd();
        return b;
    }
}
void split(tp w,int k,tp &left,tp &right)
{
    left = right = 0;
    if (!w) return;
    w->upd();
    if (w->l) w->l->upd();
    if (w->r) w->r->upd();
    if (w->id <= k)
    {
        split(w->r,k-w->id,w->r,right);
        left = w;
    }
    else
    {
        split(w->l,k,left,w->l);
        right = w;
    }
    if (left) left->upd();
    if (right) right->upd();
}
tp Root = 0;
void del(int p,int u)
{
    tp left,mid,right;
    split(Root,p-1,left,mid);
    split(mid,u-p+1,mid,right);
    Root = Merge(left,right);
}
void rev(int p,int u)
{
    tp left,mid,right;
    split(Root,p-1,left,mid);
    split(mid,u-p+1,mid,right);
    mid->rv ^= 1;
    Root = Merge(Merge(left,mid),right);
}
int query(int pos)
{
    tp left,mid,right;
    split(Root,pos-1,left,mid);
    split(mid,1,mid,right);
    int ans = mid->key;
    Root = Merge(Merge(left,mid),right);
    return ans;
}
void add(int pos,int val)
{
    tp left,right;
    split(Root,pos-1,left,right);
    Root = Merge(Merge(left,new treap(val)),right);
}
int main(void)
{
    int n,us;
    ios_base :: sync_with_stdio(0);
    fi>>n>>us;
    while (n --)
    {
        char op;
        fi>>op;
        if (op == 'I')
        {
            int pos,val;
            fi>>pos>>val;
            add(pos,val);
        }
        else
        if (op == 'D')
        {
            int p,u;
            fi>>p>>u;
            del(p,u);
        }
        else
        if (op == 'A')
        {
            int pos;
            fi>>pos;
            fo << query(pos) << '\n';
        }
        else
        {
            int p,u;
            fi>>p>>u;
            rev(p,u);
        }
    }
    if (Root)
    {
        int sz = Root->cnt;
        for (int i = 1;i <= sz;++i) fo << query(i) << ' ';
        fo << '\n';
    }
    return 0;
}