Cod sursa(job #1685952)

Utilizator cojocarugabiReality cojocarugabi Data 11 aprilie 2016 22:43:41
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 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;
void print(tp w)
{
    if (!w) return;
    w->upd();
    print(w->l);
    //cerr << w->key << ' ' << w->id << ' ' << w->cnt << '\n';
    cerr << w->key << ' ';
    print(w->r);
}
int ok = 0;
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 (ok) cerr << "FUCK " << w->key << ' ' << w->id << ' ' << w->cnt << ' ' << k << '\n';
    if (w->id <= k)
    {
    //    if (ok) cerr << "RIGHT\n";
        split(w->r,k-w->id,w->r,right);
        left = w;
    }
    else
    {
    //    if (ok) cerr << "LEFT\n";
        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;
    //if (pos == 4 && val == 4) ok = 1;
    split(Root,pos-1,left,right);
    //if (pos == 4 & val == 4)
    //{
    //    cerr << "1: ";
    //    print(left);
    //    cerr << "\n2: ";
    //    print(right);
    //    cerr << '\n';
    //    exit(0);
    //}
    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);
            if (pos == 4 && val == 4)
            {
                //print(Root);
                //cerr << '\n';
                //exit(0);
            }
        }
        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);
        }
        //cerr << "Begin ";
        //print(Root);
        //cerr << '\n';
    }
    if (Root)
    {
        int sz = Root->cnt;
        for (int i = 1;i <= sz;++i) fo << query(i) << ' ';
        fo << '\n';
    }
    return 0;
}