Cod sursa(job #2144619)

Utilizator CozehNita Horia Teodor Cozeh Data 26 februarie 2018 20:38:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
using namespace std;

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

const int nmax = 3 * 1e4;
int n;

int aint[4*nmax+1];
int v[nmax+1];
int rez[nmax+1];

void creare(int st, int dr, int nod){
    if(st == dr) aint[nod] = 1;
    else{
        int mij = (st+dr)/2;
        creare(st,mij,nod*2);
        creare(mij+1,dr,nod*2+1);
        aint[nod] = aint[nod*2]+aint[nod*2+1];
    }
}

void update(int nod, int st, int dr, int pos, int ind){
    if(st == dr){
        aint[nod] = 0;
        rez[st] = ind;
    }
    else{
        int mij = (st+dr)/2;
        if(aint[nod*2] >= pos){
            update(nod*2,st,mij,pos,ind);
        }
        else{
            update(nod*2+1,mij+1,dr,pos-aint[2*nod],ind);
        }
        aint[nod] = aint[nod*2]+aint[nod*2+1];
    }
}

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

    creare(1,n,1);
    for(i = n; i >= 1; i--){
        update(1,1,n,v[i],i);
    }

    for(i = 1; i <= n; i++){
        fout<<rez[i]<<"\n";
    }

}