Pagini recente » Cod sursa (job #2620550) | Cod sursa (job #1623324) | Cod sursa (job #1216527) | Cod sursa (job #1058638) | Cod sursa (job #342569)
Cod sursa(job #342569)
#include <stdio.h>
long a[100002],b[100002],d[100002],i,n,j;
void inter(long x,long m,long y){
long c[100002],d[100002];
for(i=x;i<=y;i++){
c[i]=a[i];
d[i]=b[i];
}
long i1=x;
long i2=m+1;
long k=x-1;
while(i1<=m&&i2<=y)
if(d[i1]<d[i2]){
a[++k]=c[i1++];
b[k]=d[i1-1];
}
else{
a[++k]=c[i2++];
b[k]=d[i2-1];
}
for(i=i1;i<=m;i++){
a[++k]=c[i];
b[k]=d[i];
}
for(i=i2;i<=y;i++){
a[++k]=c[i];
b[k]=d[i];
}
}
void sort(long x,long y){
if(x!=y){
long m=(x+y)/2;
sort(x,m);
sort(m+1,y);
inter(x,m,y);
}
}
long BS(long x,long l,long r){
if (l<=r){
long m=(l+r)/2+1;
if(x<b[m]) BS(x,l,m-1);
else
if(x>b[m]) BS(x,m+1,r);
else
if(x==b[m])return m;
}
else
return r;
}
int main(){
FILE *f,*g;
f=fopen("heavymetal.in","r");
g=fopen("heavymetal.out","w");
fscanf(f,"%ld",&n);
for(i=1;i<=n;i++)
fscanf(f,"%ld%ld",&a[i],&b[i]);
sort(1,n);
d[1]=b[1]-a[1];
for(i=2;i<=n;i++){
d[i]=d[i-1];
j=BS(a[i],1,i-1);
if(d[i]<b[i]-a[i]+d[j])
d[i]=b[i]-a[i]+d[j];
}
fprintf(g,"%ld\n",d[n]);
fclose(f);
fclose(g);
return 0;
}