Cod sursa(job #3326513)

Utilizator Victor321321Victor Casandra Victor321321 Data 29 noiembrie 2025 11:56:51
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int clasament[300005];

struct SegTree
{
    int n;
    vector<long long> tree;
    void init(int _n)
    {
        n=_n;
        tree.assign(4 * n + 4, 0);
    }
    void build(const vector<long long> &a, int node, int l, int r)
    {
        if (l == r)
        {
            tree[node] = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(a, node * 2, l, mid);
        build(a, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    void build(const vector<long long> &a)
    {
        build(a, 1, 1, n);
    }
    void pointUpdate(int node, int l, int r, int pos, long long val)
    {
        if (l == r)
        {
            tree[node] = 0;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid)
            pointUpdate(node * 2, l, mid, pos, val);
        else
            pointUpdate(node * 2 + 1, mid + 1, r, pos, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    void pointUpdate(int pos, long long val)
    {
        pointUpdate(1, 1, n, pos, val);
    }
    long long rangeQuery(int nod, int st, int dr, int k)
    {
        if (st == dr)
        {
            return st;
        }
        else
        {
            int mij = (st + dr) / 2;
            if (tree[nod * 2] >= k)
            {
                return rangeQuery(nod * 2, st, mij, k);
            }
            else
            {
                return rangeQuery(nod * 2 + 1, mij + 1, dr, k - tree[nod * 2]);
            }
        }
    }
    long long rangeQuery(int l)
    {
        return rangeQuery(1, 1, n, l);
    }
};
int main()
{
    int n, q;
    fin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
    SegTree ST;
    ST.init(n);
    ST.build(a);
    for (int i = n; i >= 1; --i)
    {
        int poz = ST.rangeQuery(a[i]);
        clasament[poz] = i;
        ST.pointUpdate(poz, 0);
    }
    for(int i = 1; i <= n; ++i)
    {
        fout << clasament[i] << "\n";
    }
    return 0;
}