← 返回题目列表

AtCoder · abc462_d

D. 同谋

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

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

注意较大情况下的溢出。