Pagini recente » Cod sursa (job #2718751) | Cod sursa (job #2298931) | Cod sursa (job #2395698) | Cod sursa (job #205467) | Cod sursa (job #184833)
Cod sursa(job #184833)
#include <stdio.h>
#include <stdlib.h>
#define max(a,b)((a>b)?a:b)
#define FOR(i,s,d) for(i=(s);i<=(d);++i)
long a[100005],b[100005],n,i,j,v[1000001],ind[1000001],x[100005],q,s,d,mid;
int comp(const void * n1 ,const void * n2){
return b[*((long*)n1)]-b[*((long*)n2)];
}
int main ()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
FOR (i,1,n){
scanf("%ld %ld",&a[i],&b[i]);
ind[i]=i;
}
qsort(ind+1,n,sizeof(long),comp);
FOR (i,1,n){
if (x[q]!=b[i])q++;
x[q]=b[ind[i]];
v[q]=v[q-1];
s=1;d=q;
while (s<d)
{
long mid=(s+d)/2;
if (x[mid]>a[ind[i]])
d=mid;
else
s=mid+1;
}
if(s<q&&x[s]==a[ind[i]])
v[q]=max(v[q],v[s]+b[ind[i]]-a[ind[i]]);
else
v[q]=max(v[q],v[s-1]+b[ind[i]]-a[ind[i]]);
}
printf("%ld",v[q]);
//printf("\n");
//FOR (i,1,q)printf("%ld ",v[i]);
return 0;
}