For subtask 1, the intended solution is to do exactly what is described in the problem statement. That is, for all pairs of geese, if they both honk at each other, then increment the answers for both of the geese. There are ~\mathcal O(N^2)~ pairs to search through.

Time complexity: ~\mathcal O(N^2)~

For the other subtasks, it is helpful to find an algorithm that can be optimized from ~\mathcal O(N^2)~ to a better time complexity. The algorithm is as follows.

The input contains ~2N~ geese. Each goose can be described by a 2D point and a honking radius. Next, sort the geese by increasing radius, and rotate the coordinate system by ~45^\circ~.

The geese are sorted by increasing radius, and each goose is described by a point and a square. There is no need to keep track of which pairs of geese are mates. In the rest of this editorial, "Goose ~i~" will refer to the ~i^{th}~ goose in the sorted list of geese. Also, goose ~i~ is described by "point ~i~" and "square ~i~".

To get the answer for goose ~i~, simply loop through all of the ~j~ that fit into these 2 cases.

• Case 1, ~i < j~. In this case, goose ~i~'s radius is less than or equal to goose ~j~'s radius. The following are equivalent conditions:

  • Goose ~i~ will fight with goose ~j~.
  • Goose ~i~ is honking at goose ~j~.
  • Point ~j~ is strictly inside square ~i~.

  In summary, if point ~j~ is in square ~i~, then increment the answer for goose ~i~.

• Case 2, ~i > j~. In this case, goose ~i~'s radius is greater than or equal to goose ~j~'s radius. If point ~i~ is strictly inside square ~j~, then increment the answer for goose ~i~.

It takes ~\mathcal O(N)~ time to get the answer for goose ~i~. Overall, this algorithm is ~\mathcal O(N^2)~.

Time complexity: ~\mathcal O(N^2)~ with a better constant

For subtask 2, the intended solution is to optimize the previous solution to run in sub-~\mathcal O(N^2)~ time.

In the naive ~\mathcal O(N^2)~ solution, case 1 will occur ~\mathcal O(N^2)~ times. There is a way to do all of the case 1's in sub-~\mathcal O(N^2)~ time. Design a data structure that supports the following:

• Insert a 2D point.
• Query a rectangle. Return the number of points that are inside the rectangle.

Then use the data structure like this. Query square ~2N~, insert point ~2N~, query square ~2N-1~, insert point ~2N-1~, etc.

The data structure can be implemented with a 2D segment tree that uses ~\mathcal O(C^2)~ memory. Insertion is ~\mathcal O(\log^2 C)~ and query is ~\mathcal O(\log^2 C)~. Overall, the case 1's will take ~\mathcal O(N \log^2 C)~ time.

Similarly, to do the case 2's in sub-~\mathcal O(N^2)~ time, design a data structure that supports the following:

• Insert a rectangle.
• Query a 2D point. Return the number of rectangles that the point is in.

Again, the data structure can be a 2D segment tree.

At this point, all of the case 1's and case 2's are handled. It is time to print the answer.

Time complexity: ~\mathcal O(N \log^2 C)~

Memory complexity: ~\mathcal O(C^2)~

For subtask 3, the intended solution is to memory optimize the subtask 2 solution. However, the author strongly dislikes 2D segment trees, so he used a different approach to solve subtask 3.

Consider a function ~f(lo,hi)~. This function will solve all of the case 1's and case 2's among the geese in the range ~[lo,hi)~. The first observation is to use divide and conquer in the following way:

• If there are fewer than 2 geese in ~[lo,hi)~, then nothing needs to be done.
• Split the range ~[lo,hi)~ into the two ranges ~[lo,mid)~ and ~[mid,hi)~.
• Do the case 1's where goose ~i~ is in ~[lo,mid)~ and goose ~j~ is in ~[mid,hi)~.
• Do the case 2's where goose ~i~ is in ~[mid,hi)~ and goose ~j~ is in ~[lo,mid)~.
• Call ~f(lo,mid)~ and ~f(mid,hi)~. This will do the remaining case 1's and case 2's.

(Insert a diagram when I have time. Maybe it can help the reader visualize what's happening.)

The idea is to get the answer by running ~f(lo,hi)~ on the entire list of geese.

The second observation is that the case 1's can be done quickly. First, insert all of the points in ~[mid,hi)~. Next, query all of the squares in ~[lo,mid)~. This can be done with line sweep, and a 1D segment tree that supports the following:

• Insert a 1D point.
• Query a line segment. Return the number of points in this line segment.
• Reset. That is, remove all 1D points from the data structure.

The line sweep will generate ~\mathcal O(hi-lo)~ events, and it takes ~\mathcal O((hi-lo) \log (hi-lo))~ time to sort them. In the 1D segment tree, insertion is ~\mathcal O(\log C)~ and query is ~\mathcal O(\log C)~. Overall, the time complexity to solve the case 1's is ~\mathcal O((hi-lo) \log (hi-lo) + (hi-lo) \log C)~.

(Note: It is possible to use a BIT instead of a 1D segment tree. The time complexity is the same.)

The third observation is that the case 2's can be done quickly with line sweep. The approach is similar. The time complexity is also ~\mathcal O((hi-lo) \log (hi-lo) + (hi-lo) \log C)~.

At this point, the algorithm is complete. The time complexity of the algorithm can be described as:

$$\displaystyle T(n) = 2 T(n/2) + \mathcal O(n \log n) + \mathcal O(n \log C)$$

The ~2T(n/2)~ comes from recursion. The ~\mathcal O(n \log n)~ comes from creating and sorting the events. The ~\mathcal O(n \log C)~ comes from the 1D segment tree.

The time complexity simplifies to ~\mathcal O(N \log^2 N + N \log N \log C)~.

Time complexity: ~\mathcal O(N \log^2 N + N \log N \log C)~

Memory complexity: ~\mathcal O(N+C)~

Fun fact: This problem was originally supposed to be tle17c7p5, but my ~\mathcal O(N \log C)~ algorithm turned out to be incorrect, and a different problem had to be used for the contest.