Cod sursa(job #1072436)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 4 ianuarie 2014 14:16:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#define Nmax 30000
#define common int mij=((left+right)>>1), lson=(nod<<1), rson=lson+1

using namespace std;

int N,a[Nmax],aint[4*Nmax];

inline void Read()
{
    ifstream fin("schi.in");
    fin>>N;
    for(int i=1;i<=N;++i)
        fin>>a[i];
    fin.close();
}

inline void Build(int nod, int left, int right)
{
    if(left==right)
    {
        aint[nod]=1;
        return;
    }
    common;
    Build(lson,left,mij);
    Build(rson,mij+1,right);
    aint[nod]=aint[lson]+aint[rson];
}

inline int Query(int nod, int left, int right, int val)
{
    if(left==right)
        return left;
    common;
    if(val<=aint[lson])
        return Query(lson,left,mij,val);
    return Query(rson,mij+1,right,val-aint[lson]);
}

inline void Update(int nod, int left, int right, int poz)
{
    if(left==right)
    {
        aint[nod]=0;
        return;
    }
    common;
    if(poz<=mij)
        Update(lson,left,mij,poz);
    else
        Update(rson,mij+1,right,poz);
    aint[nod]=aint[lson]+aint[rson];
}

inline void Solve()
{
    int i,sol[30005],poz;
    for(i=N;i>0;--i)
    {
        poz=Query(1,1,N,a[i]);
        sol[poz]=i;
        Update(1,1,N,poz);
    }
    ofstream fout("schi.out");
    for(i=1;i<=N;++i)
        fout<<sol[i]<<"\n";
    fout.close();
}

int main()
{
    Read();
    Build(1,1,N);
    Solve();
    return 0;
}