| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 512 MB | 19 | 7 | 6 | 60.000% |
There are $n$ rectangles on the coordinate plane, with sides parallel to the coordinate axis. The $i$-th rectangle covers all points $(x, y)$ with $l_i \le x \le r_i$ and $d_i \le y \le u_i$.
For simplicity, for every $i \neq j,ドル we have $l_i \neq l_j,ドル $r_i \neq r_j,ドル $l_i \neq r_j,ドル $d_i \neq d_j,ドル $u_i \neq u_j,ドル $d_i \neq u_j$.
Count the number of triples $(i, j, k)$ with 1ドル \le i < j < k \le n$ for which $i$-th, $j$-th, and $k$-th rectangles are pairwise disjoint (every pair of them has no common points).
The first line of the input contains a single integer $n$ (1ドル \le n \le 2 \cdot 10^5$), the number of rectangles.
The $i$-th of the next $n$ lines contains four integers describing the $i$-th rectangle: $l_i,ドル $r_i,ドル $d_i,ドル $u_i$ ($-10^9 \le l_i < r_i \le 10^9,ドル $-10^9 \le d_i < u_i \le 10^9$).
It is guaranteed that, for every $i \neq j,ドル we have $l_i \neq l_j,ドル $r_i \neq r_j,ドル $l_i \neq r_j,ドル $d_i \neq d_j,ドル $u_i \neq u_j,ドル $d_i \neq u_j$.
Output the number of triples $(i, j, k)$ with 1ドル \le i < j < k \le n$ for which $i$-th, $j$-th, and $k$-th rectangles are pairwise disjoint.
5 1 5 1 5 4 8 2 6 3 7 3 7 2 6 28 32 42 46 42 46
3
6 1 8 6 10 2 5 3 12 3 4 15 20 0 9 2 22 -5 22 -2 23 -7 11 -1 17
0