Cod sursa(job #1684018)

Utilizator cojocarugabiReality cojocarugabi Data 10 aprilie 2016 18:41:22
Problema Secv8 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("secv8.in");
ofstream fo("secv8.out");
int ok = 0;
struct treap
{
    int key,iv,pr,id,cnt;
    treap * l,* r;
    treap(int key) : key(key),iv(1),pr(rand()+1),l(0),r(0) {}
    void upd(void)
    {
        cnt = 1;
        if (l) l->iv ^= iv,cnt += l->cnt;
        id = cnt;
        if (r) r->iv ^= iv,cnt += r->cnt;
        if (iv) swap(l,r);
        iv = 0;
    }
};
typedef treap *tp;
tp Root = 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;
    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();
}
void add(int pos,int val)
{
    tp left,right;
    split(Root,pos-1,left,right);
    Root = Merge(Merge(left,new treap(val)),right);
}
void del(int p,int u)
{
    tp left,m,right;
    split(Root,p-1,left,right);
    split(right,u-p+1,right,m);
    Root = Merge(left,m);
}
int get(int pos)
{
    tp left,m,right;
    split(Root,pos-1,left,right);
    split(right,1,m,right);
    int ans = m->key;
    Root = Merge(Merge(left,m),right);
    return ans;
}
void print(tp w)
{
    if (!w) return;
    print(w->l);
    cerr << w->key << ' ';
    print(w->r);
}
void rev(int p,int u)
{
    tp left,m,right;
    split(Root,p-1,left,right);
    split(right,u-p+1,m,right);
    m->iv ^= 1;
    Root = Merge(Merge(left,m),right);
}
int main(void)
{
    srand(time(0));
    int n,unused;
    ios_base :: sync_with_stdio(0);
    fi>>n>>unused;
    assert(!unused);
    while (n --)
    {
        char op;
        fi>>op;
        int p,u;
        if (op == 'I')
        {
            fi>>p>>u;
            add(p,u);
        }
        else
        if (op == 'A') fi>>p,fo << get(p) << '\n';
        else
        if (op == 'R') fi>>p>>u,rev(p,u);
        else fi>>p>>u,del(p,u);
    }
    if (Root)
    {
        int n = Root->cnt;
        for (int i = 1;i <= n;++i) fo << get(i) << ' ';
        fo << '\n';
    }
    fo << '\n';
    return 0;
}