Cod sursa(job #917017)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 17 martie 2013 09:46:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
using namespace std;

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

const int INF  = (1<<29);

int n,x[30010],s[30010],i,j,a[70100],m,op,p,q;

int build(int i, int li, int ls) {
    if(li > ls)
        return -INF;

    if(li == ls) {
        a[i] = x[li];
        return a[i];
    }
    
    a[i] = 
          build(2*i  , li,         (li+ls)/2 )
        + build(2*i+1, (li+ls)/2+1,  ls        )
    ;
    return a[i];
}

int chg(int i, int li, int ls, int v, int pos) {
    if(pos < li || pos > ls) {
        return a[i];
    }
    if(li == ls && li == pos) {
        a[i] -= v;
        return a[i];
    }
    return a[i] = chg(2*i, li, (li+ls)/2, v, pos) + chg(2*i+1, (li+ls)/2+1, ls, v, pos);
}

int query(int i, int li, int ls, int qi, int qs) {
    if(qs < li || qi > ls)
        return 0;
    if(li >= qi && ls <= qs)
        return a[i];
    return query(2*i, li, (li+ls)/2, qi, qs) + query(2*i+1, (li+ls)/2+1, ls, qi, qs);
}

int mark(int i, int li, int ls, int q) {
    a[i] --;
    if(li == ls)
        return li;
    if(q <= a[2*i]) {
        return mark(2*i, li, (li+ls)/2, q);
    } else {
        return mark(2*i+1, (li+ls)/2+1, ls, q-a[2*i]);
    }
}

int main() {
    in>>n;
    for(i=1; i<=n; i++) {
        x[i] = 1;
        in>>s[i];
    }
    build(1, 1, n);
    for(i=1; i<=n; i++) {
        q = s[n-i+1];
        p = mark(1, 1, n, q);
        x[p] = n-i+1;
        //out<<n-i+1<<" --> "<<p<<'\n';
    }
    for(i=1; i<=n; i++)
        out<<x[i]<<'\n';
    return 0;
}