← 返回题目列表

AtCoder · abc207_c

C. 许多细分

中文机器翻译题面 查看原题

分数: 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