Cod sursa(job #342592)

Utilizator ZethpixZethpix Zethpix Data 22 august 2009 13:49:40
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
long a[100002],b[100002],d[100002],i,n,j,max,poz;
void inter(long x,long m,long y){
	long c[100002],d[100002];
	for(i=x;i<=y;i++){
		c[i]=a[i];
		d[i]=b[i];
	}
	long i1=x;
	long i2=m+1;
	long k=x-1;
	while(i1<=m&&i2<=y)
		if(d[i1]<d[i2]){
			a[++k]=c[i1++];
			b[k]=d[i1-1];
		}
		else
		if(d[i1]>d[i2]){
			a[++k]=c[i2++];
			b[k]=d[i2-1];
		}
		else{
			if(c[i1]>c[i2]){
				a[++k]=c[i1++];
				b[k]=d[i1-1];
			}
			else{
				a[++k]=c[i2++];
				b[k]=d[i2-1];
			}
		}
	for(i=i1;i<=m;i++){
		a[++k]=c[i];
		b[k]=d[i];
	}
	for(i=i2;i<=y;i++){ 
		a[++k]=c[i];
		b[k]=d[i];
	}
}
void sort(long x,long y){
	if(x!=y){
		long m=(x+y)/2;
		sort(x,m);
		sort(m+1,y);
		inter(x,m,y);
	}
}
long BS(long x,long l,long r){
	if (l<=r){
		long m=(l+r)/2;
		if(x<b[m]) BS(x,l,m-1);
		else
		if(x>b[m]) BS(x,m+1,r);
		else
		return m;
	}
	else 
	return r;
}
int main(){
	FILE *f,*g;
	f=fopen("heavymetal.in","r");
	g=fopen("heavymetal.out","w");
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%ld%ld",&a[i],&b[i]);
	sort(1,n);
	d[1]=b[1]-a[1];
	for(i=2;i<=n;i++){
		d[i]=d[i-1];
		j=BS(a[i],1,i-1);
		while(b[j]==b[j-1]) j--;
		j++;
		max=0;
		while(b[j]==b[j+1]){
			if(d[j]<d[j+1]){
				max=d[j+1];
				poz=j+1;
			}
			j++;
		}
		j=poz;
		if(d[i]<b[i]-a[i]+d[j])
			d[i]=b[i]-a[i]+d[j];
	}
	fprintf(g,"%ld\n",d[n]);
	fclose(f);
	fclose(g);
	return 0;
}