Pagini recente » Cod sursa (job #2953600) | Cod sursa (job #214098) | Cod sursa (job #320966) | Cod sursa (job #566669) | Cod sursa (job #1783464)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 100005
using namespace std;
FILE *IN,*OUT;
int N,D[MaxN],P[MaxN];
struct _Interval
{
int x,y;
}v[MaxN];
bool cond(int a,int b)
{
return v[a].y<v[b].y||(v[a].y==v[b].y&&v[a].x<v[b].x);
}
int Binary_Search(int val)
{
int hi=N,lw=1,mid,last=0;
while(lw<=hi)
{
mid=(lw+hi)>>1;
if(v[P[mid]].y<=val)
last=mid,lw=mid+1;
else hi=mid-1;
}
return last;
}
int main()
{
IN=fopen("heavymetal.in","r");
OUT=fopen("heavymetal.out","w");
fscanf(IN,"%d",&N);
for(int i=1;i<=N;i++)
{
fscanf(IN,"%d%d",&v[i].x,&v[i].y);
P[i]=i;
}
sort(P+1,P+1+N,cond);
for(int i=1;i<=N;i++)
D[i]=max(D[i-1],D[Binary_Search(v[P[i]].x)]+v[P[i]].y-v[P[i]].x);
fprintf(OUT,"%d",D[N]);
return 0;
}