Editorial for DMOPC '20 Contest 4 P3 - Roving Roombas
Submitting an official solution before solving the problem yourself is a bannable offence.
We can mark all the squares with the Roombas and then for each cord, check how many squares contain the path of a Roomba.
Time Complexity: ~\mathcal O(NX_i + MY_i)~
We could line sweep, but the easier solution for this subtask is to simply check every Roomba and cord pair and determine if they intersect. A Roomba ~(R_x, R_y)~ intersects cord ~(C_x, C_y)~ if ~C_y \ge R_y~ and ~R_x \ge C_x~.
Time Complexity: ~\mathcal O(NM)~
If we look at the inequality used for the previous subtask, we note that we benefit greatly from sorting. Let's sort both the cords and the Roombas by ~X~. As we walk along the cords from left to right, we know that certain Roombas become irrelevant, since their paths are too short.
If we have a set of Roombas and a given cord, we can determine which Roombas intersect easily with a BIT. As we walk left to right, we remove certain Roombas from the set by updating the BIT. We query for all Roombas with small enough ~Y~ values by querying the BIT.
Time Complexity: ~\mathcal O(N \log N + M \log M + M + Y_i)~
We can finish off this solution with a line sweep. Note that any ~X~ that does not appear for any Roombas nor any cords is irrelevant, and similarly with ~Y~.
An alternative, very similar solution is to use binary search instead of a BIT. The effect is the same.
Time Complexity: ~\mathcal O(N \log N + M \log M)~