Cod sursa(job #2945335)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 23 noiembrie 2022 18:31:11
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[120005];

/**
1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1
2 1 3 1 1 1 1 1
2 1 3 4 1 1 1 1
2 1 3 5 4 1 1 1
3 1 4 6 5 2 1 1
4 2 5 7 6 3 1 1
5 2 6 8 7 4 1 3

**/

void update (int nod, int st, int dr, int pos, int val)
{
    if (st == dr)
    {
        a[nod] += val;
        return;
    }

    int mid = (st + dr) / 2;
    if (pos <= mid)
        update(2*nod, st, mid, pos, val);
    else
        update(2*nod+1, mid+1, dr, pos, val);

    a[nod] = a[2*nod] + a[2*nod+1];
}

int query (int nod, int st, int dr, int l, int r)
{
    if (l <= st && dr <= r)
        return a[nod];
    int mid = (st + dr) / 2;

    int ret = 0;
    if (l <= mid)
        ret += query(2*nod, st, mid, l, r);
    if (mid < r)
        ret += query(2*nod+1, mid+1, dr, l, r);

    return ret;
}

int b[30001];
int ans[30001];

int main()
{
    int n;
    in >> n;

    for (int i=1; i<=n; i++)
    {
        in >> b[i];
        update(1, 1, n, i, 1);
    }

    for (int i=n; i>0; i--)
    {
        int l=1, r=n;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (query(1, 1, n, 1, mid) >= b[i])
                r = mid;
            else
                l = mid + 1;
        }

        update(1, 1, n, r, -1);

        ans[r] = i;
    }

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

    return 0;
}