Cod sursa(job #1307191)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 1 ianuarie 2015 16:26:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int NMAX=30005;

int n,a[NMAX],sol[NMAX];
int aint[4*NMAX];

inline void Update(int nod,int st,int dr,int poz,int val)
{
    if (st==dr) aint[nod]=val;
    else
        {
            int mij=(st+dr)>>1;

            if (poz<=mij) Update(2*nod,st,mij,poz,val);
            if (poz>mij) Update(2*nod+1,mij+1,dr,poz,val);

            aint[nod]=aint[2*nod]+aint[2*nod+1];
        }
}

inline int Query(int nod,int st,int dr,int val)
{
    if (st==dr) return st;
    else
        {
            int mij=(st+dr)>>1;

            if (aint[2*nod]>=val) return Query(2*nod,st,mij,val);
            else return Query(2*nod+1,mij+1,dr,val-aint[2*nod]);
        }
}

int main()
{
    int i,x;
    fin>>n;
    for (i=1;i<=n;i++)
        {
            fin>>a[i];
            Update(1,1,n,i,1);
        }
    for (i=n;i>=1;i--)
        {
            x=Query(1,1,n,a[i]);
            sol[x]=i;
            Update(1,1,n,x,0);
        }
    for (i=1;i<=n;i++) fout<<sol[i]<<"\n";
    return 0;
}