Cod sursa(job #1676520)

Utilizator DacianBocea Dacian Dacian Data 5 aprilie 2016 22:58:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
using namespace std;
int ARB[400000],S[400000],V[30001], N, M, a, b, c, val;
void update(int nod, int left, int right,int t){
	if (left == right){ ARB[nod] = val; return; }
	int  m = (left + right) / 2;
	if (t <= m)update(2 * nod, left, m,t);
	else update(2 * nod + 1, m + 1, right,t);
	ARB[nod] = ARB[2 * nod] + ARB[2 * nod + 1];
}
int q(int nod, int left, int right,const int& val1){
	{
		if (left == right)
		{
			return left;
		}

		int div = (left + right) / 2;
		if (ARB[nod<<1] >= val1) return q(2 * nod, left, div,val1);
		else return q(2 * nod + 1, div + 1, right, val1-ARB[nod<<1]);
	}
}
int main(){
	ofstream of("schi.out");
	ifstream f("schi.in");
	f >> N;
	for (int i = 1; i <= N; ++i){
		f >> V[i];
		val = 1;
		update(1, 1, N,i);
	}
	for (int i = N; i >0; --i){
		V[i] = q(1,1,N,V[i]);
		val = 0;
		update(1, 1, N, V[i]);
		S[V[i]] = i;
	}
	for (int i = 1; i <= N; ++i)of << S[i] << "\n";
}