Editorial for DMOPC '17 Contest 1 P1 - Fujō Neko

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 the first subtask, we can loop through the column $x_i$ ~x_i~ and row $y_i$ ~y_i~ and check if there's an X.

Time Complexity: $\mathcal O(RC + Q(R+C))$ ~\mathcal O(RC + Q(R+C))~

For the second subtask, we can preprocess the grid and create two arrays, $A$ ~A~ and $B$ ~B~. Let $A_i$ ~A_i~ be true if there is an X on column $i$ ~i~ and $B_j$ ~B_j~ be true if there is an X on row $j$ ~j~. To answer each query, we just check if $A_{x_i}$ ~A_{x_i}~ or $B_{y_i}$ ~B_{y_i}~ is true.

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

Comments

There are no comments at the moment.