Pagini recente » Cod sursa (job #1720011) | Cod sursa (job #71968) | Cod sursa (job #1491398) | Cod sursa (job #1619497) | Cod sursa (job #142233)
Cod sursa(job #142233)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define N 100010
using namespace std;
struct interval{
int a,b;
};
interval v[N];
int pozz[N];
struct timp{
int cost,ora;
};
timp best[N];
inline int compar(interval*aa,interval*bb){
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 compara(const void *x,const void*y){
return compar(&v[*(int*)x],&v[*(int*)y]);
}
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(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);
pozz[i]=i;
}
//sort(v,v+n,f_comp);
qsort(pozz,n,sizeof(pozz[0]),compara);
best[m].cost=v[pozz[0]].b-v[pozz[0]].a;
best[m++].ora=v[pozz[0]].b;
for(i=1;i<n;++i){
poz=caut(0,m-1,v[pozz[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[pozz[i]].b-v[pozz[i]].a>best[m-1].cost)
best[m-1].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
}
else
if(best[poz].cost+v[pozz[i]].b-v[pozz[i]].a>best[m-1].cost){
best[m].cost=best[poz].cost+v[pozz[i]].b-v[pozz[i]].a;
best[m++].ora=v[pozz[i]].b;
}
}
printf("%d\n",best[m-1].cost);
return 0;
}