Editorial for Perrito chill y los caramelos

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: karellgz

Vamos a ordenar todos los puntos por su componente X y luego vamos a mapearlos: $f: X_k \rightarrow k$ ~f: X_k \rightarrow k~

Nos queda un problema equivalente, pero los componentes X solo van a ir desde $0$ ~0~ hasta $n-1$ ~n-1~

Mantenemos una estructura de datos en el que el elemento $S_i$ ~S_i~ es la solución para el elemento con valor en $X=i$ ~X=i~

Iteramos por los puntos desde abajo hacia arriba (según su componente Y) y la solución para el punto actual $(X,Y)$ ~(X,Y)~ va a ser el máximo valor de un punto en la estructura de datos en el intervalo $[0;X]$ ~[0;X]~ y le sumamos 1, luego actualizamos la estructura $E_X := max(E_0, E_1, ..., E_X) + 1$ ~E_X := max(E_0, E_1, ..., E_X) + 1~ y repetimos para el siguiente punto.

Al final, la solución va a ser el máximo valor en la estructura completa.

Complejidad (Asumiendo que utilizaste un árbol de segmentos): $O(n \cdot \log n)$ ~O(n \cdot \log n)~

Comments

There are no comments at the moment.