Cod sursa(job #3367613)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 8 octombrie 2026 21:45:45
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

int v[30005], aint[120005];
int sol[30005];

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

void update(int l, int r, int x, int poz, int val)
{
    if (l == r)
    {
        aint[x] -= val;
        return;
    }
    int mid = (l + r) / 2;
    if (poz <= mid)
    {
        update(l, mid, 2 * x, poz, val);
    }
    else
    {
        update(mid + 1, r, 2 * x + 1, poz, val);
    }
    aint[x] = aint[2 * x] + aint[2 * x + 1];
}

int query(int l, int r, int x, int liml, int limr)
{
    if (l > limr || r < liml)
    {
        return 0;
    }
    if (liml <= l && limr >= r)
    {
        return aint[x];
    }
    int mid = (l + r) / 2;
    return query(l, mid, 2 * x, liml, limr) + query(mid + 1, r, 2 * x + 1, liml, limr);
}

int main() 
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
	int n, m; cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> v[i];
    }
    build(1, n, 1);
    for(int i = n; i >= 1; i--) {
        int st = 1;
        int dr = n;
        int pos = 0;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(query(1, n, 1, 1, mid) > v[i]) {
                dr = mid - 1;
            } else {
                if(query(1, n, 1, 1, mid) < v[i]) {
                    st = mid + 1;
                } else {
                    pos = mid;
                    dr = mid - 1;
                }
            }
        }
        sol[pos] = i;
        update(1, n, 1, pos, 1);
    }
    for(int i = 1; i <= n; i++) {
        cout << sol[i] << ' ';
    }
    
}