分数: 300 点
问题陈述
你被给予 N 间隔编号 1 通过 N,如下:
- if t_i=1,间隔 i is [l_i,r_i];
- if t_i=2,间隔 i is [l_i,r_i);
- if t_i=3,间隔 i is (l_i,r_i];
- if t_i=4,间隔 i is (l_i,r_i).
有多少对整数 (i,j) 满意 1 \leq i \lt j \leq N 是否存在这样的间隔 i 和间隔 j 相交?
什么是 [X,Y],[X,Y),(X,Y],(X,Y)?
- 闭区间 [X,Y] 是由所有实数组成的区间 x 这样 X \leq x \leq Y.
- 半开区间 [X,Y) 是由所有实数组成的区间 x 这样 X \leq x < Y.
- 半开区间 (X,Y] 是由所有实数组成的区间 x 这样 X < x \leq Y.
- 开区间 (X,Y) 是由所有实数组成的区间 x 这样 X < x < Y.
约束
- 2 \leq N \leq 2000
- 1 \leq t_i \leq 4
- 1 \leq l_i \lt r_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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 相交。
示例输入 1
3 1 1 2 2 2 3 3 2 4
示例输出 1
2
如问题陈述中所定义,间隔 1 is [1,2],间隔 2 is [2,3)和间隔 3 is (2,4].
有两对整数 (i,j) 使得间隔 i 和间隔 j 相交: (1,2) 和 (2,3)。对于第一对,交集是 [2,2],对于第二对,交集是 (2,3).
示例输入 2
19 4 210068409 221208102 4 16698200 910945203 4 76268400 259148323 4 370943597 566244098 1 428897569 509621647 4 250946752 823720939 1 642505376 868415584 2 619091266 868230936 2 306543999 654038915 4 486033777 715789416 1 527225177 583184546 2 885292456 900938599 3 264004185 486613484 2 345310564 818091848 1 152544274 521564293 4 13819154 555218434 3 507364086 545932412 4 797872271 935850549 2 415488246 685203817
示例输出 2
102