Rectangle Shrinking
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 2300
Tags: binary search, brute force, data structures, greedy, implementation, two pointers

You have a rectangular grid of height $$$2$$$ and width $$$10^9$$$ consisting of unit cells. There are $$$n$$$ rectangles placed on this grid, and the borders of these rectangles pass along cell borders. The $$$i$$$-th rectangle covers all cells in rows from $$$u_i$$$ to $$$d_i$$$ inclusive and columns from $$$l_i$$$ to $$$r_i$$$ inclusive ($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$). The initial rectangles can intersect, be nested, and coincide arbitrarily.

You should either remove each rectangle, or replace it with any of its non-empty subrectangles. In the latter case, the new subrectangle must lie inside the initial rectangle, and its borders must still pass along cell borders. In particular, it is allowed for the subrectangle to be equal to the initial rectangle.

After that replacement, no two (non-removed) rectangles are allowed to have common cells, and the total area covered with the new rectangles must be as large as possible.

Illustration for the first test case. The initial rectangles are given at the top, the new rectangles are given at the bottom. Rectangle number $$$4$$$ is removed.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of rectangles.

Each of the next $$$n$$$ lines contains four integers $$$u_i, l_i, d_i, r_i$$$ ($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$) — the coordinates of cells located in the top-left and the bottom-right corners of the rectangle, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, first print an integer $$$s$$$ — the largest possible covered by new rectangles area. Then print $$$n$$$ lines with your solution to cover this area.

In the $$$i$$$-th of these lines print four integers $$$u'_i, l'_i, d'_i, r'_i$$$. If you remove the $$$i$$$-th rectangle, print $$$u'_i = l'_i = d'_i = r'_i = 0$$$. Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the $$$i$$$-th rectangle, satisfying $$$u_i \le u'_i \le d'_i \le d_i$$$; $$$l_i \le l'_i \le r'_i \le r_i$$$.

If there are multiple solutions, print any.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
The picture in the statement illustrates the first test case.

Example input:
8
5
1 2 2 4
2 4 2 8
1 4 2 7
1 2 1 2
1 9 1 10
2
1 1 1 10
1 5 1 15
2
1 1 1 10
1 1 1 10
5
1 3 1 7
1 3 1 8
1 1 1 4
1 2 1 7
1 10 1 11
2
1 1 2 10
1 5 1 8
2
1 5 2 10
1 2 1 7
2
1 5 2 10
2 2 2 15
5
2 6 2 7
1 4 2 5
1 5 1 9
1 7 2 10
1 2 1 6

Example output:
15
1 2 2 4
2 5 2 8
1 5 1 7
0 0 0 0
1 9 1 10
15
1 1 1 10
1 11 1 15
10
1 1 1 10
0 0 0 0
10
0 0 0 0
1 8 1 8
1 1 1 4
1 5 1 7
1 10 1 11
20
1 1 2 10
0 0 0 0
15
1 5 2 10
1 2 1 4
20
1 5 1 10
2 2 2 15
16
2 6 2 6
2 4 2 5
0 0 0 0
1 7 2 10
1 2 1 6

Editorial:
It turns out that it is always possible to cover all cells that are covered by the initial rectangles.
If the grid had height $$$1$$$ instead of $$$2$$$, the solution would be fairly simple. Sort the rectangles in non-decreasing order of their left border $$$l_i$$$. Maintain a variable $$$p$$$ denoting the rightmost covered cell. Then, for each rectangle, in order:
• If $$$r_i \le p$$$, remove this rectangle (note that since we process the rectangles in non-decreasing order of $$$l_i$$$, it means that this rectangle is fully covered by other rectangles).
• Otherwise, if $$$l_i \le p$$$, set $$$l_i = p + 1$$$ (shrink the current rectangle). Then, set $$$p = r_i$$$ (this is the new rightmost covered cell).
Let's generalize this approach for a height $$$2$$$ grid. Again, sort the rectangles in non-decreasing order of $$$l_i$$$, and maintain two variables $$$p_1$$$ and $$$p_2$$$ denoting the rightmost covered cell in row $$$1$$$ and row $$$2$$$, respectively. Then, for each rectangle, in order:
• If it is a height $$$1$$$ rectangle (that is, $$$u_i = d_i$$$), proceed similarly to the "height $$$1$$$ grid" case above:   If $$$r_i \le p_{u_i}$$$, remove this rectangle.  Otherwise, if $$$l_i \le p_{u_i}$$$, set $$$l_i = p_{u_i} + 1$$$. Then, set $$$p_{u_i} = r_i$$$.
• If $$$r_i \le p_{u_i}$$$, remove this rectangle.
• Otherwise, if $$$l_i \le p_{u_i}$$$, set $$$l_i = p_{u_i} + 1$$$. Then, set $$$p_{u_i} = r_i$$$.
• If it is a height $$$2$$$ rectangle (that is, $$$u_i = 1$$$ and $$$d_i = 2$$$):   If $$$r_i \le p_1$$$, set $$$u_i = 2$$$ (remove the first row from the rectangle) and go back to the "height $$$1$$$ rectangle" case above.  If $$$r_i \le p_2$$$, set $$$d_i = 1$$$ (remove the second row from the rectangle) and go back to the "height $$$1$$$ rectangle" case above.  Otherwise, consider all processed rectangles $$$j$$$ that have $$$r_j \ge l_i$$$, i.e., intersect the $$$i$$$-th rectangle. If $$$l_j \ge l_i$$$, remove rectangle $$$j$$$; otherwise, shrink rectangle $$$j$$$ by setting $$$r_j = l_i - 1$$$. Finally, set $$$p_1 = p_2 = r_i$$$.
• If $$$r_i \le p_1$$$, set $$$u_i = 2$$$ (remove the first row from the rectangle) and go back to the "height $$$1$$$ rectangle" case above.
• If $$$r_i \le p_2$$$, set $$$d_i = 1$$$ (remove the second row from the rectangle) and go back to the "height $$$1$$$ rectangle" case above.
• Otherwise, consider all processed rectangles $$$j$$$ that have $$$r_j \ge l_i$$$, i.e., intersect the $$$i$$$-th rectangle. If $$$l_j \ge l_i$$$, remove rectangle $$$j$$$; otherwise, shrink rectangle $$$j$$$ by setting $$$r_j = l_i - 1$$$. Finally, set $$$p_1 = p_2 = r_i$$$.
Here, only the last case is tricky and different from our initial "height $$$1$$$ grid" solution, but it is also necessary: in a height $$$2$$$ grid, sometimes we have to shrink rectangles on the right, not only on the left.
Now, if we implement this solution in a straightforward fashion, iterating over all $$$j < i$$$ for every $$$i$$$, we'll arrive at an $$$O(n^2)$$$ solution — again, purely because of the last case. To optimize it, note that once a rectangle is shrinked in this last case, it never has to be shrinked again. Thus, we can maintain all rectangles in a priority queue ordered by their $$$r_i$$$, and once we pop a rectangle from the priority queue, we will never have to push it again, which will help us arrive at an amortized $$$O(n \log n)$$$ solution.
Instead of a priority queue, we can use some stacks as well — one for each row and maybe an extra one for height $$$2$$$ rectangles. The overall time complexity will still be $$$O(n \log n)$$$ due to sorting.