Cod sursa(job #3000163)

Utilizator alexgroparuObada Alex alexgroparu Data 12 martie 2023 01:26:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <vector>
using namespace std;

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

using VI = vector<int>;

#define left (2 * x)
#define right (2 * x + 1)

VI arb, sol, sir;
int n;

void Build(int x, int st, int dr);
int Query(int x, int st, int dr, int X);
void Update(int x, int st, int dr, int poz);

int main()
{
    fin >> n;
    arb = VI(4 * n + 1);
    sol = sir = VI(n + 1);

    for(int i = 1; i <= n; ++i)
        fin >> sir[i];
        
    Build(1, 1, n);

    for(int loc, i = n; i > 0; --i)
    {
        loc = Query(1, 1, n, sir[i]);
        Update(1, 1, n, loc);
        sol[loc] = i;
    }

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

    return 0;
}


void Build(int x, int st, int dr)
{
    if(st == dr)
    {
        arb[x] = 1;
        return;
    }

    int mid = (st + dr) >> 1;
    Build(left, st, mid);
    Build(right, mid + 1, dr);

    arb[x] = arb[left] + arb[right];
}

int Query(int x, int st, int dr, int X)
{
    if(st == dr)
        return st;

    int mid = (st + dr) >> 1;

    if(arb[left] >= X)
        return Query(left, st, mid, X);
    else
    {
        X -= arb[left];
        return Query(right, mid + 1, dr, X);
    }
}

void Update(int x, int st, int dr, int poz)
{
    if(st == dr)
    {
        arb[x] = 0;
        return;
    }

    int mid = (st + dr) >> 1; 
    if(mid >= poz)
        Update(left, st, mid, poz);
    else
        Update(right, mid + 1, dr, poz);

    arb[x] = arb[left] + arb[right];
}