Editorial for COI '09 #1 Hrastovi

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.

We simplify the original query in the task with $4$ ~4~ queries, one for each side of the rectangle. Each of these $4$ ~4~ queries can be solved in the same way independently. Let us solve the vertical left side $(x_1, y_1)$ ~(x_1, y_1)~ – $(x_1, y_2)$ ~(x_1, y_2)~ for example.

We start by sorting all oaks by their $x$ ~x~ coordinate first, breaking ties by sorting on $y$ ~y~ second. It is easy to see that all points on the vertical left side of the rectangle will be in sequence. Since the sequence is sorted, using binary search we can easily determine where points $(x_1, y_1)$ ~(x_1, y_1)~ and $(x_1, y_2)$ ~(x_1, y_2)~ would be in the sequence. The number of items between those two points in the sequence is then the number of oaks that intersect that vertical side. Care should be taken to account for cases where oaks are in points $(x_1, y_1)$ ~(x_1, y_1)~ and $(x_1, y_2)$ ~(x_1, y_2)~.

The other vertical side is solved by using corresponding points. Horizontal sides are solved by sorting by $y$ ~y~ first, using $x$ ~x~ as the tiebreaker.

Time complexity is $\mathcal O(N \log N + P \log N)$ ~\mathcal O(N \log N + P \log N)~.

Comments

There are no comments at the moment.