## Editorial for DMOPC '20 Contest 4 P3 - Roving Roombas

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

#### Subtask 1

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

#### Subtask 2

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 intersects cord if and .

**Time Complexity**:

#### Subtask 3

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 . 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 values by querying the BIT.

**Time Complexity**:

#### Subtask 4

We can finish off this solution with a line sweep. Note that any that does not appear for any Roombas nor any cords is irrelevant, and similarly with .

An alternative, very similar solution is to use binary search instead of a BIT. The effect is the same.

**Time Complexity**:

## Comments