Pagini recente » Cod sursa (job #2138228) | Cod sursa (job #1018269) | Cod sursa (job #1968178) | Cod sursa (job #324447) | Cod sursa (job #154220)
Cod sursa(job #154220)
#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];
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;
}
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);
if(v[pozz[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;
}