Cod sursa(job #3351623)

Utilizator cristiz123456Zoescu Cristian cristiz123456 Data 20 aprilie 2026 16:31:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 30000;
int n;

struct aint
{
    int n;
    vector <int> tree;
    void init(int n, int v[])
    {
        this->n = n;
        tree.resize(4* n + 5);
    }
    void update(int node, int le, int ri, int pos, int val)
    {
        if(le == ri)
        {
            tree[node] += val;
            return;
        }
        int mid = (le + ri) / 2;
        if(pos <= mid)
        {
            update(2 * node, le, mid, pos, val);
        }
        else
        {
            update(2 * node + 1, mid + 1, ri, pos, val);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    void update(int pos)
    {
        update(1, 1, n, pos, 1);
    }
    void query(int node, int le, int ri, int a, int b, int &accum)
    {
        if(a <= le && b >= ri)
        {
            accum = accum + tree[node];
            return;
        }
        int mid = (le + ri) / 2;
        if(a <= mid)
        {
            query(2 * node, le, mid, a, b, accum);
        }
        if(b > mid)
        {
            query(2 * node + 1, mid + 1, ri, a, b, accum);
        }
    }
    int query(int a, int b)
    {
        int accum = 0;
        query(1, 1, n, a, b, accum);
        return accum;
    }
};

aint t;
int v[N + 1], x[N + 1];
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int i, b, st, dr, mij;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    t.init(n, v);
    for(i = n; i > 0; i--)
    {
        st = 1;
        dr = n;
        while(st <= dr)
        {
            mij = (st + dr) / 2;
           // printf("%d %d %d\n",mij, t.query(1, mij),v[i]);
            if(mij - t.query(1, mij) < v[i])
            {
                st = mij + 1;
            }
            else
            {
                b = mij;
                dr = mij - 1;
            }
        }
        //printf("%d\n\n", b);
        x[b] = i;
        t.update(b);
    }
    for(i = 1; i <= n; i++)
    {
        cout << x[i] << "\n";
    }
    return 0;
}