Editorial for Vudú


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: humbertoyusta

Para 30 puntos la fuerza bruta manteniendo la suma del subarreglo en O(n^2) es suficiente.

Observación clave: si restamos P a cada elemento, podemos transformar el problema a buscar la cantidad de subarreglos con suma mayor o igual a 0.

Esto se puede resolver contando la cantidad de inversiones al arreglo de prefix sums, lo cual se puede hacer comprimiendo coordenadas y usando un fenwick tree, complejidad O(n\log n).


Comments

There are no comments at the moment.