Cod sursa(job #1654318)

Utilizator touristGennady Korotkevich tourist Data 16 martie 2016 22:39:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
#define Nmax 30005

using namespace std;

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

inline void upd(int nod, int st, int dr, int x, int val)
{
    if(st==dr)
    {
        aint[nod]=val; return;
    }
    int mij=((st+dr)>>1);
    if(x<=mij) upd(2*nod,st,mij,x,val);
    else upd(2*nod+1,mij+1,dr,x,val);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}

inline int qry(int nod, int st, int dr, int k)
{
    if(st==dr) return st;
    int mij=((st+dr)>>1);
    if(aint[2*nod]>=k) return qry(2*nod,st,mij,k);
    else return qry(2*nod+1,mij+1,dr,k-aint[2*nod]);
}

int main()
{
    int i;
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>a[i];
        upd(1,1,n,i,1);
    }
    for(i=n;i;--i)
    {
        a[i]=qry(1,1,n,a[i]);
        upd(1,1,n,a[i],0);
        sol[a[i]]=i;
    }
    for(i=1;i<=n;++i) cout<<sol[i]<<"\n";
    return 0;
}