Cod sursa(job #2107957)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 17 ianuarie 2018 20:15:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;

const int dim = 30005;

int v[dim], seg_tree[4 * dim], sol[dim];

void create(int node, int lef, int rig, int pos) {
    if (lef == rig) {
        seg_tree[node] = 1;
        return;
    }

    int mid = (lef + rig) / 2;
    if (pos <= mid)
        create(2*node, lef, mid, pos);
    else
        create(2*node+1, mid+1, rig, pos);

    seg_tree[node] = seg_tree[2*node] + seg_tree[2*node + 1];
}

void find(int node, int lef, int rig, int pos, int curr) {
    if (lef == rig) {
        seg_tree[node] = 0;
        sol[lef] = curr;
        return;
    }

    int mid = (lef + rig) / 2;
    if (pos <= seg_tree[2*node])
        find(2*node, lef, mid, pos, curr);
    else
        find(2*node+1, mid+1, rig, pos - seg_tree[2*node], curr);

    seg_tree[node] = seg_tree[2*node] + seg_tree[2*node + 1];
}

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        create(1, 1, n, i);
    }

    for (int i = n; i; --i)
        find(1, 1, n, v[i], i);

    for (int i = 1; i <= n; ++i)
        cout << sol[i] << '\n';
}

int main() {
    assert(freopen("schi.in", "r", stdin));
    assert(freopen("schi.out", "w", stdout));
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}