Cod sursa(job #3248502)

Utilizator CaldareaCiprianCaldarea Ciprian CaldareaCiprian Data 12 octombrie 2024 09:13:20
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;

using VI = vector<int>;

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

VI sgt;
int sum = 0;
int found = 0;
void Update(int nod, int l, int r, int poz)
{
    if (l == r)
    {
        sgt[nod] = 0;
        return;
    }

    int mid = (l + r) / 2;
    if (poz <= mid)
        Update(nod * 2, l, mid, poz);
    else
        Update(nod * 2 + 1, mid + 1, r, poz);

    sgt[nod] = sgt[nod * 2] + sgt[nod * 2 + 1];

}

void Build(int nod, int l, int r)
{
    if (l == r)
    {
        sgt[nod] = 1;
        return;
    }

    int mid = (l + r) / 2;
    Build(nod * 2, l, mid);
    Build(nod * 2 + 1, mid + 1, r);
    sgt[nod] = sgt[nod * 2] + sgt[nod * 2 + 1];

}

/*
void Query(int nod, int l, int r, int st, int dr)
{
    if (st <= l && r <= dr)
    {
        sum += sgt[nod];
        return;
    }

    int mid = (l + r) / 2;
    if (st <= mid)
        Query(nod * 2, l, mid, st, dr);

    if (dr > mid)
        Query(nod * 2 + 1, mid + 1, r, st, dr);
}
*/

void Find(int nod, int l, int r, int val)
{
    if (l == r)
    {
        found = l;
        sgt[nod] = 0;
        return;
    }
    int mid = (l + r) / 2;
    if (sum + sgt[nod * 2] < val)
    {
        sum += sgt[nod * 2];
        Find(nod * 2 + 1, mid + 1, r, val);
    }
    else
        Find(nod * 2, l, mid, val);

    sgt[nod] = sgt[nod * 2] + sgt[nod * 2 + 1];

}
int main()
{
    int n;
    fin >> n;
    sgt = VI(4 * n + 10);
    Build(1, 1, n);
    sum = 0;
    VI v(n + 1), poz(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
    }

    for (int i = n; i >= 1; --i)
    {

        found = 0;
        sum = 0;
        Find(1, 1, n, v[i]);
        poz[found] = i;
    }


    for (int i = 1; i <= n; ++i)
        fout << poz[i] << '\n';


}