Cod sursa(job #520930)

Utilizator S7012MYPetru Trimbitas S7012MY Data 10 ianuarie 2011 19:58:30
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#define DN 30005
using namespace std;

int n,rez[DN],a[2*DN-1],s[DN],i,x;

void update(int vnod,int ls, int ld, int val, int poz) {
    if(ls==ld) {
        a[vnod]=val;
        return;
    }
    int m=(ls+ld)>>1;
    if(poz<=m) update((vnod<<1),ls,m,val,poz);
    else update((vnod<<1)+1,m+1,ld,val,poz);
    a[vnod]=a[(vnod<<1)]+a[(vnod<<1)+1];
}

int query(int vnod, int ls, int ld, int val) {
    if(ls==ld) return ls;
    int m=(ls+ld)>>1;
    if(val<=a[(vnod<<1)]) return query((vnod<<1),ls,m,val);
    else return query((vnod<<1)+1,m+1,ld,val-a[(vnod<<1)]);
}

int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    for (i=1; i<=n; ++i) {
        f>>s[i];
        update(1,1,n,1,i);
    }
    for (i=n; 0<i; --i)  {
        x=query(1,1,n,s[i]);
        rez[x]=i;
        update(1,1,n,0,x);
    }
    for (i=1; i<=n; ++i)  g<<rez[i]<<'\n';
    return 0;
}