Pagini recente » Cod sursa (job #2833983) | Cod sursa (job #1410685) | Cod sursa (job #3143521) | Cod sursa (job #111691) | Cod sursa (job #149520)
Cod sursa(job #149520)
#include <stdio.h>
#define DIM 100001
struct inter {
long int a;
long int b;
};
typedef inter tip;
long int n;
tip v[DIM];
int a[DIM];
long int t,i,j,m,x,max;
void cre(tip *v, long int n);
void corect(long int poz, tip *v, long int n);
void sort(tip *v, long int n);
int cautb(int x,int p,int u){
int m,t;
while (p<=u) {
m = (p+u)/2;
if (v[m].b<=x) p=m+1;
else
if (v[m].b>x) u=m-1;
}
if (v[m].b==x) {
t = a[m];
return t;
} else {
m=p;
if (v[m].b>x)
m=u;
t = a[m];
return t;
}
}
int main(){
FILE *f = fopen("heavymetal.in","r");
FILE *g = fopen("heavymetal.out","w");
fscanf(f,"%ld",&n);
for (j=1;j<=n;j++) {
fscanf(f,"%ld %ld",&v[j].a,&v[j].b);
}
fclose(f);
sort(v,n);
a[0]=0;
a[1]=v[1].b-v[1].a;
for (i=2;i<=n;i++){
a[i]=a[i-1];
x = v[i].a;
t=cautb(v[i].a,1,i);
if (t-v[i].a+v[i].b>a[i])
a[i]=t-v[i].a+v[i].b;
}
i=n-1;
max = a[n];
while (v[n].b==v[i].b) {
if (a[i]>max)
max = a[i];
i--;
}
fprintf(g,"%d",max);
fclose(g);
return 0;
}
void cre(tip *v, long int n){
long int i,c,p;
tip aux;
for (i=2;i<=n;i++) {
c = i;
p = i>>1;
while ((p)&&(v[c].b>v[p].b)) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
c = p;
p = p>>1;
}
}
}
void corect(long int poz, tip *v, long int n){
long int p,c;
tip aux;
p = poz;
c = p<<1;
while (c<=n) {
if ((c+1<=n) && (v[c+1].b>v[c].b))
c++;
if (v[c].b>v[p].b) {
aux = v[c];
v[c] = v[p];
v[p] = aux;
p = c;
c = p<<1;
} else break;
}
}
void sort(tip *v, long int n) {
long int i;
tip aux;
cre(v,n);
for (i=n;i>1;i--) {
aux = v[1];
v[1] = v[i];
v[i] = aux;
corect(1,v,i-1);
}
}