Cod sursa(job #342556)

Utilizator irene_mFMI Irina Iancu irene_m Data 22 august 2009 12:55:43
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream.h>
#define MaxN 100009
#define t(x)	((x)/2)
#define fs(x)	((x)*2)
#define fd(x)	((x)*2+1)

long d[MaxN],l[MaxN],T[MaxN],pos[MaxN],heap[MaxN],T_max,X,L,n,s,k,N;

void cit()
{
	int i;
	ifstream fin("lupu.in");
	fin>>n>>X>>L;
	for(i=1;i<=n;i++)
		fin>>d[i]>>l[i];
	fin.close();
}

void sch(int i,int j)
{
	long aux=d[i]; d[i]=d[j]; d[j]=aux;
	aux=l[i]; l[i]=l[j]; l[j]=aux;
}

void poz(int li,int ls)
{
	long i=0,j=-1,c;
	while(li<ls)
	{
		if(d[li]>d[ls])
		{
			sch(li,ls);
			c=i; i=-j; j=-c;
		}
		li+=i; ls+=j;
	}
	k=li;
}

void quick(int li,int ls)
{
	if(li<ls)
	{
		poz(li,ls);
		quick(li,k-1);
		quick(k+1,ls);
	}
}

void timp()
{
	long t=0,i=n,nr=0;
	while(d[i]>X && i>=1)
		i--;
	while(i>=1)
	{
		
		while(d[i]+t>X && i>=1)
			T[i]=nr, pos[nr]=i, i--;
		nr++;
		t+=L;
	}
	T_max=nr-1;
}

void swap(int x,int y)
{
	int aux=heap[x];
	heap[x]=heap[y];
	heap[y]=aux;
}

void upheap(int nod)
{
	while(nod>1 && heap[t(nod)]<heap[nod])
	{
		swap(t(nod),nod);
		nod=t(nod);
	}
}

void insert(int val)
{
	N++;
	heap[N]=val;
	upheap(N);
}

void downheap(int nod)
{
	while(fs(nod)<=N && heap[nod]<heap[fs(nod)] || fd(nod)<=N && heap[nod]<heap[fd(nod)])
		if(fd(nod)<=N)
		{
			if(heap[fs(nod)]>heap[fd(nod)])
			{
				swap(nod,fs(nod));
				nod=fs(nod);
			}
			else
			{
				swap(nod,fd(nod));
				nod=fd(nod);
			}
		}
		else
		{
			swap(nod,fs(nod));
			nod=fs(nod);
		}
}

void erase(int nod)
{
	swap(nod,N);
	N--;
	downheap(1);
}

void sol()
{
	int i,nr=0;
	for(i=T_max;i>=1;i--)
	{
		k=pos[i];
		while(T[k]==i && k<=n)
			insert(l[k]), k++;
		s+=heap[1];
		if(N>=1)
			erase(1);
	}
}

void afis()
{
	ofstream fout("lupu.out");
	fout<<s;
	fout.close();
}
	

int main()
{
	cit();
	quick(1,n);
	timp();
	sol();
	afis();
	return 0;
}