Cod sursa(job #147851)

Utilizator crawlerPuni Andrei Paul crawler Data 3 martie 2008 17:29:58
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>

#define Nmax 100100
#define LogN 20

typedef unsigned int uint;
#define int uint

struct interval { int x,y; };

interval a[Nmax];
int n, best[Nmax];

inline int max(int a,int b)
{
	if (a>b) return a;
	return b;
}

inline int comp(interval a,interval b)
{
	if (a.x < b.x) return 1;
	if (a.x > b.x) return 0;
	if (a.y < b.y) return 1;
	return 0;
}

int search(int X)
{
	int ret=0,t;
	#define q(W) if(ret + (1<<(W)) <= n) if (a[ret + (1<<(W))].x <= X) ret += (1<<(W));
	t = LogN;
	while(t--) q(t);
	return ret;
}

void sort(int st,int dr)
{
	int i=st,j=dr;
	interval m=a[(st+dr)/2], aux;
	do
	{
		while (comp(a[i],m)) ++i;
		while (comp(m,a[j])) --j;
		if (i<=j)
		{
			aux = a[i];
			a[i]= a[j];
			a[j]= aux;
			++i; --j;
		}
	} while (i<=j);
	if (i<dr) sort(i,dr);
	if (st<j) sort(st,j);
}

#undef int

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);

	scanf("%d", &n);

	int i,x;

	for (i=1;i<=n;++i)
	scanf("%d%d", &a[i].y,&a[i].x);

	sort(1,n);

	for (i=1;i<=n;++i)
	{
		best[i] = best[i-1];
		x = search(a[i].y);
		best[i] = max(best[i],best[x]+a[i].x-a[i].y);
	}
	printf("%d\n", best[n]);

	return 0;
}