Cod sursa(job #1809594)

Utilizator lupvasileLup Vasile lupvasile Data 19 noiembrie 2016 01:24:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
#define cout fout
#endif // INFOARENA

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

#define nmax 30001

int n,m;
int aib[70000];
int loc[nmax],loc_fin[nmax];

void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aib[nod]=1;
        return;
    }

    int left=nod<<1,right=nod<<1|1;
    int mid=(st+dr)>>1;

    build(left,st,mid);
    build(right,mid+1,dr);

    aib[nod]=aib[left]+aib[right];
}

void update(int nod,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        aib[nod]+=val;
        return;
    }

    int left=nod<<1,right=nod<<1|1;
    int mid=(st+dr)>>1;

    if(pos<=mid)update(left,st,mid,pos,val);
    else update(right,mid+1,dr,pos,val);

    aib[nod]=aib[left]+aib[right];
}

int binsrc(int nod,int st,int dr,int val)
{
    if(aib[nod]<=val) return dr;

    if(st==dr) return st-1;

    int left=nod<<1,right=nod<<1|1;
    int mid=(st+dr)>>1;

    if(val>=aib[left]) return binsrc(right,mid+1,dr,val-aib[left]);
    return binsrc(left,st,mid,val);
}

void read()
{
    fin>>n;
    for(int i=1; i<=n; ++i) fin>>loc[i];
}

int main()
{
    read();

    int i,x;

    build(1,1,n);

    for(i=n; i; --i)
    {
        x=binsrc(1,1,n,loc[i]-1)+1;
        loc_fin[x]=i;
        update(1,1,n,x,-1);
    }
    for(i=1; i<=n; ++i) cout<<loc_fin[i]<<'\n';
    return 0;
}