Cod sursa(job #140827)

Utilizator za_wolfpalianos cristian za_wolf Data 22 februarie 2008 12:32:29
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 201001
using namespace std;
long p,i,y[NMAX],poz,in,sf,a,j,k,l,n,m,q;
struct kkt
{
	long X,Y;
};
kkt x[NMAX],aux;
int cmpf1(const kkt a,const kkt b)
{
	return a.Y<b.Y;
}
struct coi
{
	long X,P,xoy;
};
coi z[NMAX],aaux;
struct fin
{
	long I,J;
};
fin pwl[NMAX];
int cmpf2(const coi a,const coi b)
{
//	return a.X<b.X;
	return ((a.X<b.X)||(a.X==b.X&&!(z[i].xoy==0&&z[i+1].xoy==1))||(a.X==b.X&&a.P<b.P));
}
long mx(long a,long b)
{
	if (a>b) return a;
	return b;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%ld%ld",&x[i].X,&x[i].Y);

	}
/*	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<n;i++)
			if ((x[i].Y>x[i+1].Y)||(x[i].Y==x[i+1].Y&&x[i].X<x[i+1].X))
			{
				aux=x[i];
				x[i]=x[i+1];
				x[i+1]=aux;
				a=1;
			}
	} */

	for (i=1;i<=n;i++)
	{
		z[++m].X=x[i].X;
		z[m].P=i;
		z[m].xoy=0;
		z[++m].X=x[i].Y;
		z[m].P=i;
		z[m].xoy=1;
	}
/*	a=1;
	while (a)
	{
		a=0;
		for (i=1;i<m;i++)
			if ((z[i].X>z[i+1].X)||(z[i].X==z[i+1].X&&z[i].xoy==0&&z[i+1].xoy==1)||(z[i].X==z[i+1].X&&z[i].P>z[i+1].P))
			{
				aaux=z[i];
				z[i]=z[i+1];
				z[i+1]=aaux;
				a=1;
			}
	} */



	sort(x+1,x+n+1,cmpf1);
	sort(z+1,z+m+1,cmpf2);
	for (i=1;i<=m;i++)
	{
		in=i;
		sf=i;
		j=i;
		while (z[i].X==z[i+1].X&&z[i].xoy==z[i+1].xoy&&z[i].xoy==1)
		{
			sf++;
			i++;
		}
		if (z[j].xoy==1)
		for (l=j;l<=i;l++)
		{
			pwl[l].I=z[in].P;
			pwl[l].J=z[sf].P;
		}
	}

	for (i=1;i<=m;i++)
	{
		y[z[i].X]=y[z[i-1].X];
		if (z[i].xoy)
		for (j=pwl[i].I;j<=pwl[i].J;j++)
			if (x[j].Y==z[i].X)

				y[z[i].X]=mx(y[z[i].X],y[x[j].X]+(x[j].Y-x[j].X));

		if (y[z[i].X]>p)
			p=y[z[i].X];


	}

/*	for (i=1;i<=m;i++)
	{
		y[x[i].Y]=y[x[i-1].Y];
		for (j=1;j<=n;j++)
			if (x[j].Y==x[i].Y)

				y[x[i].Y]=mx(y[x[i].Y],y[x[j].X]+(x[j].Y-x[j].X));

		if (y[x[i].Y]>p)
			p=y[x[i].Y];
		if (y[x[i].X]>p)
			p=y[x[i].X];

	} */
	printf("%ld\n",p);

	return 0;
}