Pagini recente » Cod sursa (job #2803184) | Cod sursa (job #140076) | Cod sursa (job #2308634) | Cod sursa (job #1501870) | Cod sursa (job #837825)
Cod sursa(job #837825)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,p[100001],tmax,nr;
long long best[100001];
struct timp
{
int a,b;
}v[100001];
int cmp(timp x,timp y)
{
return x.b<y.b;
}
void citire()
{
freopen("heavymetal.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&v[i].a,&v[i].b);
p[2*i-1]=v[i].a;
p[2*i]=v[i].b;
}
}
int cauta(int x)
{
int m,st=1,sf=nr;
while(st<=sf)
{
m=(st+sf)/2;
if(p[m]==x)
return m;
if(p[m]<x)
st=m+1;
else
sf=m-1;
}
}
void normalizare()
{
nr=1;
for(int i=2;i<=2*n;i++)
{
if(p[i]!=p[i-1])
p[++nr]=p[i];
}
for(int i=1;i<=n;i++)
{
v[i].a=cauta(v[i].a);
v[i].b=cauta(v[i].b);
}
}
void din()
{
int t=1;
long long rez;
for(int i=1;i<=nr;i++)
{
best[i]=best[i-1];
while(v[t].b<i)
t++;
while(v[t].b==i)
{
rez=best[v[t].a]+p[v[t].b]-p[v[t].a];
if(rez>best[i])
best[i]=rez;
t++;
}
}
}
void afisare()
{
freopen("heavymetal.out","w",stdout);
printf("%lld",best[nr]);
}
int main()
{
citire();
sort(v+1,v+n+1,cmp);
sort(p,p+2*n+1);
normalizare();
din();
afisare();
return 0;
}