Cod sursa(job #522235)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 14 ianuarie 2011 17:00:53
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct intz
{
	int st,dr;
};
bool ver2(intz x,intz y)
{
	if(x.dr==y.dr)
		return (x.st<y.st);
	return (x.dr<y.dr);
}
intz a[100100];
int sol[100100];
bool ver(int x,int i)
{
	return (a[x].dr<=a[i].st);
}
void bs (int i)
{
	int st=0,dr,last=0,med;
	dr=i;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(ver(med,i))
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	sol[i]=sol[last]+a[i].dr-a[i].st;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i].st,&a[i].dr);
	sort(a+1,a+n+1,ver2);
	sol[1]=a[1].dr-a[1].st;
	for(i=2;i<=n;i++)
		bs(i);
	printf("%d",sol[n]);
	return 0;
}