Cod sursa(job #2062474)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 10 noiembrie 2017 14:59:34
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>

using namespace std;

int arbint[120005], v[30005], s[30005];

void update(int nod, int st, int dr, int poz, int val) {
    if(st == dr) {
        arbint[nod] = val;
    } else if(st < dr) {
        int med = (st + dr) / 2;
        if(poz <= med) {
            update(2 * nod, st, med, poz, val);
        } else {
            update(2 * nod + 1, med + 1, dr, poz, val);
        }
        arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
    }
}

int ramasSt;
void sterge(int nod, int st, int dr, int suma, int val) {
    if(st == dr) {
        s[st] = val;
        arbint[nod] = 0;
    } else if(st < dr) {
        int med = (st + dr) / 2;
        if(ramasSt + arbint[2 * nod] >= suma) {
            sterge(2 * nod, st, med, suma, val);
        } else {
            ramasSt += arbint[2 * nod];
            sterge(2 * nod + 1, med + 1, dr, suma, val);
        }
        arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
    }
}

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

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &v[i]);
        update(1, 1, n, i, 1);
    }

    for(int i = n; i >= 1; -- i) {
        ramasSt = 0;
        sterge(1, 1, n, v[i], i);
    }

    for(int i = 1; i <= n; ++ i) {
        printf("%d\n", s[i]);
    }

    return 0;
}