Pagini recente » Cod sursa (job #1957616) | Cod sursa (job #943715) | Cod sursa (job #2584997) | Cod sursa (job #691073) | Cod sursa (job #1866681)
#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,ok;
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;
ok=0;
while(left<=right)
{
mid=(left+right)/2;
if(d[mid].cpt<=x)
{
ok=0;
left=mid+1;
}
else
{
ok=1;
right=mid-1;
}
}
return mid;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,t;
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d%d",&v[i].left,&v[i].right);
sort(v+1,v+n+1,cmp);
d[1].cpt=v[1].right;
d[1].val=v[1].right-v[1].left;
for(i=2; i<=n; i++)
{
if(v[i].left<d[i-1].cpt)
{
x=v[i].left;
t=caut(0,i-2);
if(ok==1)
t--;
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;
}
}
else
{
d[i].cpt=v[i].right;
d[i].val=d[i-1].val+v[i].right-v[i].left;
}
}
printf("%d",d[n].val);
return 0;
}