Ayuda con "Dancing Elephants" (IOI Tailandia)

Question

Como puedo obtener los 100 puntos en este problema?? intente usando el solucionario oficial pero no lo entiendo del todo. Alguien podria ayudarme?

Problema:

http://bo.spoj.com/problems/TH_ELEPH/

Solucionario:

http://www.ioi2011.or.th/hsc/tasks/solutions/elephants.pdf

Saque 38.24 puntos

Answer 1

Ese es el puntaje por fuerza bruta.

Para obtener 100 puntos, no siempre es posible con la siguiente mejor solución, muchas veces requiere 2 o más optimizaciones. Es mejor ir paso a paso.

Para mejorar tu puntaje, sería bueno mejorar dicha solución. Una búsqueda por fuerza bruta es O(N). Como podrías mejorar la búsqueda para no hacerla lineal?

Una pista es la siguiente:

Dado que las posiciones son muy grandes, es dificil introducir elementos en una estructura de datos que tenga que reservar espacio (interval tree por ej. ), pero hay una técnica para poder sortear este obstáculo.

 

Para eso, necesitamos comprimir los datos, hacer que todos los números sean consecutivos, pero para esto necesitamos procesar los datos de forma "offline", es decir, despues de haber leido toda la entrada. Ya que despues de tener todos los datos, ya podemos comprimir los números que vayamos a usar.

Comments

Como se procesan datos de forma "offline"? y como se comprime?