Cod sursa(job #3364031)

Utilizator prodsevenStefan Albu prodseven Data 27 august 2026 14:29:58
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

int n;
vector<int> queries, ans;

class Segment_Tree {
    vector<int> tree;
    int size;
    void _build(int node, int left, int right) {
        if (left == right) {
            tree[node] = 1;
            return;
        }
        int middle = (left + right) / 2;
        _build(2 * node, left, middle);
        _build(2 * node + 1, middle + 1, right);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    void _update(int node, int left, int right, int pos) {
        if (left == right) {
            tree[node] = 0;
            return;
        }
        int middle = (left + right) / 2;
        if (pos <= middle) {
            _update(2 * node, left, middle, pos);
        } else {
            _update(2 * node + 1, middle + 1, right, pos);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    int _query(int node, int left, int right, int k) {
        if (left == right) {
            return left;
        }
        int middle = (left + right) / 2;
        if (k <= tree[2 * node]) {
            return _query(2 * node, left, middle, k);
        }
        return _query(2 * node + 1, middle + 1, right, k - tree[2 * node]);
    }
public:
    Segment_Tree(int size) {
        this->size = size;
        tree.assign(4 * size + 2, 0);
        _build(1, 1, size);
    }
    void update(int pos) {
        _update(1, 1, size, pos);
    }
    int query(int k) {
        return _query(1, 1, size, k);
    }
};

int main() {
    cin >> n;
    queries.assign(n + 2, 0);
    ans.assign(n + 2, 0);
    for (int i = 1 ; i <= n ; ++i) {
        cin >> queries[i];
    }
    Segment_Tree t(n);
    for (int i = n ; i >= 1 ; --i) {
        int pos = t.query(queries[i]);
        ans[pos] = i;
        t.update(pos);
    }
    for (int i = 1 ; i <= n ; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}