Cod sursa(job #2950945)

Utilizator SabrinaGiuliaMacoveiciuc Sabrina Giulia SabrinaGiulia Data 4 decembrie 2022 21:38:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[120005], b[30001], rez[30001];

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

    int mijl = (st + dr) / 2;
    if (pos <= mijl)
        reseteaza(2*nod, st, mijl, pos, val);
    else
        reseteaza(2*nod+1, mijl+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 main()
{
    int n,i,l,r;
    f >> n;
    for (i=1; i<=n; i++)
    {
        f >> b[i];
        reseteaza(1, 1, n, i, 1);
    }

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

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

        rez[r] = i;
    }

    for(i=1;i<=n;i++)
        g<<rez[i]<<'\n';

    return 0;
}