Editorial for DMOPC '17 Contest 4 P1 - Ribbon Colouring Fun

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

For $40\%$ ~40\%~ of points, we can keep a boolean array and perform the update in $\mathcal O(N)$ ~\mathcal O(N)~.

Time Complexity: $\mathcal O(NQ)$ ~\mathcal O(NQ)~

For the remaining $60\%$ ~60\%~ of points, we can sort all the queries by left endpoint, and then keep a pointer for the rightmost location we are in the array. As we iterate through the queries, we can move the right endpoint until it is at least as far right as the current query we are considering. This takes $\mathcal O(N)$ ~\mathcal O(N)~ time.

Time Complexity: $\mathcal O(N + Q \log Q)$ ~\mathcal O(N + Q \log Q)~

Comments

There are no comments at the moment.