Editorial for Max's Anger Contest Series 2 P5 - Job Anger

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

Subtask 1

Iterate through every line and check if it intersects with any other line by iterating through all points in one and checking if it overlaps with the other line.

Time Complexity: \mathcal{O}(N^{2}(\sum_{i=1}^{N} x_{2_{i}} - x_{1_{i}} + y_{2_{i}} - y_{1_{i}}))

Subtask 2

Maintain two grids: one that counts the number of horizontal lines at a given point and the other for the number of vertical lines.

Iterate through the grid and sum the number of horizontal lines multiplied by the number of vertical lines at any given point.

Time Complexity: \mathcal{O}((\max(x_{2_{i}}) - \min(x_{1_{i}})) \times (\max(y_{2_{i}}) - \min(y_{1_{i}})))

Subtask 3

Perform a line sweep on the x-coordinate of the start and end points of horizontal lines and the x-coordinate of the vertical lines.

Maintain a data structure (e.g. segment tree or Fenwick tree) that can support point-update and range queries.

First, perform coordinate compression on the x-coordinates and y-coordinates to support them in your data structure (or use an implicit segment tree).

When you encounter the start point of a horizontal line, add 1 to the frequency at the y-coordinate in the data structure.

When you encounter the end point of a horizontal line, subtract 1 to the frequency at the y-coordinate in the data structure.

When you encounter a vertical line, query the sum of lines in [y_{1_{i}}, y_{2_{i}}] in the data structure.

Note that you should be cautious of the order you process the lines: break ties in x-coordinates based on the type with start points of horizontal lines first, vertical lines, and finally, end points of horizontal lines.

Time Complexity: \mathcal{O}(N \log(N))


There are no comments at the moment.