Cod sursa(job #2972971)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 30 ianuarie 2023 18:49:27
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>
#define GCC optimize ("O3")
#define GCC target ("popcnt")

using namespace std;

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

const int MAX_N = 30'000;
int n, place[MAX_N + 5], sol[MAX_N + 5];

struct SEGTREE{
    int aint[4 * MAX_N + 5];

    inline void build(int nod=1, int st=1, int dr=n){
        if(st == dr){
            aint[nod] = 1;
        }else{
            int md = ((st + dr) >> 1);
            build(2*nod, st, md);
            build(2*nod+1, md+1, dr);
            aint[nod] = aint[2*nod] + aint[2*nod+1];
        }
        return;
    }

    inline void update(int poz, int val, int nod=1, int st=1, int dr=n){
        if(st == dr){
            aint[nod] = 0;
            sol[st] = val;
        }else{
            int md = ((st + dr) >> 1);
            if(aint[2*nod] >= poz)
                update(poz, val, 2*nod, st, md);
            else
                update(poz - aint[2*nod], val, 2*nod+1, md+1, dr);
            aint[nod] = aint[2*nod] + aint[2*nod+1];
        }
        return;
    }
} tree;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>place[i];

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

    for(int i=1; i<=n; i++)
        fout<<sol[i]<<"\n";
    return 0;
}
/**
8
1 1 3 4 4 2 1 3
**/