Cod sursa(job #403843)

Utilizator freak93Adrian Budau freak93 Data 25 februarie 2010 14:00:36
Problema Secv8 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.65 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<ctime>
#include<string>

using namespace std;

const char iname[]="secv8.in";
const char oname[]="secv8.out";

ifstream f(iname);
ofstream g(oname);

class treap
{
    private:
    class node
    {
        public:
        int key,priority,reverse,sons;
        node *left,*right;
        node(int _key,int _priority,node* _left,node* _right):key(_key),priority(_priority),reverse(0),sons((_left ? _left->sons : 0)+(_right ? _right->sons : 0)+1),left(_left),right(_right){}
    }*R;
    void _get_sons(node* &r){r->sons=((r->left ? r->left->sons : 0)+(r->right ? r->right->sons : 0)+1);}
    void _rot_left(node* &r)
    {
        node *aux=r->left;
        r->left=aux->right;
        aux->right=r;
        _get_sons(r);_get_sons(aux);r=aux;
    }
    void _rot_right(node* &r)
    {
        node* aux=r->right;
        r->right=aux->left;
        aux->left=r;
        _get_sons(r);_get_sons(aux);r=aux;
    }
    void _balance(node* &r)
    {
        if(r->left&&r->left->priority<r->priority)
            _rot_left(r);
        else
            if(r->right&&r->right->priority<r->priority)
                _rot_right(r);
            else
                _get_sons(r);
    }
    void _reverse(node* &r)
    {
        if(r==0)
            return;
        if(r->left)
            r->left->reverse^=r->reverse;
        if(r->right)
            r->right->reverse^=r->reverse;
        if(r->reverse)
        {
            node *aux=r->left;
            r->left=r->right;
            r->right=aux;
            r->reverse=0;
        }
    }
    void _insert(node* &r,int k,int key,int priority)
    {
        if(r==0)
        {
            r=new node(key,priority,NULL,NULL);
            return;
        }
        _reverse(r);_reverse(r->left);_reverse(r->right);
        if(k<=(r->left?r->left->sons:0))
            _insert(r->left,k,key,priority);
        else
            _insert(r->right,(k-1-(r->left?r->left->sons:0)),key,priority);
        _balance(r);
    }
    void _erase(node* &r)
    {
        if(r->left==0&&r->right==0)
        {
            delete r,r=0;
            return;
        }
        _reverse(r),_reverse(r->left),_reverse(r->right);
        if(r->left&&r->right)
            if(r->left->priority<r->right->priority)
                _rot_left(r),_erase(r->right);
            else
                _rot_right(r),_erase(r->left);
        else
            if(r->left)
                _rot_left(r),_erase(r->right);
            else
                _rot_right(r),_erase(r->left);
        _get_sons(r);
    }
    node* _find(node *r,int k)
    {
        _reverse(r);
        if((r->left?r->left->sons:0)+1==k)
            return r;
        if(k<=(r->left?r->left->sons:0))
            return _find(r->left,k);
        else
            return _find(r->right,k-(1+(r->left?r->left->sons:0)));
    }
    public:
    void LRR(node *r)
    {
        if(r==0)
            return;
        _reverse(r);
        LRR(r->left);
        g<<r->key<<" ";
        LRR(r->right);
    }
    void LRR()
    {
        LRR(R);
        g<<"\n";
    }
    void insert(int x,int k)
    {
        _insert(R,k-1,x,rand()+1);
    }
    int find(int x)
    {
        return (_find(R,x))->key;
    }
    void erase(int x,int y)
    {
        node *Ts,*T,*Tg;
        _insert(R,x-1,0,0);
        Ts=R->left;
        _insert(R->right,y-x+1,0,0);
        T=R->right->left;
        Tg=R->right->right;
        delete R->right;
        delete R;
        R=new node(0,0,Ts,Tg);
        _erase(R);
    }
    void reverse(int x,int y)
    {
        node *Ts,*T,*Tg;
        _insert(R,x-1,0,0);
        Ts=R->left;
        _insert(R->right,y-x+1,0,0);
        T=R->right->left;
        Tg=R->right->right;
        T->reverse^=1;
        _reverse(T);
        delete R->right,delete R;
        R=new node(0,0,Ts,T);
        _erase(R);
        T=R,R=new node(0,0,T,Tg);
        _erase(R);
    }
    treap():R(0)
    {
        srand(time(NULL));
    }
} T;

string aux;
int n,x,i,y;

int main()
{
    f>>n>>x;
    f.get();
    for(i=1;i<=n;++i)
    {
        f>>aux;
        if(aux=="I")
            f>>x>>y,T.insert(y,x);
        else
            if(aux=="A")
            {
                f>>x;
                y=T.find(x);
                g<<y<<"\n";
            }
            else
                if(aux=="R")
                    f>>x>>y,T.reverse(x,y);
                else
                    f>>x>>y,T.erase(x,y);
        f.get();
    }

    T.LRR();

    f.close();
    g.close();

    return 0;
}