Pagini recente » Cod sursa (job #1730667) | Cod sursa (job #942491) | Cod sursa (job #1106846) | Cod sursa (job #2836609) | Cod sursa (job #1852369)
#include<cstdio>
#include<algorithm>
#include<vector>
const int Nmax=100000;
struct interv
{
int x,y,rez;
};
interv v[Nmax+1];
bool comparare(interv a,interv b)
{
if(a.y<b.y)
return true;
if(a.y>b.y)
return false;
if(a.x<b.x)
return true;
return false;
}
int main()
{
int n;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d ",&n);
for(int i=1;i<=n;i++)
scanf("%d %d ",&v[i].x,&v[i].y);
std::sort(v+1,v+n+1,comparare);
for(int i=1;i<=n;i++)
{
int st=1,dr=i-1,sol=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v[mij].y<=v[i].x)
{
sol=mij;
st=mij+1;
}
else
dr=mij-1;
}
v[i].rez=std::max(v[i-1].rez, v[i].y-v[i].x+v[sol].rez);
}
printf("%d\n",v[n].rez);
return 0;
}