Cod sursa(job #584194)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 24 aprilie 2011 15:11:25
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
using namespace std;

const int NMAX=30000;
int ai[2*NMAX-1];

int query(int nod, int left, int right, int val)
{
	--ai[nod];
	if(left==right)
		return left;
	int mij=left+(right-left)/2;

	if(ai[2*nod+1]>=val)
		return query(2*nod+1,left,mij,val);
	return query(2*nod+2,mij+1,right,val-ai[2*nod+1]);
}

void init(int nod, int left, int right)
{
	if(left==right)
	{
		ai[nod]=1;
		return;
	}
	int mij=left+(right-left)/2;

	init(2*nod+1,left,mij);
	init(2*nod+2,mij+1,right);
	ai[nod]=ai[2*nod+1]+ai[2*nod+2];
}

int main()
{
	ifstream in("schi.in");
	ofstream out("schi.out");

	int n,v[NMAX];
	in>>n;
	for(int i=0;i<n;i++)
		in>>v[i];
	init(0,0,n-1);//init interval tree
/*
	int solution[NMAX];
	for(int i=n-1;i>=0;i--)
	{
		int rez=query(0,0,n-1,v[i]);
		solution[rez]=i+1;
	}
	for(int i=0;i<n;i++)
		out<<solution[i]<<"\n";
	in.close();
	out.close();*/
}