Cod sursa(job #1680355)

Utilizator binicBinica Nicolae binic Data 8 aprilie 2016 17:53:33
Problema Schi Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,ras[30004];
struct arbore
{
    int info;
    int mi;
}a[90004];
void split(int nod)
{
    a[nod*2].info+=a[nod].info;
    a[nod*2+1].info+=a[nod].info;

    a[nod*2].mi+=a[nod].info;
    a[nod*2+1].mi+=a[nod].info;
    a[nod].info=0;
}
void update(int nod,int st, int dr, int x, int y, int val1,int val2)
{
    if(x<=st&&dr<=y&&a[nod].mi>=val1)
    {
        a[nod].mi+=val2;
        a[nod].info+=val2;
        return;
    }
    if(st==dr)return;
    int mij=(st+dr)/2;
    if(a[nod].info)split(nod);

    if(mij>=x&&a[nod].mi<=val1)update(nod*2,st,mij,x,y,val1,val2);
    if(mij<y&&a[nod].mi<=val1)update(nod*2+1,mij+1,dr,x,y,val1,val2);

    a[nod].mi=min(a[nod*2].mi,a[nod*2+1].mi);
}
void dfs(int nod,int st, int dr)
{
    if(st==dr)
    {
        ras[a[nod].mi]=st;
        return ;
    }
    int mij=(st+dr)/2;
    if(a[nod].info)split(nod);
    dfs(nod*2,st,mij);
    dfs(nod*2+1,mij+1,dr);
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i>1)update(1,1,n,1,i-1,x,1);
        update(1,1,n,i,i,0,x);
    }
    dfs(1,1,n);
    for(int i=1;i<=n;i++)
        printf("%d\n",ras[i]);
    return 0;
}