Pagini recente » Cod sursa (job #4488) | Cod sursa (job #678577) | Cod sursa (job #476605) | Cod sursa (job #2311758) | Cod sursa (job #517132)
Cod sursa(job #517132)
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[200001],v[200001],v2[100001],r[200001],ind[200001],d[200001],n,x;
inline int cmp(int i,int j)
{
return v[i]<v[j];
}
inline int cmp2(int i,int j)
{
return v2[i]<v2[j];
}
int main()
{
int i,j=0;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d%d",&v[2*i-1],&v[2*i]);
ind[2*i-1]=2*i-1;
ind[2*i]=2*i;
}
sort(ind+1,ind+2*n+1,cmp);
for (i=1;i<=2*n;++i)
{
if (v[ind[i]]==v[ind[i-1]]) a[i]=x;
else
{
++x;
r[x]=v[ind[i]];
a[i]=x;
}
}
for (i=1;i<=2*n;++i) v[ind[i]]=a[i];
for (i=2;i<=2*n;i+=2) v2[i/2]=v[i];
for (i=1;i<2*n;i+=2) v[i/2+1]=v[i];
for (i=1;i<=n;++i) ind[i]=i;
sort(ind+1,ind+n+1,cmp2);
for (i=1;i<=n;++i) a[i]=v[ind[i]];
for (i=1;i<=n;++i) v[i]=a[i];
for (i=1;i<=n;++i) a[i]=v2[ind[i]];
for (i=1;i<=n;++i) v2[i]=a[i];
for (i=1;i<=x;++i)
{
d[i]=d[i-1];
while (v2[j+1]==i)
{
++j;
if (d[i]<d[v[j]]+r[v2[j]]-r[v[j]]) d[i]=d[v[j]]+r[v2[j]]-r[v[j]];
}
}
printf("%d",d[x]);
return 0;
}