Pagini recente » Cod sursa (job #2637501) | Cod sursa (job #2687668) | Cod sursa (job #2534016) | Cod sursa (job #561887) | Cod sursa (job #1860323)
#include<cstdio>
#include<algorithm>
using namespace std;
struct heavymetal
{
int st,dr,timp;
};
heavymetal v[100001],f[100001];
bool sortare(heavymetal a, heavymetal b)
{
return a.dr<b.dr;
}
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,pp;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].st,&v[i].dr);
v[i].timp=v[i].dr-v[i].st;
}
sort(v+1,v+n+1,sortare);
f[1].st=v[1].st;
f[1].dr=v[1].dr;
f[1].timp=v[1].timp;
int l1,l2,mij;
for(i=2;i<=n;i++)
{
if(v[i].st<f[i-1].dr)
{
l1=0;
l2=i-2;
pp=0;
while(l1<=l2)
{
mij=(l1+l2)/2;
if(f[mij].dr<=v[i].st)
{
l1=mij+1;
pp=0;
}
if(f[mij].dr>v[i].st)
{
l2=mij-1;
pp=1;
}
}
if(pp==1)
mij--;
if(f[mij].timp+v[i].timp>f[i-1].timp)
{
f[i].st=f[i-1].st;
f[i].dr=v[i].dr;
f[i].timp=f[mij].timp+v[i].timp;
}
else if(f[mij].timp+v[i].timp<=f[i-1].timp)
{
f[i].st=f[i-1].st;
f[i].dr=f[i-1].dr;
f[i].timp=f[i-1].timp;
}
}
else
if(v[i].st>=f[i-1].dr)
{
f[i].st=f[i-1].st;
f[i].dr=v[i].dr;
f[i].timp=f[i-1].timp+v[i].timp;
}
}
printf("%d",f[n].timp);
return 0;
}