Pagini recente » Cod sursa (job #19169) | Cod sursa (job #26145) | Cod sursa (job #327726) | Cod sursa (job #183263) | Cod sursa (job #140849)
Cod sursa(job #140849)
#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)||(a.X==b.X&&a.xoy>=b.xoy&&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);
}
sort(x+1,x+n+1,cmpf1);
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;
}
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];
}
printf("%ld\n",p);
return 0;
}