Cod sursa(job #2849114)

Utilizator MR0L3eXMaracine Constantin Razvan MR0L3eX Data 14 februarie 2022 16:12:26
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include "bits/stdc++.h"

using namespace std;

using ld = long double;
using ll = long long;
using ull = unsigned long long;

#if defined(ONPC)
#include "bits/debug.h"
#endif

int n;
vector<int> sgt, ans;

void bld(int node = 0, int l = 0, int r = n - 1) {
    if (l == r) {
        sgt[node] = 1;
        return;
    }
    int m = (l + r) / 2;
    bld(2 * node + 1, l, m);
    bld(2 * node + 2, m + 1, r);
    sgt[node] = sgt[2 * node + 1] + sgt[2 * node + 2];
}

void upd(int p, int val, int node = 0, int l = 0, int r = n - 1) {
    if (l == r) {
        ans[l] = val;
        sgt[node] = 0;
        return;
    }
    int m = (l + r) / 2;
    if (sgt[2 * node + 1] >= p) {
        upd(p, val, 2 * node + 1, l, m);
    } else {
        upd(p - sgt[2 * node + 1], val, 2 * node + 2, m + 1, r);
    }
    sgt[node]--;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    cin >> n;
    ans.resize(n);
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) {
        cin >> pos[i];
    }

    int sgt_size = 1;
    while (sgt_size < n) sgt_size *= 2;
    sgt.resize(2 * sgt_size);

    bld();
    for (int i = n - 1; i >= 0; --i) {
        upd(pos[i], i);
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] + 1 << "\n";
    }
}