Cod sursa(job #162442)

Utilizator sealTudose Vlad seal Data 20 martie 2008 00:40:04
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<stdio.h>
#define Nm (1<<15)
#define md (l+r>>1)
#define ls (n<<1)
#define rs (n<<1|1)
short A[Nm],M[Nm<<1],P[Nm<<1],Sub[Nm<<1],n;

void read()
{
    int i;

    freopen("schi.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",A+i);
}

void build(int n, int l, int r)
{
    if(l==r)
    {
        M[n]=A[l];
        P[n]=l;
    }
    else
    {
        build(ls,l,md);
        build(rs,md+1,r);
        
        if(M[ls]<M[rs])
        {
            M[n]=M[ls];
            P[n]=P[ls];
        }
        else
        {
            M[n]=M[rs];
            P[n]=P[rs];
        }
    }
}

int p;

void update1(int n, int l, int r)
{
    if(l==r)
        M[n]=Nm-1;
    else
    {
        if(p<=md)
            update1(ls,l,md);
        else
            update1(rs,md+1,r);
            
        if(M[ls]<M[rs])
        {
            M[n]=M[ls];
            P[n]=P[ls];
        }
        else
        {
            M[n]=M[rs];
            P[n]=P[rs];
        }
        M[n]-=Sub[n];
    }
}

void update2(int n, int l, int r)
{
    if(l>p)
        --M[n], ++Sub[n];
    else
    {
        if(p<md)
            update2(ls,l,md);
        update2(rs,md+1,r);

        if(M[ls]<M[rs])
        {
            M[n]=M[ls];
            P[n]=P[ls];
        }
        else
        {
            M[n]=M[rs];
            P[n]=P[rs];
        }
        M[n]-=Sub[n];
    }
}

void solve()
{
    int i;

    build(1,1,n);

    freopen("schi.out","w",stdout);
    
    for(i=n;i;--i)
    {
        p=P[1];
        printf("%d\n",p);
        update1(1,1,n);
        if(p<n)
            update2(1,1,n);
    }
}

int main()
{
    read();
    solve();
    return 0;
}