Cod sursa(job #1765795)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 26 septembrie 2016 23:34:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

using namespace std;

const int N=30005;
int v[4*N],d[N],sol[N],sum;

void update(int pos, int st, int dr, int a, int val){
    if(a<st or dr<a) return;
    if(st==dr){
        v[pos]+=val;
        return;
    }

    update(2*pos, st, (st+dr)/2, a, val);
    update(2*pos+1, (st+dr)/2+1, dr, a, val);
    v[pos]=v[2*pos]+v[2*pos+1];
}

void query(int pos, int st, int dr, int a, int b){
    if(st>b or dr<a) return;
    if(a<=st and dr<=b){
        sum+=v[pos];
        return;
    }

    query(2*pos, st, (st+dr)/2, a, b);
    query(2*pos+1, (st+dr)/2+1, dr, a, b);
}

int main(){
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    int n,i,in,sf,mij;

    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&d[i]);
    for(i=n;i>=1;i--){
        in=1, sf=n;
        mij=(in+sf)>>1;
        while(in<sf){
            sum=0;
            query(1,1,n,1,mij);
            if(mij<sum+d[i]) in=mij+1;
            else sf=mij;
            mij=(in+sf)>>1;
        }

        update(1,1,n,mij,1);
        sol[mij]=i;
    }
    for(i=1;i<=n;i++) printf("%d\n",sol[i]);

    return 0;
}