USACO 2012 January Contest, Bronze Division, Problem 2. Haybale Stacking

USACO 2012 January Contest, Bronze Division, Problem 2. Haybale Stacking

Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=104
Este problema no se puede resolver con fuerza bruta ya que N es de 1,000,000 de elementos, y K es de 25,000, entonces como puedo resolver este problema ?
El problema pide que se de el tamaño de la pila de enmedio ( ya ordenadas todas ) , entonces hay que generar de alguna manera todas las pilas de forma lineal, y despues ordenarlas para sacar la de enmedio.
Si yo marco en un erreglo insert todas las posiciones en donde inicia un intervalo
y en otro arreglo delete marco todas las posicones en donde termina un intervalo
si hay mas de dos posiciones repetidas lo que se guardan en ambos arreglos es el numero de intervalos que se insertan y el numero de intervalos que terminan en esa posicion
Con solo recorrer el arreglo de izquierda a derecha ( de 1 a N (en mi algoritmo de 0 a N - 1, ya que decremento a y b por 1) ) puedo asignarle a cada pila el numero de fardos de heno que deberia tener despues de asignar todas los fardos correspondientes, este valor lo guardamos en count, ya teniendo esta informacion solo se ordena y se imprime la posicion n / 2

Aqui el codigo:

/*
   Autor: Rodrigo Burgos Dominguez
   Problema: Stacking
*/
# include "string.h"
# include "stdio.h"

int insert[1000001];
int delete[1000001];
int count[1000001];

int compare( int *a, int *b){ return *a - *b; }

main(){
  int x, n, k, a, b, cont;
  freopen("stacking.in", "r", stdin);
  freopen("stacking.out", "w", stdout);
  scanf("%d %d", &n, &k);
  memset( insert, 0, sizeof( insert ));
  memset( delete, 0, sizeof( delete ));
  memset( count , 0, sizeof( count  ));
  for( x = 0; x < k ; x++){
     scanf("%d %d", &a, &b);
     insert[ a - 1 ]++;
     delete[ b - 1 ]++;
  }
  cont = 0;
  for( x = 0; x < n; x++){
   cont += insert[ x ];
    count[ x ] = cont;
   cont -= delete[ x ];
  }
  qsort( count, x, sizeof( int ) , compare );
  printf("%d\n", count[ n / 2 ]);
  return 0; 
}

Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com