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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Para 30 puntos la fuerza bruta manteniendo la suma del subarreglo en es suficiente.
Observación clave: si restamos a cada elemento, podemos transformar el problema a buscar la cantidad de subarreglos con suma mayor o igual a .
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 .
Comments