Cod sursa(job #1649891)

Utilizator Master011Dragos Martac Master011 Data 11 martie 2016 15:37:05
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<cstdio>
using namespace std;

const int nMax = 30000 + 5;
int v[nMax], aint[nMax * 4], sol[nMax];
int st, dr, u, val, poz;

void query(int nod, int a, int b){
    if(st <= a && dr >= b){
        u += aint[nod];
        dr += aint[nod];
    }else{
        int mid = (a + b) / 2;
        if(st <= mid){
            query(2 * nod, a, mid);
        }
        if(dr > mid){
            query(2 * nod + 1, mid + 1, b);
        }

    }
}

void update(int nod, int a, int b){
    if(a == b){
        aint[nod]++;
    }else{
        int mid = (a + b) / 2;
        if(poz <= mid)
            update(2 * nod, a, mid);
        if(poz > mid)
            update(2 * nod + 1, mid + 1, b);

        aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
    }
}

int main (){
    FILE *in = fopen("schi.in","r");
    FILE *out = fopen("schi.out","w");

    int n;
    fscanf(in,"%d", &n);

    for(int i = 1 ; i <= n ; ++i){
        fscanf(in,"%d", v + i);
    }

    for(int i = n ; i >= 1 ; --i){
        st = 1;
        dr = v[i];
        u = 0;
        query(1, 1, n);

        val = 1;
        poz = v[i] + u;
        update(1, 1, n);

        sol[v[i] + u] = i;
    }

    for(int i = 1 ; i <= n ; ++i)
        fprintf(out,"%d\n", sol[i]);
    return 0;
}