Cod sursa(job #1312675)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 ianuarie 2015 20:41:57
Problema Heavy metal Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#define MAXN 100000
int st[MAXN], dr[MAXN], rez[MAXN];

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int caut(int x, int n){
  int i = 0, pas = 1 << 16;
  while(pas > 0){
    if(i + pas < n)
      if(dr[i + pas] <= x)
        i += pas;
    pas >>= 1;
  }
  if(dr[i] <= x)
    return rez[i];
  return 0;
}

void qs(int cst, int cdr){
  int i = cst, j = cdr, piv = dr[(cst + cdr) / 2], aux;
  while(i <= j){
    while(dr[i] < piv)
      i++;
    while(dr[j] > piv)
      j--;
    if(i <= j){
      aux = st[i];
      st[i] = st[j];
      st[j] = aux;
      aux = dr[i];
      dr[i] = dr[j];
      dr[j] = aux;
      i++;
      j--;
    }
  }
  if(cst < j)
    qs(cst, j);
  if(i < cdr)
    qs(i, cdr);
}

int main(){
  FILE *in = fopen("heavymetal.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(in, "%d%d", &st[i], &dr[i]);
  fclose(in);
  qs(0, n - 1);
  int el;
  for(i = 0; i < n; i++){
    if(i != 0)
      rez[i] = max2(rez[i - 1], dr[i] - st[i] + caut(st[i], n));
    else
      rez[i] = dr[i] - st[i];
  }
  FILE *out = fopen("heavymetal.out", "w");
  fprintf(out, "%d", rez[n - 1]);
  fclose(out);
  return 0;
}