Cod sursa(job #2901882)

Utilizator Mendea_IanisMendea Ianis Teodor Mendea_Ianis Data 14 mai 2022 18:08:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

int A[150005],V[30005],n,M[30005];

void build(int nod,int st,int dr)
{
    if(st == dr)
    {
        A[nod] = 1;
        return;
    }

    int mid = (st+dr)/2;

    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);

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

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

void update(int nod,int st,int dr,int poz)
{
    if(st == dr)
    {
        A[nod]--;
        return;
    }
    int mid = (st+dr)/2;
    if(poz<=mid)
        update(2*nod,st,mid,poz);
    else
        update(2*nod+1,mid+1,dr,poz);
    A[nod] = A[2*nod] + A[2*nod+1];
}

int main()
{
    fin>>n;
    for(int i = 1;i<=n;i++)
    {
        fin>>V[i];
    }
    build(1,1,n);
    for(int i = n;i>=1;i--)
    {
        int poz = query(1,1,n,V[i]);
        update(1,1,n,poz);
        M[poz] = i;
    }
    for(int i = 1;i<=n;i++)
        fout<<M[i]<<'\n';



}