AT_abc207_c [ABC207C] Many Segments

[problemUrl]: https://atcoder.jp/contests/abc207/tasks/abc207_c $ 1 $ から $ N $ までの番号が付いた $ N $ 個の区間が与えられます。区間 $ i $ は、 - $ t_i=1 $ なら $ [l_i,r_i] $ - $ t_i=2 $ なら $ [l_i,r_i) $ - $ t_i=3 $ なら $ (l_i,r_i] $ - $ t_i=4 $ なら $ (l_i,r_i) $ です。 $ 1\ \leq\ i\ \lt\ j\ \leq\ N $ を満たす整数の組 $ (i,j) $ のうち、区間 $ i $ と区間 $ j $ が共通部分を持つようなものは幾つありますか？ 区間 $ [X,Y],[X,Y),(X,Y],(X,Y) $ とは？- 閉区間 $ [X,Y] $ は、 $ X $ 以上 $ Y $ 以下の全ての実数からなる区間 - 半開区間 $ [X,Y) $ は、 $ X $ 以上 $ Y $ 未満の全ての実数からなる区間 - 半開区間 $ (X,Y] $ は、 $ X $ より大きく $ Y $ 以下の全ての実数からなる区間 - 開区間 $ (X,Y) $ は、 $ X $ より大きく $ Y $ 未満の全ての実数からなる区間 を表します。一言で言うと、角括弧 $ [] $ を使っている側は端点を含み、丸括弧 $ () $ を使っている側は端点を含みません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ t_1 $ $ l_1 $ $ r_1 $ $ t_2 $ $ l_2 $ $ r_2 $ $ \hspace{1cm}\vdots $ $ t_N $ $ l_N $ $ r_N $

区間 $ i $ と区間 $ j $ が共通部分を持つような整数の組 $ (i,j) $ の個数を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ 1\ \leq\ t_i\ \leq\ 4 $ - $ 1\ \leq\ l_i\ \lt\ r_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 問題文中の定義より、区間 $ 1 $ は $ [1,2] $, 区間 $ 2 $ は $ [2,3) $, 区間 $ 3 $ は $ (2,4] $ です。 区間 $ i $ と区間 $ j $ が共通部分を持つような整数の組 $ (i,j) $ は、$ (1,2) $ と $ (2,3) $ の $ 2 $ つとなります。それぞれ、$ [2,2] $ と $ (2,3) $ を共通部分として持っています。