Cod sursa(job #1689144)

Utilizator george_stelianChichirim George george_stelian Data 13 aprilie 2016 23:22:13
Problema Secv8 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.93 kb
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <vector>

using namespace std;

int random()
{
    return abs(rand()*rand());
}

class treap
{
    public:
        treap()
        {
            nil=new node(-1);
            nil->st=nil->dr=nil;
            rad=nil;
        }
        void insert(int x,int poz)
        {
            rad=insert(rad,poz,random(),x);
        }
        int acces(int poz)
        {
            return find(rad,poz);
        }
        void reverse(int x,int y)
        {
            pairnode a=split(rad,x-1);
            pairnode b=split(a.dr,y-x+1);
            b.st->inv^=1;
            rad=merge(a.st,b.st);
            rad=merge(rad,b.dr);
        }
        void erase(int poz)
        {
            rad=erase(rad,poz);
        }
        vector<int> get_vector()
        {
            vector<int> sol;
            dfs(rad,sol);
            return sol;
        }

    private:
        struct node
        {
            node *st,*dr;
            int val=0,pr=0,inv=0,size=0;
            node(node *st1,node *dr1,int val1,int pr1)
            {
                st=st1;dr=dr1;
                val=val1;pr=pr1;
                update(1);
            }
            node(int pr1) {pr=pr1;}
            void update(int tip)
            {
                if(tip) size=st->size+dr->size+1;
                if(inv)
                {
                    swap(st,dr);
                    st->inv^=1;dr->inv^=1;
                    inv=0;
                }
            }
        };
        node *rad,*nil;

        struct pairnode
        {
            node *st,*dr;
            pairnode(node *st1,node *dr1) {st=st1;dr=dr1;}
        };

        node *insert(node *nod,int poz,int pr,int val)
        {
            nod->update(0);
            if(pr>nod->pr)
            {
                pairnode a=split(nod,poz);
                return new node(a.st,a.dr,val,pr);
            }
            if(poz<=nod->st->size) nod->st=insert(nod->st,poz,pr,val);
            else nod->dr=insert(nod->dr,poz-nod->st->size-1,pr,val);
            nod->update(1);
            return nod;
        }
        pairnode split(node *nod,int poz)
        {
            if(nod==nil) return pairnode(nil,nil);
            nod->update(0);
            if(poz<=nod->st->size)
            {
                pairnode a=split(nod->st,poz);
                nod->st=a.dr;
                nod->update(1);
                return pairnode(a.st,nod);
            }
            else
            {
                pairnode a=split(nod->dr,poz-nod->st->size-1);
                nod->dr=a.st;
                nod->update(1);
                return pairnode(nod,a.dr);
            }
        }
        node *erase(node *nod,int poz)
        {
            nod->update(0);
            if(poz==nod->st->size+1)
            {
                node *a=merge(nod->st,nod->dr);
                delete nod;
                return a;
            }
            if(poz<=nod->st->size) nod->st=erase(nod->st,poz);
            else nod->dr=erase(nod->dr,poz-nod->st->size-1);
            nod->update(1);
            return nod;
        }
        node *merge(node *st,node *dr)
        {
            if(st==nil && dr==nil) return nil;
            st->update(0);dr->update(0);
            if(st->pr>dr->pr)
            {
                st->dr=merge(st->dr,dr);
                st->update(1);
                return st;
            }
            else
            {
                dr->st=merge(st,dr->st);
                dr->update(1);
                return dr;
            }
        }
        int find(node *nod,int poz)
        {
            nod->update(0);
            if(poz==nod->st->size+1) return nod->val;
            else if(poz<=nod->st->size) return find(nod->st,poz);
            else return find(nod->dr,poz-nod->st->size-1);
        }
        void dfs(node *nod,vector<int> &sol)
        {
            if(nod==nil) return;
            nod->update(0);
            dfs(nod->st,sol);
            sol.push_back(nod->val);
            dfs(nod->dr,sol);
        }
};

int main()
{
    freopen("secv8.in", "r", stdin);
    freopen("secv8.out", "w", stdout);
    srand(time(0));
    int n,x,poz,y;
    char c;
    treap v;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++)
    {
        scanf("\n%c",&c);
        if(c=='I')
        {
            scanf("%d%d",&poz,&x);
            v.insert(x,poz-1);
        }
        else if(c=='A')
        {
            scanf("%d",&poz);
            printf("%d\n",v.acces(poz));
        }
        else if(c=='R')
        {
            scanf("%d%d",&x,&y);
            v.reverse(x,y);
        }
        else if(c=='D')
        {
            scanf("%d%d",&x,&y);
            for(int j=x;j<=y;j++) v.erase(x);
        }
    }
    vector<int> sol=v.get_vector();
    for(int i=0;i<sol.size();i++) printf("%d ",sol[i]);
    return 0;
}