Cod sursa(job #2706942)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 16 februarie 2021 10:07:10
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#define dim 30010
using namespace std;
int a[4*dim];
int v[dim];
int sol[dim];
int i,n;

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];
    }
}

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

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

int main() {
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i];
    }
    build(1,1,n);
    for (i=n;i>=1;i--) {
        int poz=v[i];
        poz=pozActualizata(1,1,n,poz);
        update(1,1,n,poz);
    }
    for (i=1;i<=n;i++) {
        fout<<sol[i]<<"\n";
    }
    return 0;
}