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

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))$ $O (R C + 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)$ $O (R C + Q)$

Comments

There are no comments at the moment.