Cod sursa(job #1399475)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 martie 2015 19:16:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <cstdlib>
using namespace std;

struct item {
    item *l,*r;
    int sz,vl,pr;

    item(int x)
    {
        l = r = NULL;
        sz = 1;
        vl = x;
        pr = (rand() << 6) ^ rand();
    }
};

#define tree item*

void upd(tree& t)
{
    if ( !t ) return;
    t->sz = 1 + ( t->l ? t->l->sz : 0 ) + ( t->r ? t->r->sz : 0 );
}

void split(tree t,int pl,tree &l,tree &r)
{
    if ( !t )
        return void(l = r = NULL);
    int sz = t->l ? t->l->sz : 0;
    if ( pl <= sz )
        split(t->l,pl,l,t->l) , r = t;
    else
        split(t->r,pl-sz-1,t->r,r), l = t;
    upd(l);
    upd(r);
}

void insert(tree &t,int pl,tree x)
{
    if ( !t )
        return void(t = x);
    int sz = t->l ? t->l->sz : 0;
    if ( t->pr > x->pr )
        split(t,pl,x->l,x->r), t = x;
    else
        if ( pl <= sz )
            insert(t->l,pl,x);
        else
            insert(t->r,pl-sz-1,x);
    upd(t);
}

void merge(tree &t,tree l,tree r)
{
    if ( !l || !r )
        return void(t = l ? l : r);
    if ( l->pr > r->pr )
        merge(r->l,l,r->l) , t = r;
    else
        merge(l->r,l->r,r) , t = l;
    upd(t);
}

void erase(tree& t,int pl)
{
    int sz = t->l ? t->l->sz : 0;
    if ( sz + 1 == pl )
        merge(t,t->l,t->r);
    else
    {
        if ( pl <= sz )
            erase(t->l,pl);
        else
            erase(t->l,pl-sz-1);
    }
    upd(t);
}

void print(tree t)
{
    if ( t->l ) print(t->l);
    printf("%d\n",t->vl);
    if ( t->r ) print(t->r);
}

int n,x;
tree t = NULL;

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

    scanf("%d",&n);
    for (int i=1,p;i<=n;++i)
    {
        scanf("%d",&p);
        tree x = new item(i);
        insert(t,p-1,x);
    }
    print(t);
}