## Editorial for CPC '21 Contest 1 P6 - AQT's Break Time is Over

**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 model each student as a 3-dimensional coordinate . We will first "plane sweep" (like line sweep, but in 3 dimensions) through the x dimension in non-increasing order. We sweep with a plane parallel to the yz-plane, having its x-coordinate denote the current being considered. This means that any coordinate with will get covered. We can treat the remaining points with as 2-dimensional coordinates . Since we are sweeping in non-increasing order, our algorithm will add new points into consideration and never remove any old points. Let be the minimum value of we need to cover all the points if we set at the current moment. When we add a point into consideration, all with will get updated to . For the first subtask, it is sufficient to loop to update all . We can then loop through all to find the minimum (we set and ). Our answer is the minimum of all . This costs per point for a total time complexity of .

#### Subtask 2

Notice that the function is monotonically non-increasing. Instead of looping to update and query, we can use a data structure such as a segment tree or a balanced binary search tree (BBST). segment tree solutions should pass with ease. Some optimization may be required to get BBST solutions or solutions to pass.

## Comments