Cod sursa(job #3253739)

Utilizator schema_227Stefan Nicola schema_227 Data 4 noiembrie 2024 17:04:00
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N;
vector<int> arbore(4 * 30000);
vector<int> rezultat;

void BUILD(int nod, int st, int dr){
    if(st == dr){
        arbore[nod] = 1;
        return;
    }
    int mij = (st + dr) / 2;
    BUILD(2 * nod, st, mij);
    BUILD(2 * nod + 1, mij + 1, dr);
    arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];
}

void UPDATE(int nod, int st, int dr, int pos){
    if(st == dr){
        arbore[nod] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if(pos <= mij)
        UPDATE(nod * 2, st, mij, pos);
    else
        UPDATE(nod * 2 + 1, mij + 1, dr, pos);
        arbore[nod] = arbore[nod * 2] + arbore[nod * 2 + 1];
}

void QUERY(int nod, int st, int dr, int k, int i){
    if(st == dr){
        rezultat[st] = i;
        arbore[nod] = 0;
        return;
    }
    int mij = (st + dr) / 2;
    if(arbore[nod * 2] <= k)
        QUERY(nod * 2, st, mij, k, i);
    else
        QUERY(nod * 2 + 1, mij + 1, dr, k - arbore[nod * 2], i);
    arbore[nod] = arbore[nod * 2] + arbore[nod * 2 + 1];
}

int main()
{
    vector<int> rang(N);
    rezultat.resize(N);
    in >> N;
    for(int i = 1; i <= N; i++){
        in >> rang[i];
    }

    BUILD(1, 1, N);

    for(int i = N; i >= 1; i--){
        QUERY(1, 1, N, rang[i], i);
    }

    for(int i = 1; i <= N; i++)
        out << rezultat[i] << '\n';
    return 0;
}