Editorial for COCI '09 Contest 4 #4 Ograda

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.

This task can easily be reduced to a histogram problem, solvable in three steps:

For each column, determine the maximal height reachable if the left part of the brush is touching the column. Using monotone queue, this can be solved in $\mathcal O(N)$ ~\mathcal O(N)~.
For each column, determine the maximal height reachable at all. This also determines the surface area left unpainted. Again, using a different monotone queue this can be solved in $\mathcal O(N)$ ~\mathcal O(N)~.
For each column, use a greedy algorithm to determine whether or not to perform a stroke. This can also be done in $\mathcal O(N)$ ~\mathcal O(N)~.

Using $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ structures was also acceptable, if coded correctly.

Comments

There are no comments at the moment.