Cod sursa(job #3246115)

Utilizator ioanabaduIoana Badu ioanabadu Data 1 octombrie 2024 21:17:29
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int aint[120005], ans[30005], arr[30005];

void build (int idx, int st, int dr){
    if (st == dr){
        aint[idx] = 1; // loc liber in arbore pentru un schior
        return;
    }

    int mij = (st + dr) / 2;
    build (idx*2, st, mij);
    build(idx*2+1, mij+1, dr);
    aint[idx] = aint[idx*2] + aint[idx*2+1];
}

void update (int idx, int st, int dr, int value, int pos){ 
    if (st == dr){
        aint[idx] = 0; // nu mai e loc liber
        ans[st] = value;
        return;
    }

    int mij = (st + dr) / 2;
    if (aint[2*idx] >= pos) update(2*idx, st, mij, value, pos); // incerc sa o pun cat mai in stanga dupa cate locuri libere sunt in arbore
    else update(2*idx+1, mij+1, dr, value, pos-aint[idx*2]);
    aint[idx] = aint[idx*2] + aint[idx*2+1];
}

int main (){
    in >> n;
    for (int i=1; i<=n; ++i)
        in >> arr[i];

    build(1, 1, n);
    for (int i=n; i>=1; --i)
        update(1, 1, n, i, arr[i]);

    for (int i=1; i<=n; ++i)
        out << ans[i] << '\n';

    return 0;
}