Cod sursa(job #2120408)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 2 februarie 2018 13:56:37
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 30000;

int n;
int v[NMAX + 2];

int aint[4 * NMAX + 2], ans[NMAX + 2];

void update(int node, int st, int dr, int poz)
{
    if(st == dr)
    {
        aint[node] = 1;
        return;
    }

    int med = (st + dr) / 2;
    if(poz <= med)
        update(2 * node, st, med, poz);
    else
        update(2 * node + 1, med + 1, dr, poz);

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

void query(int node, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        aint[node] = 0;
        ans[st] = poz;
        return;
    }

    int med = (st + dr) / 2;
    if(val <= aint[2 * node])
        query(2 * node, st, med, poz, val);
    else
        query(2 * node + 1, med + 1, dr, poz, val - aint[2 * node]);

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

int main()
{
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i];
        update(1, 1, n, i);
    }

    for(int i = n; i >= 1; i--)
        query(1, 1, n, i, v[i]);

    for(int i = 1; i <= n; i++)
        out << ans[i] << '\n';

    return 0;
}