The Cells on the Paper
Contest: Codeforces Round 758 (Div.1 + Div. 2)
Difficulty rating: 2800
Tags: binary search, implementation, sortings

On an endless checkered sheet of paper, $$$n$$$ cells are chosen and colored in three colors, where $$$n$$$ is divisible by $$$3$$$. It turns out that there are exactly $$$\frac{n}{3}$$$ marked cells of each of three colors!

Find the largest such $$$k$$$ that it's possible to choose $$$\frac{k}{3}$$$ cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:

- No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be $$$0$$$.
- The $$$i$$$-th rectangle contains all the chosen cells of the $$$i$$$-th color and no chosen cells of other colors, for $$$i = 1, 2, 3$$$.

Input format:
The first line of the input contains a single integer $$$n$$$ — the number of the marked cells ($$$3 \leq n \le 10^5$$$, $$$n$$$ is divisible by 3).

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$; $$$1 \leq c_i \leq 3$$$), where $$$(x_i, y_i)$$$ are the coordinates of the $$$i$$$-th marked cell and $$$c_i$$$ is its color.

It's guaranteed that all cells $$$(x_i, y_i)$$$ in the input are distinct, and that there are exactly $$$\frac{n}{3}$$$ cells of each color.

Output format:
Output a single integer $$$k$$$ — the largest number of cells you can leave.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, it's possible to leave $$$6$$$ cells with indexes $$$1, 5, 6, 7, 8, 9$$$.

In the second sample, it's possible to leave $$$3$$$ cells with indexes $$$1, 2, 3$$$.

Example input:
9
2 3 1
4 1 2
2 1 3
3 4 1
5 3 2
4 4 3
2 4 1
5 2 2
3 5 3

Example output:
6

Example input:
3
1 1 1
2 2 2
3 3 3

Example output:
3

Editorial:
Rectangles in optimal answer always arranged in one of the following ways:
1. horizontally from left to right;
2. divided by «T»: first rectangle is upper than second and third, and the second is to the left of the third;
3. rotations of previous ways.
Lets consider all four rotations and find best answer for arrangements 1 and 2. Additionally, fix the order of colors, they will be $$$3!=6$$$.
Arrangement 1 can be found by binary search on $$$k$$$. Greedily take $$$k$$$ leftmost points of first color and $$$k$$$ rightmost points of third. Check if rectangles does not cross and it is enough points of seconds color between rectangles.
Arrangement 2 is binary search on $$$k$$$ too. Take $$$k$$$ uppermost points of first color, in remaining area take $$$k$$$ leftmost points of second color, check if is enough points of third color in remaining area.
Considering the constant factor, in total solution works in $$$O(36nlogn)$$$.
Bonus. Task can be solved in $$$O(36n + nlogn)$$$. In first, sort all points once by $$$x$$$ and once by $$$y$$$. Arrangement 1 can be solved by two pointers in $$$O(n)$$$. For arrangement 2 let first (upper) rectangle be empty, and all points be divided into two noncrossed rectangles in such way that difference between sizes is minimal possible. Now lets move bottom of first rectangle and remove points of second and third colors from their rectangles keeping difference as minimum as possible. It can be achieved with linked list in $$$O(n)$$$.