Cod sursa(job #3161033)

Utilizator zetef3Dediu Stefan zetef3 Data 25 octombrie 2023 16:25:27
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;

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

const int NMAX=3e4;
const int NAINT=4*NMAX;

int n;
int v[NMAX], rez[NMAX], aint[NAINT];

void build(int p, int st, int dr) {
    if (st==dr) {
        aint[p]=1;
        return;
    }

    int m=(st+dr)/2, fs=2*p, fd=2*p+1;
    build(fs, st,m);
    build(fd, m+1,dr);

    aint[p]=aint[fs]+aint[fd];
}

void update(int p, int st, int dr, int poz, int x) {
    if (st==dr) {
        aint[p]+=x;
        return;
    }

    int m=(st+dr)/2, fs=2*p, fd=2*p+1;

    if (poz<=m) update(fs, st,m, poz,x);
    else update(fd, m+1,dr, poz,x);

    aint[p]=aint[fs]+aint[fd];
}

int query(int p, int st, int dr, int val) {
    if (st==dr) {
        return st;
    }

    int m=(st+dr)/2, fs=2*p, fd=2*p+1;
    if (val<=aint[fs]) return query(fs, st,m, val);
    else               return query(fd, m+1,dr, val-aint[fs]);
}

int main()
{
    f >> n;

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

    for (int i=n;i>=1;i--) {
        int poz=query(1,1,n,v[i]);
        update(1,1,n,poz,-1);
        rez[poz]=i;
    }

    for (int i=1;i<=n;i++)
        g << rez[i] << '\n';

    return 0;
}