Editorial for Valentine's Day '19 S2 - Ctudor's Cute Cacti

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

For the first subtask, we can brute force.

Time Complexity: \mathcal{O}(NQ)

For the second subtask, we can observe a few things. Firstly, notice that for every update event, only a row and a column is updated. Thus, we can keep track of the rows and columns separately. Let r_j represent the number of times row j was updated, and let c_i represent the number of times column i was updated. For an update event, we only need to increment r_j and c_i by one. For a query event, we simply add r_j + c_i, and modulo by 2.

However, notice that position (i, j) is counted twice in both the row and the column. Thus, we need to use a hashmap or a map to keep track of the number times position (i, j) was the actual position that was updated, and subtract that value.

Time Complexity: \mathcal{O}(Q) or \mathcal{O}(Q \log Q)


There are no comments at the moment.