Cod sursa(job #1867788)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 4 februarie 2017 12:42:16
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <stdio.h>
#include <iostream>
#define MAX 100000

using namespace std;
int interval[2][MAX], timp[MAX];
void quicksort(int inf, int sup)
{
  int i, j, x, t;

  i = inf;
  j = sup;
  x = interval[1][(inf + sup) / 2];
  do
  {
    while(i < sup && interval[1][i] < x)i++;
    while(j > inf && interval[1][j] > x)j--;
    if(i <= j)
    {
      t = interval[1][i];
      interval[1][i] = interval[1][j];
      interval[1][j] = t;
      t = interval[0][i];
      interval[0][i] = interval[0][j];
      interval[0][j] = t;
      i++;
      j--;
    }
  }while(i <= j);
  if(inf < j)quicksort(inf, j);
  if(i < sup)quicksort(i, sup);
}
int main()
{
  FILE *fin, *fout;
  int n, i, maxi, j, st, dr, mij, retinem, gasit;

  fin = fopen("heavymetal.in", "r");
  fout = fopen("heavymetal.out", "w");
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)fscanf(fin, "%d%d", &interval[0][i], &interval[1][i]);
  quicksort(0, n - 1);
  for(i = 0; i < n; i++)
  {
    st = 0;
    dr = i - 1;
    mij = retinem = -1;
    while(st <= dr)
    {
      mij = (st + dr) / 2;
      if(interval[0][i] >= interval[1][mij])
      {
        st = mij + 1;
        retinem = mij;
      }
      else dr = mij - 1;
    }
    maxi = 0;
    for(j = i - 1; j >= 0; j--)if(maxi < timp[j])maxi = timp[j];
    if(retinem > -1)timp[i] = interval[1][i] - interval[0][i] + timp[retinem];
    else if(maxi < interval[1][i] - interval[0][i])timp[i] = interval[1][i] - interval[0][i];
    else timp[i] = maxi;
  }
  maxi = 0;
  /*printf("\n");
  for(i = 0; i < n; i++)printf("%d %d\n", interval[0][i], interval[1][i]);
  printf("\n");
  for(i = 0; i < n; i++)printf("%d\n", timp[i]);*/
  for(i = 0; i < n; i++)if(maxi < timp[i])maxi = timp[i];
  fprintf(fout, "%d", maxi);
  fclose( fin );
  fclose( fout );
  return 0;
}