Cod sursa(job #3198417)

Utilizator PescarusTanislav Luca Andrei Pescarus Data 29 ianuarie 2024 11:25:48
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
using namespace std;
const int nmax = 30005;
int arbi[3 * nmax];
int v[nmax], sol[nmax];
void build(int node, int st, int dr){
    if(st == dr){
        arbi[node] = 1;
        return;
    }
    int mid = (st + dr) / 2;
    build(2 * node, st, mid);
    build(2 * node + 1, mid + 1, dr);
    arbi[node] = arbi[2 * node] + arbi[2 * node + 1];
}
int query(int node, int st, int dr, int x){
    if(st == dr){
        return st;
    }
    int mid = (st + dr) / 2;
    if(x <= arbi[2 * node]){
        return query(2 * node, st, mid, x);
    }
    else{
        return query(2 * node + 1, mid + 1, dr, x - arbi[2 * node]);
    }
}

void update(int node, int st, int dr, int x){
    if(st == dr){
        arbi[node] = 0;
        return;
    }
    int mid = (st + dr) / 2;
    if(x <= mid){
        update(2 * node, st, mid, x);
    }
    else{
        update(2 * node + 1, mid + 1, dr, x);
    }
    arbi[node] = arbi[2 * node] + arbi[2 * node + 1];
}
int main(){
    ifstream f("schi.in");
    ofstream g("schi.out");
    int n;
    f >> n;
    for(int i = 1;  i <= n; i++){
        f >> v[i];
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--){
        int poz = query(1, 1, n, v[i]);
        sol[poz] = i;
        update(1, 1, n, poz);
    }
    for(int i = 1; i <= n; i++){
        g << sol[i] << '\n';
    }
}