Cod sursa(job #3259644)

Utilizator SilviuC25Silviu Chisalita SilviuC25 Data 27 noiembrie 2024 09:59:28
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX_NUM = 3e4 + 5;

int a[MAX_NUM], tree[4 * MAX_NUM];
map<int, int> answer;

void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node + 1, l, mid);
    build(2 * node + 2, mid + 1, r);
    tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}

void update(int node, int l, int r, int queryR, int pos) {
    if (l == r) {
        tree[node] = 0;
        answer[l + 1] = pos;
        return;
    }
    int mid = (l + r) / 2;
    if (tree[2 * node + 1] > queryR) {
        update(2 * node + 1, l, mid, queryR, pos);
    } else {
        update(2 * node + 2, mid + 1, r, queryR - tree[2 * node + 1], pos);
    }
    tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build(0, 0, n - 1);
    for (int i = n - 1; i >= 0; --i) {
        update(0, 0, n - 1, a[i] - 1, i + 1);
    }
    for (int i = 1; i <= n; ++i) {
        cout << answer[i] << "\n";
    }
    return 0;
}