Mai intai trebuie sa te autentifici.

Cod sursa(job #1767476)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 29 septembrie 2016 11:15:27
Problema Schi Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2140000000
#define MaxT 66000
#define MaxN 30001
#define MAX 131072
using namespace std;

FILE *IN,*OUT;
int N,pos=0,v[MaxN],out=0,sign,Ans;
char f[MAX],Out[MAX],str[10];

struct _Tree
{
	int Min,Lower,Pos;
}T[MaxT];

inline void Write_Ch(char ch)
{
	Out[out++]=ch;
	if(out==MAX)
		fwrite(Out,MAX,1,OUT),out=0;
}
inline void Write_Int(int nr)
{
	int x=0;
	if(nr<0)Write_Ch('-'),nr=-nr;
	do
	{
		str[x++]=nr%10+'0';
		nr/=10;
	}
	while(nr);
	while(x>0)
		Write_Ch(str[--x]);
}
inline int max2(int a,int b)
{
	if (a>b) return a;
	else return b;
}
inline void Read(int &nr)
{
	sign=0;
	nr=0;
	while(f[pos]<'0'||f[pos]>'9')
	{
		if(f[pos]=='-')sign=1;
		pos++;
		if(pos==MAX)
			fread(f,MAX,1,IN),pos=0;
	}
	while(f[pos]>='0'&&f[pos]<='9')
	{
		nr=10*nr+f[pos++]-'0';
		if(pos==MAX)
			fread(f,MAX,1,IN),pos=0;
	}
	if(sign)nr=-nr;
}

void DFS(int node,int start,int end)
{
	if(start==end)
		T[node].Lower=0,T[node].Min=v[start],T[node].Pos=start;
	else
	{
		DFS(node*2,start,(start+end)/2);
		DFS(node*2+1,(start+end)/2+1,end);
		T[node].Min=T[node*2].Min,T[node].Pos=T[2*node].Pos;
		if(T[node].Min>=T[2*node+1].Min)T[node].Min=T[node*2+1].Min,T[node].Pos=T[2*node+1].Pos;
	}
}
void Update(int node,int start,int end)
{
	if(start==end)
	{
		T[node].Min=INF;
		return;
	}
	else
	{
		int mid=(start+end)/2;
		if(T[node*2].Min<T[node*2+1].Min)
		{
			T[2*node+1].Lower++;
			T[2*node+1].Min--;
			Update(2*node,start,mid);
		}
		else Update(2*node+1,mid+1,end);
	}
	T[node].Min=T[2*node].Min,T[node].Pos=T[2*node].Pos;
	if(T[node].Min>=T[node*2+1].Min)T[node].Min=T[2*node+1].Min,T[node].Pos=T[2*node+1].Pos;
}
int main()
{
    IN=fopen("schi.in","r");
	OUT=fopen("schi.out","w");

	fread(f,1,MAX,IN);
	Read(N);
	for(int i=1;i<=N;i++)
		Read(v[i]);
	DFS(1,1,N);
	for(int i=1;i<=N;i++)
	{
		Ans=T[1].Pos;
		Update(1,1,N);
		Write_Int(Ans);
		Write_Ch('\n');
	}
	if(out>0)fwrite(Out,1,out,OUT);
    return 0;
}