Cod sursa(job #352710)

Utilizator bigdoggMic Matei bigdogg Data 3 octombrie 2009 11:57:03
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream.h>

struct oaie{ int t,a; } v[100001],c[100001];

int N,X,L,H[100001],NH=0;

void mergesort(int,int);
void merge(int,int,int);
int search(int);
void up(int);
void down(int);

int main()
{
	int i,j,maxT=0,first,last;
	long long S=0;
	
	ifstream in("lupu.in");
	in>>N>>X>>L;
	for(i=1;i<=N;i++)
	{
		in>>v[i].t>>v[i].a;
		if(X-v[i].t>=0)
		{
			v[i].t=(X-v[i].t)/L+1;
			if(v[i].t>maxT) maxT=v[i].t;
		}
		else{ i--; N--; }
	}
	in.close();
	
	mergesort(1,N);

	for(i=maxT;i>=1;i--)
	{
		first=last=search(i);
		first--; last++;
		while(first>=1 && v[first].t==i) first--;
		while(last<=N && v[last].t==i) last++;
		first++; last--;
		for(j=first;j<=last;j++)
		{
			H[++NH]=v[j].a;
			up(NH);
		}
		S+=H[1];
		H[1]=H[NH--]; down(1);
	}

	ofstream out("lupu.out"); out<<S<<'\n'; out.close();
	
	return 0;
}

void mergesort(int first,int last)
{
	int mid;
	
	if(first<last)
	{
		mid=(first+last)/2;
		mergesort(first,mid);
		mergesort(mid+1,last);
		merge(first,mid,last);
	}
}

void merge(int first,int mid,int last)
{
	int i=first,j=mid+1,k=first;
	
	while(i<=mid && j<=last)
	{
		if(v[i].t<v[j].t) c[k]=v[i++];
		else c[k]=v[j++];
		k++;
	}
	while(i<=mid) c[k++]=v[i++];
	while(j<=last) c[k++]=v[j++];
	for(i=first;i<k;i++) v[i]=c[i];
}

int search(int key)
{
	int first=1,mid,last=N;
	
	while(first<=last)
	{
		mid=(first+last)/2;
		if(v[mid].t<key) first=mid+1;
		if(v[mid].t>key) last=mid-1;
		if(v[mid].t==key) return mid;
	}
	return 0;
}
			
void up(int K)
{
	int key=H[K];
	
	while(K>1 && key>H[K/2])
	{
		H[K]=H[K/2];
		K/=2;
	}
	H[K]=key;
}

void down(int K)
{
	int son,left,right,swap;
	
	do
	{
		son=0; left=K*2;
		if(left<=NH)
		{
			son=left; right=K*2+1;
			if(right<=NH && H[son]<H[right])
				son=right;
			if(H[son]<=H[K]) son=0;
		}
		if(son){ swap=H[son]; H[son]=H[K]; H[K]=swap; K=son; }
	}while(son);
}