Cod sursa(job #1618074)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 27 februarie 2016 18:06:07
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int Nmax = 30002;

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

int n;
int arb[4*Nmax], d[Nmax], s[Nmax];
int x, y, val, sol;

void Build(int nod, int l, int r);
void Update(int nod, int l, int r);
void Query(int nod, int l, int r);

int main()
{
    fin >> n;

    for (int i = n; i >= 1; --i)
        fin >> d[i];

    Build(1, 1, n);

    for (int i = 1; i <= n; ++i)
    {
        sol = 0;
        val = d[i];
        Query(1, 1, n);
        Update(1, 1, n);

        s[sol] = n - i + 1;

    }


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


    fin.close();
    fout.close();
    return 0;
}

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

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

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

void Update(int nod, int l, int r)
{
    if (l == r)
    {
        arb[nod] = 0;
        return;
    }
    int mid = (l + r) / 2;

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

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

void Query(int nod, int l, int r)
{
    if (l == r)
    {
        sol = l;
        return;
    }
    int mid = (l + r) / 2;
    if (arb[2*nod] >= val)
        Query(2*nod, l, mid);
    else
    {
        val -= arb[2*nod];
        Query(2*nod+1, mid+1, r);
    }
}