Cod sursa(job #602209)

Utilizator maritimCristian Lambru maritim Data 9 iulie 2011 19:31:58
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<stdio.h>

#define MaxN 30100
#define MaxEl 200100
#define lf (2 * nod)
#define rf (2 * nod) + 1
#define mij (i + j) / 2
#define INF 123120123
#define FaraSumerf - SAI[rf]
#define FaraSumelf - SAI[lf]

int A[MaxN];
int VAI[MaxEl];
int PAI[MaxEl];
int SAI[MaxEl];
int N;

void citire(void)
{
	FILE *f = fopen("schi.in","r");
	
	fscanf(f,"%d ",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%d ",&A[i]);
	
	fclose(f);
}

int min(int a,int b)
{
	return a<b ? a:b;
}

void build(int nod,int i,int j)
{
	if(i == j)
	{
		VAI[nod] = A[i];
		PAI[nod] = i;
		return ;
	}
	
	build(lf , i , mij);
	build(rf , mij + 1 , j);
	
	if(VAI[rf] <= VAI[lf])
	{
		VAI[nod] = VAI[rf];
		PAI[nod] = PAI[rf];
	}
	else
	{
		VAI[nod] = VAI[lf];
		PAI[nod] = PAI[lf];
	}
}

void update(int nod,int i,int j,int a,int b)
{
	if(i != j)
	{
		SAI[lf] += SAI[nod];
		SAI[rf] += SAI[nod];
		VAI[nod] -= SAI[nod];
		SAI[nod] = 0;
	}
	else
		VAI[nod] -= SAI[nod];
	if(a <= i && j <= b)
	{
		SAI[nod] = 1;
		return ;
	}
	
	if(a <= mij)
		update(lf , i , mij , a , b);
	if(b > mij)
		update(rf , mij + 1 , j , a , b);
	
	if(VAI[rf] FaraSumerf <= VAI[lf] FaraSumelf)
	{
		VAI[nod] = VAI[rf] FaraSumerf;
		PAI[nod] = PAI[rf];
	}
	else
	{
		VAI[nod] = VAI[lf] FaraSumelf;
		PAI[nod] = PAI[lf];
	}		
}

void querry(int nod,int i,int j,int a)
{
	if(i == j)
	{
		VAI[nod] = INF;
		return ;
	}
	
	if(a <= mij)
		querry(lf , i , mij , a);
	else
		querry(rf , mij + 1 , j , a);
	
	if(VAI[rf] FaraSumerf <= VAI[lf] FaraSumelf)
	{
		VAI[nod] = VAI[rf] FaraSumerf;
		PAI[nod] = PAI[rf];
	}
	else
	{
		VAI[nod] = VAI[lf] FaraSumelf;
		PAI[nod] = PAI[lf];
	}		
}

int main()
{
	FILE *g = fopen("schi.out","w");
	citire();
	build(1,1,N);
	for(int i=1;i<=N;i++)
	{
		fprintf(g,"%d\n",PAI[1]);
		update(1,1,N,PAI[1],N);
		querry(1,1,N,PAI[1]);
	}
	
	fclose(g);
	return 0;
}