Cod sursa(job #137333)

Utilizator ioraIoana Radu iora Data 17 februarie 2008 11:17:43
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 1.08 kb
#include<stdio.h>
#define NMAX 100000
long s,rr,ll,i,n;
long part(long st,long dr,long l[], long r[])
{
	long x,m,p,i,j;
	m=(st+dr)/2;
	p=l[m];
	i=st-1;
	j=dr+1;
	while(1)
	{
		do{i++;}while(l[i]<p||(l[i]==p&&r[i]<r[m])) ;
		do{j--;}while(l[j]>p||(l[j]==p&&r[j]>r[m])) ;
		if(i<j)
	{
		x=l[i];
		l[i]=l[j];
		l[j]=x;
		x=r[i];
		r[i]=r[j];
		r[j]=x;
	}
	else return j;
	}


}
void quick(long st,long dr,long l[],long r[])
{
	long sep;
	if(st<dr)
	{
		sep=part(st,dr,l,r);
		quick(st,sep,l,r);
		quick(sep+1,dr,l,r);
	}
}
int main()
{
	long l[NMAX],r[NMAX];
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);

	scanf("%ld",&n);
	for(i=1;i<=n;++i)
		scanf("%ld %ld",&l[i],&r[i]);
	quick(1,n,l,r);

	ll=l[1];
	rr=r[1];
	s=s+rr-ll;
	for(i=2;i<=n;++i)
		{

			if(l[i]==ll)
					{
					if(r[i]-l[i]>rr-ll)
						{
							s+=(r[i]-l[i])-(rr-ll);
							ll=l[i];
							rr=r[i];
						}
					}
			else
			{
			if(l[i]>=rr)
				{
					ll=l[i];
					rr=r[i];
					s+=rr-ll;
				}
			}
		}
	printf("%ld",s);
	return 0;
}