Cod sursa(job #149520)

Utilizator marinMari n marin Data 5 martie 2008 20:16:33
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#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);
  }
}