分数: 400 点
问题陈述
某宅邸发生了凶杀案。有 N 嫌疑人,被叫人 1, 人 2, \dots, 人 N.
人 i 进入宅邸的时间 S_i,离开宅邸的时间 T_i,其他时间未进出。
有关该犯罪的已知事实如下:
- 罪魁祸首确实有两个。
- 犯罪在某个整数时间开始 x,采取 D 时间单位,完成时间 x + D.
- 两名歹徒从犯罪开始到犯罪完成,一直都在豪宅里。 (他们可能恰好在犯罪开始时进入宅邸,或者在犯罪完成时恰好离开。)
假设两个罪魁祸首都在 N 犯罪嫌疑人,两个凶手和作案开始时间有多少种可能的组合?在这里,两个罪魁祸首的顺序并不重要。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq T_i \leq 10^6
- 1 \leq D \leq 10^6
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N D S_1 T_1 S_2 T_2 \vdots S_N T_N
输出
输出两个罪犯可能的组合数量以及犯罪开始时间。
示例输入 1
3 2 9 17 10 12 13 20
示例输出 1
4
在该样本中,有三名嫌疑人,犯罪花费了两个单位的时间。
- 如果人 1 和 2 是罪魁祸首,他们当时就在豪宅里 10 到时间 12。如果犯罪开始时间是时间 10,犯罪可以在两个时间单位内实施。
- 如果人 1 和 3 是罪魁祸首,他们当时就在豪宅里 13 到时间 17。如果犯罪开始时间是 13, 14,或 15,犯罪可以在两个时间单位内实施。
- 如果人 2 和 3 是凶手,他们从来没有同时在宅邸里,所以这两人不可能作案。
因此,两个罪犯和犯罪开始时间的可能组合为(人 1, 2,时间 10), (人 1, 3,时间 13), (人 1, 3,时间 14), (人 1, 3,时间 15),给出四种组合。
示例输入 2
3 5 9 17 10 12 13 20
示例输出 2
0
嫌疑人与样本输入 1 中的相同,但这次犯罪花费了 5 个单位的时间。
无论哪两人是凶手,他们在宅邸中的时间都比作案所需的时间短,所以作案是不可能的。
因此,两个罪犯和犯罪开始时间的可能组合数为零。 (换句话说,我们的假设是错误的,真正的罪魁祸首已经逃走了。)
示例输入 3
4 1 1 1000000 1 1000000 1 1000000 1 1000000
示例输出 3
5999994
注意较大情况下的溢出。