Cod sursa(job #2011735)

Utilizator ioanadarcCristina Arc ioanadarc Data 17 august 2017 00:33:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#define Nmax 30005
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int arb[4*Nmax], b[Nmax], a[Nmax], N;
void upd(int nod, int l, int r, int poz, int val)
{
    int mid = (l + r)/2;
    if(l == r)
    {
        arb[nod] = val;
        return;
    }
    if(poz <= mid)
        upd(nod * 2, l, mid, poz, val);
    else upd(nod *2 + 1, mid+1, r, poz, val);
    arb[nod] = arb[2*nod] + arb[2*nod + 1];
}
void qu(int nod,int l, int r, int poz, int pact, int val)
{
    int mid = (l + r)/2;
    if(l == r)
    {
        b[l] = val;
        upd(1, 1, N, l, 0);
        return;
    }
    if(poz <= pact + arb[2*nod])
        qu(2*nod, l, mid, poz, pact, val);
    else qu(2*nod + 1, mid + 1, r, poz, pact+arb[2*nod], val);
}
int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
        fin >> a[i];
    for(int i = 1; i <= N; i++)
        upd(1, 1, N, i, 1);
    for(int i = N; i >= 1; i--)
        qu(1, 1, N, a[i], 0, i);//gaesc a a[i] a pozitie nefolosita
    for(int i = 1; i <= N; i++)
        fout << b[i] << "\n";
    return 0;
}