Cod sursa(job #36326)

Utilizator victorsbVictor Rusu victorsb Data 23 martie 2007 13:33:04
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>

#define Nmax 30005
#define Amax 65536

int n, vl, a, b;
int sir[Nmax], ai[Amax], pos[Nmax];

void citire()
{
    int i;
    
    scanf("%d\n", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d\n", &sir[i]);
}

void update(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
        ai[nod] += vl;
    else
    {
        int mij = (st + dr) >> 1;
        
        if (a <= mij)
            update(nod*2, st, mij);
        
        if (mij < b)
            update(nod*2+1, mij + 1, dr);
        
        ai[nod] = ai[nod*2] + ai[nod*2+1];
    }
}

int query(int nod, int st, int dr, int k)
{
    if (st == dr && k == 1)
        return st;
    else
    {
        int mij = (st + dr) >> 1;
        
        if (k <= ai[nod*2])
            return query(nod*2, st, mij, k);
        
        else
            return query(nod*2+1, mij + 1, dr, k - ai[nod*2]);
    }
}

void solve()
{
    int i;
    
    vl = 1;
    for (i = 1; i <= n; ++i)
    {
        a = b =i;
        update(1, 1, n);
    }
    
    vl = -1;
    for (i = n; i > 0; --i)
    {
        a = b = query(1, 1, n, sir[i]);
        pos[a] = i;
        update(1, 1, n);
    }
    
    for (i = 1; i <= n; ++i)
        printf("%d\n", pos[i]);
}    

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    citire();
    solve();
    return 0;
}