Cod sursa(job #2015849)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 27 august 2017 19:48:31
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#define DM 30001
#include <fstream>
using namespace std;

ifstream fi ("schi.in");
ofstream fo ("schi.out");
int n, v[DM], arb[4*DM], rasp[DM];

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

void update_pe_steroizi(int nod, int st, int dr, int poz, int val)
{
	if (st == dr)
	{
		rasp[st] = val;
		arb[nod] = 0;
		return;
	}
	int mid = (st + dr)/2;
	if (arb[nod*2] >= poz)
		update_pe_steroizi(nod*2, st, mid, poz, val);
	else
		update_pe_steroizi(nod*2 + 1, mid + 1, dr, poz - arb[nod*2], val);
	arb[nod] = arb[nod*2] + arb[nod*2+1];
}

int main()
{
	fi >> n;
	for (int i = 1; i <= n; ++i)
		fi >> v[i];
	for (int i = 1; i <= n; ++i)
		update(1, 1, n, i, 1);
	for (int i = n; i >= 1; --i)
		update_pe_steroizi(1, 1, n, v[i], i);
	for (int i = 1; i <= n; ++i)
		fo << rasp[i] << '\n';
	return 0;
}