Cod sursa(job #3239946)

Utilizator Victor321321Victor Casandra Victor321321 Data 9 august 2024 14:52:11
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, clasament[300005], a[300005], aint[1200005];


void build(int nod, int st, int dr)
{
    if (st == dr)
    {
        aint[nod] = 1;
    }
    else
    {
        int mij = (st + dr) / 2;
        build(nod * 2, st, mij);
        build(nod * 2 + 1, mij + 1, dr);
        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }
}

void update(int nod, int st, int dr, int poz)
{
    if (st == dr)
    {
        aint[nod] = 0;
    }
    else
    {
        int mij = (st + dr) / 2;
        if (poz <= mij)
        {
            update(nod * 2, st, mij, poz);
        }
        else
        {
            update(nod * 2 + 1, mij + 1, dr, poz);
        }
        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }
}

int query(int nod, int st, int dr, int k)
{
    if (st == dr)
    {
        return st;
    }
    else
    {
        int mij = (st + dr) / 2;
        if (aint[nod * 2] >= k)
        {
            return query(nod * 2, st, mij, k);
        }
        else
        {
            return query(nod * 2 + 1, mij + 1, dr, k - aint[nod * 2]);
        }
    }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i];
    build(1, 1, n);
    for (int i = n; i >= 1; --i)
    {
        int poz = query(1, 1, n, a[i]);
        clasament[poz] = i;
        update(1, 1, n, poz);
    }
    for(int i = 1; i <= n; ++i)
    {
        fout << clasament[i] << "\n";
    }
    return 0;
}