Cod sursa(job #350355)

Utilizator bigdoggMic Matei bigdogg Data 23 septembrie 2009 16:54:35
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream.h>

struct el{ int d,a; } v[100001];
int N,range,L;

int mergesort(int,int);
void merge(int,int,int);
int search_low(int);
int search_top(int);
int get_max(int,int);

int main()
{
	int i,a,z,S=0;

	ifstream in("lupu.in");
	in>>N>>range>>L;
	for(i=1;i<=N;i++)
		in>>v[i].d>>v[i].a;
	in.close();
	
	mergesort(1,N);
	
	do
	{
		if(range+1-L<0) a=search_low(0);
		else a=search_low(range+1-L);
		z=search_top(range);
		S+=get_max(a,z);
		range-=L; N=a-1;
	}while(N>0);

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

int mergesort(int first,int last)
{
	int mid=(first+last)/2;

	if(first<last)
	{
		mergesort(first,mid);
		mergesort(mid+1,last);
		merge(first,mid,last);
	}
	return 0;
}

void merge(int first,int mid,int last)
{
	int i=first,j=mid+1,k=first;
	el c[100001];

	while(i<=mid && j<=last)
	{
		if(v[i].d<=v[j].d) c[k++]=v[i++];
		else c[k++]=v[j++];
	}
	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_low(int key)
{
	int first=1,mid,last=N;
	while(first<=last)
	{
		mid=(first+last)/2;
		if(v[mid].d>key) last=mid-1;
		if(v[mid].d<key)
			if(v[mid+1].d>=key) return mid+1;
			else first=mid+1;
		if(v[mid].d==key)
		{
			mid--;
			while(mid>1 && v[mid].d==key) mid--;
			return mid+1;
		}
	}
}

int search_top(int key)
{
	int first=1,mid,last=N;
	while(first<=last)
	{
		mid=(first+last)/2;
		if(v[mid].d>key)
			if(v[mid-1].d<=key) return mid-1;
			else last=mid-1;
		if(v[mid].d<key) first=mid+1;
		if(v[mid].d==key)
		{
			mid++;
			while(mid<=N && v[mid].d==key) mid++;
			return mid-1;
		}
	}
}

int get_max(int first,int last)
{
	int i,max=0;
	for(i=first;i<=last;i++)
		if(v[i].a>max) max=v[i].a;
	return max;
}