Editorial for Loteria

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.

Lotería

Centrémonos en una consulta.

Calcular la distancia ingenuamente es $O(L)$ ~O(L)~.

Hay $O(n^2)$ ~O(n^2)~ pares de intervalos.

Entonces, la fuerza bruta es $O(n^2 × L) = O (n^3)$.

A A B A B A B C

distancia (1, 3) = 1

A A B A B A B C

distancia (1, 3) = 1

A A B A B A B C

distancia (2, 4) = 0

A A B A B A B C

distancia (3, 5) = 1

$O(n)$ ~O(n)~ para cada turno.

$O(n^2)$ ~O(n^2)~ en total para encontrar todas las distancias.

¿Cómo evitar el factor q en responder consultas? ¡No podemos almacenar la matriz $O(n^2)!$ ~O(n^2)!~

Consultas: 2, 4, 7

0 → 2

1 → 2

2 → 2

3 → 4

4 → 4

5 → 7

6 → 7

7 → 7

Tiempo de complejidad : $O(n^2)$ ~O(n^2)~

Memoria: $O(nq)$ ~O(nq)~

Comments

There are no comments at the moment.