Pagini recente » Cod sursa (job #1151460) | Cod sursa (job #2851081) | Cod sursa (job #2874934) | Cod sursa (job #1455901) | Cod sursa (job #258094)
Cod sursa(job #258094)
#include<stdio.h>
#define max(a,b) (a>b?a:b)
FILE *fin=fopen("heavymetal.in","r"),
*fout=fopen("heavymetal.out","w");
int N,x[100005],y[100005],B[100005];
void swap(int i,int j){
y[i]^=y[j];y[j]^=y[i];y[i]^=y[j];
x[i]^=x[j];x[j]^=x[i];x[i]^=x[j];
}
int main(){
fscanf(fin,"%d",&N);
for(int i=1;i<=N;i++){
fscanf(fin,"%d %d",&x[i],&y[i]);
int j=i;
while(j/2 && y[j/2]<y[j]){
swap(j,j/2);
j>>=1;
}
}
int Nh=N;
while(Nh>1){
swap(1,Nh);
--Nh;
int i=1,j;
while(1){
j=i*2;
if(j>Nh) break;
if(j+1<=Nh && y[j+1]>y[j]) ++j;
if(y[j]<y[i]) break;
swap(j,i);
i=j;
}
}
for(int i=1;i<=N;i++){
B[i]=B[i-1];
int li=1,lf=i-1;
while(lf-li>1){
int mij=(li+lf)/2;
if(x[i]<=y[mij])
lf=mij;
else
li=mij;
}
if(x[i]>=y[lf])
B[i]=max(B[i],y[i]-x[i]+B[lf]);
else
B[i]=max(B[i],y[i]-x[i]);
if(x[i]>=y[li])
B[i]=max(B[i],y[i]-x[i]+B[li]);
else
B[i]=max(B[i],y[i]-x[i]);
}
fprintf(fout,"%d\n",B[N]);
fclose(fin);
fclose(fout);
return 0;
}