Cod sursa(job #2699747)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 25 ianuarie 2021 19:20:04
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define DIM 30005

using namespace std;

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

int n,i,v[DIM],a[4*DIM],poz[DIM];

void build(int nod, int st, int dr)
{
    if (st == dr)
        a[nod] = 1;
    else
    {
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        a[nod] = a[2*nod]+a[2*nod+1];
    }
}

void update(int nod, int st, int dr, int p)
{
    if (st == dr)
        a[nod]--;
    else
    {
        int mid = (st+dr)/2;
        if (p <= mid)
            update(2*nod, st, mid, p);
        else
            update(2*nod+1, mid+1, dr, p);
        a[nod] = a[2*nod]+a[2*nod+1];
    }
}

int query(int nod, int st, int dr, int nr)
{
    if (st == dr)
        return st;
    else
    {
        int mid = (st+dr)/2;
        if (a[2*nod] >= nr)
            query(2*nod, st, mid, nr);
        else
            query(2*nod+1, mid+1, dr, nr-a[2*nod]);
    }
}

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i];
    build(1, 1, n);
    for (i=n; i>=1; i--)
    {
        int ind = query(1, 1, n, v[i]);
        update(1, 1, n, ind);
        poz[ind] = i;
    }
    for (i=1; i<=n; i++)
        fout << poz[i] << "\n";
    return 0;
}