Pagini recente » Cod sursa (job #2608461) | Cod sursa (job #488702) | Cod sursa (job #1882899) | Cod sursa (job #874942) | Cod sursa (job #142220)
Cod sursa(job #142220)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define N 100010
using namespace std;
struct interval{
int a,b;
};
interval v[N];
struct timp{
int cost,ora;
};
timp best[N];
int compar(const void*x,const void*y){
interval *aa=(interval *)x,*bb=(interval *)y;
if (aa->b<bb->b)
return -1;
if (aa->b>bb->b)
return 1;
if (aa->a>bb->a)
return 1;
if (aa->a<bb->a)
return -1;
return 0;
}
int f_comp(interval x,interval y){
return x.a<y.a;
}
int caut(int p,int u,int x,int n){
int m;
/*
while(p<=u){
m=(p+u)/2;
if (best[m].ora<=x && best[m+1].ora>x || best[m].ora<=x && m==n)
return m;
else
if (best[m].ora<=x && best[m+1].ora<=x)
p=m-1;
else
u=m+1;
}
return 0;
*/
while(p<u){
m=(p+u)/2;
if(x<=best[m].ora)
u=m;
else
p=m+1;
}
if(best[p].ora>x)
--p;
return p;
}
int main(){
int n,i,s=0,t,j,x,m=0;
int poz,p,u,b[N]={0};
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=0;i<n;++i){
scanf("%d%d",&v[i].a,&v[i].b);
}
sort(v,v+n,f_comp);
best[m].cost=v[0].b-v[0].a;
best[m++].ora=v[0].b;
for(i=1;i<n;++i){
poz=caut(0,m-1,v[i].a,m);//best[poz].ora va fi cea mai mare ora inainte de v[i].a
if(v[i].b==best[m-1].ora){
if(best[poz].cost+v[i].b-v[i].a>best[m-1].cost)
best[m-1].cost=best[poz].cost+v[i].b-v[i].a;
}
else
if(best[poz].cost+v[i].b-v[i].a>best[m-1].cost){
best[m].cost=best[poz].cost+v[i].b-v[i].a;
best[m++].ora=v[i].b;
}
/*
else{//e cam in plus...
best[m].cost=best[m-1].cost;
best[m++].ora=v[i].b;
}
*/
}
printf("%d\n",best[m-1].cost);
return 0;
}