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 and row y_i and check if there's an X.

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

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

Time Complexity: \mathcal O(RC + Q)


Comments

There are no comments at the moment.