P11048 [Lanqiao Cup 2024 NOI Qualifier Java B] Build a Cross

Note: For the original problem (Java), the time limit is 3.0 s and the memory limit is 512 MB.

In the mysterious ancient forest of LQ Kingdom, there is a mysterious ruin called “Build a Cross”. It is said that “Build a Cross” was built by an ancient civilization. It is a huge stone structure formed by stacking two large rectangles so that they cross each other, creating a solemn and mysterious cross shape.  Now you are given $N$ rectangles. For the $i$-th rectangle, its length and width are $l_i$ and $w_i$, and its color $c_i$ is one of red $(0)$, yellow $(1)$, or blue $(2)$. Now Xiaolan wants to know how many pairs among these $N$ rectangles can “build a cross”. Two rectangles can “build a cross” if and only if: 1. The two rectangles have different colors. 2. Rectangle $1$ has a strictly greater length than rectangle $2$, and rectangle $1$ has a strictly smaller width than rectangle $2$. Note that the length and width of a rectangle are fixed and cannot be swapped by rotating the rectangle.

The first line contains an integer $N$, meaning there are $N$ rectangles. The next $N$ lines each contain three integers $l$, $w$, and $c$, representing the length, width, and color of a rectangle.

Output one integer, the answer. Since the answer may be very large, output it modulo $10^9 + 7$.

[Sample Explanation] The 3rd rectangle can build a cross with the 1st rectangle, and the 3rd rectangle can also build a cross with the 4th rectangle. So there are 2 pairs of rectangles that can build a cross, and the answer is $2$. [Constraints] - For $30\%$ of the testdata: $1 \leq N \leq 5000$. - For $100\%$ of the testdata: $1 \leq N \leq 10^5$, $1 \leq l,w \leq 10^5$, $0 \leq c \leq 2$. Translated by ChatGPT 5