409257: GYM103469 I Intellectual Implementation
Description
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).
InputThe 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$$$.
OutputOutput 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.
ExamplesInput5 1 5 1 5 4 8 2 6 3 7 3 7 2 6 28 32 42 46 42 46Output
3Input
6 1 8 6 10 2 5 3 12 3 4 15 20 0 9 2 22 -5 22 -2 23 -7 11 -1 17Output
0