Cod sursa(job #3362988)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 13 august 2026 12:07:15
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>
using namespace std;

int n;

struct SegTree {
    vector<int> aint;
    SegTree(vector<int>& v) {
        aint.resize(4 * (n + 1));
        build(v);
    }
    int query(vector<int>& v, int a, int b, int i = 1, int j = n, int idx = 1) {
        if (i == a && j == b)
            return aint[idx];
        int mid = i + (j - i) / 2;
        if (b <= mid)
            return query(v, a, b, i, mid, 2 * idx);
        if (mid < a)
            return query(v, a, b, mid + 1, j, 2 * idx + 1);
        return query(v, a, mid, i, mid, 2 * idx)
             + query(v, mid + 1, b, mid + 1, j, 2 * idx + 1);
    }
    void update(vector<int>& v, int a, int x, int i = 1, int j = n, int idx = 1) {
        if (i == j) {
            aint[idx] = v[i] = x;
            return;
        }
        int mid = i + (j - i) / 2;
        if (a <= mid) {
            update(v, a, x, i, mid, 2 * idx);
        } else {
            update(v, a, x, mid + 1, j, 2 * idx + 1);
        }
        aint[idx] = aint[2 * idx] + aint[2 * idx + 1];
    }
private:
    void build(vector<int>& v, int i = 1, int j = n, int idx = 1) {
        if (i == j) {
            aint[idx] = v[i];
            return;
        }
        int mid = i + (j - i) / 2;
        build(v, i, mid, 2 * idx);
        build(v, mid + 1, j, 2 * idx + 1);
        aint[idx] = aint[2 * idx] + aint[2 * idx + 1];
    }
};

signed main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
#endif

    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    vector<int> a(n + 1, 1), ans(n + 1);
    SegTree aint(a);
    for (int i = n; i >= 1; --i) {
        int st = 1, dr = n, rasp = -1;
        while (st <= dr) {
            int mid = (st + dr) / 2;
            if (aint.query(a, 1, mid) < v[i]) {
                st = mid + 1;
            } else {
                dr = mid - 1;
                rasp = mid;
            }
        }
        ans[rasp] = i;
        aint.update(a, rasp, 0);
    }

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

    return 0;
}