Cod sursa(job #185871)

Utilizator raduzerRadu Zernoveanu raduzer Data 26 aprilie 2008 12:01:54
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <stdlib.h>

int n,ord[100000],d[1000000],i,j,x,aux,max;

typedef struct
{
int a, b;
} interval;
interval a[100000], b[100000];

int cmp(const void *j, const void *k)
{
	int x=*(int*)j, y=*(int*)k;
	if (a[x].b==a[y].b) return a[x].a-a[y].a;
	return a[x].b-a[y].b;
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for (i=0; i<n; ++i) { scanf("%d%d",&a[i].a,&a[i].b);ord[i]=i; }
	qsort(ord, n, sizeof(int), cmp);
	for (i=1; i<=n; ++i) b[i]=a[ord[i-1]];
	x=b[n].b;
	j=1;
	for (i=1; i<=x; ++i) 
	{
		d[i]=d[i-1];
		while ( i == b[ j ].b)
		{     aux = d[b[j].a] + b[j].b - b[j].a;  
			  if(aux > d[i]) d[i] = aux;  
			  j++;  
		}  
		if (d[i] > max) max=d[i];
	}
	printf("%d",max);
	return 0;
}