Pagini recente » Cod sursa (job #2387240) | Cod sursa (job #3250657) | Cod sursa (job #2453077) | Cod sursa (job #1142071) | Cod sursa (job #1856625)
#include<cstdio>
#include<algorithm>
using namespace std;
struct aa{int x,y;};
aa v[100001],vec[100001];
bool sortare(aa a,aa b)
{if(a.y<b.y||(a.y==b.y&&a.x<b.x))
return 1;
return 0;
}
int main ()
{freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
int n,i,c1,c2,x,k=0,q;
scanf("%d",&n);
for(i=1;i<=n;i++)
{scanf("%d%d",&v[i].x,&v[i].y);
v[i].y--;
}
sort(v+1,v+n+1,sortare);
for(i=1;i<=n;i++)
{c1=1;
c2=k;
q=0;
while(c1<=c2)
{x=(c1+c2)/2;
if(vec[x].x<v[i].x&&(vec[x+1].x>=v[i].x||x==k))
{q=x;
c1=c2+1;
}
else
if(vec[x].x<v[i].x)
c1=x+1;
else
c2=x-1;
}
if(vec[k].x!=v[i].y)
{k++;
vec[k].x=v[i].y;
vec[k].y=max(v[i].y-v[i].x+1+vec[q].y,vec[k-1].y);
}
else
vec[k].y=max(v[i].y-v[i].x+1+vec[q].y,vec[k].y);
}
printf("%d",vec[k].y);
return 0;
}