Cod sursa(job #1500500)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 12 octombrie 2015 01:50:37
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>

using namespace std;
int m  ,temp;
char tip;
int x,y;

#define priority prior

class treap{
public:
    treap(){
        nil = new node(0 , -1);
        nil->left = nil->right = nil;
        nil->nr = nil->rev = 0;
        rad=nil;
    }

    void insert(int poz , int val ){
        rad = insert(rad,poz,val,rand());
    }

    void getvector(){
        dfs(rad);
    }

 private:
    struct node{
        int val ,prior  , nr;
        char rev;
        node *left, *right;

        node(int v,int p)
            : val(v) , prior(p){}

        node(node *l,node *r,int &v,int &p,char rc)
            : val(v) , prior(p) , rev(rc) , left(l) , right(r) {
            update(1);
        }

        void update(int tip){
            if( tip ) nr = left->nr + right->nr +1;
            if( rev ) {
                rev = false;
                swap(left,right);
                left->rev  ^= 1;
                right->rev ^= 1;
            }
        }
    };
    vector<int> q;
    node *nil , *rad;
    struct pairnode{
        node *left,*right;
        pairnode( node *l, node *r) : left(l) , right(r) {}
    };


    node* insert( node *nod , int poz ,int val ,int prior ){
        nod->update(0);
        if( nod->prior < prior){
            pairnode a = split( nod , poz );
            return new node(a.left , a.right , val , prior , 0 );
        }
        if( poz <= nod->left->nr )
            nod->left = insert(nod->left , poz, val , prior);
        else
            nod->right= insert(nod->right, poz - nod->left->nr -1, val , prior);
        nod->update(1);
        return nod;
    }

    pairnode split(node *nod,int poz){
        nod->update(0);
        if( nod == nil ) return pairnode(nil,nil);
        if( poz <= nod->left->nr ){
            pairnode a = split( nod->left , poz );
            nod->left = a.right;
            nod->update(1);
            return pairnode(a.left, nod);
        }else{
            pairnode a = split( nod->right, poz - nod->left->nr -1 );
            nod->right = a.left;
            nod->update(1);
            return pairnode(nod,a.right);
        }
    }

    void dfs(node *nod){
        if(nod==nil)
            return;
        nod->update(0);
        dfs(nod->left);
        cout << nod->val <<'\n';
        dfs(nod->right);
        }
};
treap v;

int main()
{



    freopen("schi.in" , "r" , stdin);
    freopen("schi.out", "w" , stdout);

    scanf("%d",&m);
    srand(time(0));
    for(int i=1;i<=m;++i){
        scanf("%d",&x);
        v.insert(x-1,i);
    }


     v.getvector();



    return 0;
}