Cod sursa(job #138428)

Utilizator marius135Dumitran Adrian Marius marius135 Data 18 februarie 2008 17:12:07
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<stdlib.h>

struct timp{long timp,interv,dist;};
long n;
timp v[1024*128 *2];
long x[1024*128];
timp w[1024*128 *2];

int cmpstruct ( const void *a, const void *b)
{
	return (*(timp *)a).timp - (*(timp *)b).timp;
	
}
void mergesort(long st,long dr)
{
	if( st == dr)
		return;
	if( st == dr-1)
	{
		if(v[st].timp > v[dr].timp)
		{
			timp aux = v[st];
			v[st] = v[dr];
			v[dr] = aux;
		}
		return ;
	}
	long mij = (st + dr)/2;
	mergesort(st,mij);
	mergesort(mij+1,dr);
	
	long a = st , b = mij+1 ,i = a-1;
	
	for( ; a <= mij && b <= dr; )
	{
		if( v[a].timp > v[b].timp)
			w[++i] = v[b++];
		else w[++i] = v[a++];
	}
	if( a > mij)
		{while(b<=dr)
			w[++i] = v[b++];}
	else 
		while(a<=mij)
			w[++i] = v[a++];
	
	for( long i = a; i<= b; ++i)
		v[i] = w[i];
	
	
	
}


int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	scanf("%ld",&n);
	for(long  i = 1; i <= n; ++i)
	{
		long a,b;
		scanf("%ld %ld",&a,&b);
		v[i*2-1].timp = a*2+1;
		//v[i*2-1].fel = 1;
		v[i*2-1].interv = i;
		v[i*2-1].dist = b-a;
		v[i*2].timp = b*2;
		v[i*2].interv = i;
	}
	
	//qsort(v+1,2*n,sizeof(v[0]),cmpstruct);
	mergesort(1,2*n);
	
	long max = 0;
	for(long  i = 1; i <= 2*n; ++i)
	{
		if( v[i].timp%2 == 1)// intrare
		{
			x[v[i].interv] = max+ v[i].dist;
		}
		else
		{
			if(x[v[i].interv] > max)
				max = x[v[i].interv];
		}
	}
	
	printf("%ld\n",max);
	
	return 0;
}