Pagini recente » Cod sursa (job #1823956) | Cod sursa (job #1977312) | Cod sursa (job #3260498) | Cod sursa (job #3168970) | Cod sursa (job #1862385)
#include <cstdio>
#include <algorithm>
using namespace std;
struct interval
{
int left,right;
};
interval v[100010];
struct dinamica
{
int cpt,val;
};
dinamica d[100010];
int x;
bool cmp(interval x,interval y)
{
if(x.left==y.left)
return x.right<y.right;
else
return x.left<y.left;
}
int caut(int left,int right)
{
int mid;
while(left<=right)
{
mid=(left+right)/2;
if(d[mid].cpt>x)
right=mid-1;
else
left=mid+1;
}
return right;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,t;
scanf("%d",&n);
for(i=2; i<=n+1; i++)
scanf("%d%d",&v[i].left,&v[i].right);
sort(v+2,v+n+2,cmp);
for(i=2; i<=n+1; i++)
{
x=v[i].left;
t=caut(1,i-1);
if(d[t].val+v[i].right-v[i].left>d[i-1].val)
{
d[i].val=d[t].val+v[i].right-v[i].left;
d[i].cpt=v[i].right;
}
else
{
d[i].val=d[i-1].val;
d[i].cpt=d[i-1].cpt;
}
}
printf("%d",d[n+1].val);
return 0;
}