Problem link : contest practice Difficulty : Hard Prerequisites : 2D data structures, segment trees Solution : Let's start with the following claim: two rectangles intersect if and only if their projections on the coordinate axes intersect. This is an observation that isn't hard to come up with, and that can be easily reasoned. Let's consider the following problem, where we have to manage answering two types of queries:
This problem can be solved with the following approach:
How to calculate the number of the rectangles that don't intersect with the given one (denoted by its' projections Xl, Xr and Yl, Yr)? From the first glance, we might say that is: the total number of the rectangles, minus the number of rectangles with the Xaxis projection, not intersecting [Xl, Xr], minus the number of rectangles with the Yaxis projection, not intersecting [Yl, Yr]. But this is wrong, because some of the rectangles might be subtracted twice. To be exact, those that don't intersect with the both of the projections. There are four symmetric cases for such rectangles. Let's consider one of these cases, for example those when the both top/right most coordinates of the rectangle (and the projection respectively) are smaller than the bottom/left most coordinates of the rectangle (and the projection as well). Actually, we can simply calculate the number of such rectangles by counting the number of the rectangles with the topright corner inside the rectangle (1, 1, Xl1, Yl1). So now the problem becomes a standard one and you only have to:
There are generally a lot of ways to do it. Take a look at the setter's/tester's solutions for the details in case you're unfamiliar how to do so. Though, there are really a lot of ways, so everyone can find the most convenient one for himself. The tester prefers 2D Fenwick tree+SQRT decomposition. This approach is capable of achieving the maximal runtime of ~0.7 on the given test cases. The described case is one of four, the rest has exactly the same logic. The main difficulty of the problem is to code everything clear and correct, but only the practice helps to become stronger in the "techical" problems :) Setter's solution : link Tester's solution: link
This question is marked "community wiki".
asked 15 Sep '14, 15:41

I have a O(n log^2(n)) solution which got TLE during the contest. I compared my solution with the slower ones which got AC, and on randomly generated test files, my code is as fast as theirs (abs(difference) < 0.5s). Can someone provide with the generator in which my solution performs considerably worse than expected? answered 15 Sep '14, 20:38
try to produce extreme cases. for example, make a case where there are many rectangles with same coordinates. what data structure have you used in your algo?
(15 Sep '14, 21:08)
@pushkarmishra, I tried many different test cases. My program is faster*(~0.5s) for random cases. It is slower*(~0.3s) for cases with a lot of queries. Not a lot of difference. I have used 2d segment tree type structure. *In comparison to last 2 ac solutions.
(15 Sep '14, 22:47)
Well.... The time limit was certainly tooo strict....
(15 Sep '14, 23:29)

10^9 is the max co ordinate which is too high for the tree memory bounds, right ? So how do we tackle that while using a fenwick tree ? Some special hashing ? .... Or have I misunderstood the implementation and gone completely off track here ? answered 25 Sep '14, 17:26
