Cod sursa(job #470518)

Utilizator mihai995mihai995 mihai995 Data 14 iulie 2010 13:34:17
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
using namespace std;

struct interval{int x,y;} a[1<<17];
int v[1<<17],t[1<<17],n;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

bool cmp(interval a,interval b)
{
	return a.y<b.y || a.y==b.y && a.x<b.x;
}

int bs(int x)
{
	int i,step=1<<16;
	for (i=0;step;step>>=1)
		if (i+step<=t[0] && t[i+step]<=x)
			i+=step;
	return i;
}

int main()
{
	int i,j;
	in>>n;
	for (i=1;i<=n;i++)
		in>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for (i=j=1;j<=n;i++)
	{
		v[i]=v[i-1];
		t[++t[0]]=a[j].y;
		for (;a[j].y==t[i] && j<=n;j++)
			v[i]=max(v[i],v[bs(a[j].x)]+a[j].y-a[j].x);
	}
	out<<v[t[0]]<<"\n";
	return 0;
}