A7687 | Accomplice
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
一起谋杀案发生在某座豪宅中。共有 $N$ 名嫌疑人，分别称为第 $1$ 号人、第 $2$ 号人、$\dots$、第 $N$ 号人。
第 $i$ 号人在时刻 $S_i$ 进入豪宅，在时刻 $T_i$ 离开豪宅，且在其他任何时刻均未进出豪宅。
关于该犯罪事件，已知以下事实：
* 共有且仅有两名凶手；
* 犯罪始于某个整数时刻 $x$，持续 $D$ 个时间单位，并于时刻 $x + D$ 结束；
* 两名凶手在犯罪开始至结束的整个时间段内始终身处豪宅之中。（他们可能恰好在犯罪开始时刻进入豪宅，或恰好在犯罪结束时刻离开豪宅。）
假设两名凶手均来自这 $N$ 名嫌疑人，那么共有多少种可能的“两名凶手组合 + 犯罪开始时刻 $x$”的方案？注意：两名凶手的顺序不重要。
第 $i$ 号人在时刻 $S_i$ 进入豪宅，在时刻 $T_i$ 离开豪宅，且在其他任何时刻均未进出豪宅。
关于该犯罪事件，已知以下事实：
* 共有且仅有两名凶手；
* 犯罪始于某个整数时刻 $x$，持续 $D$ 个时间单位，并于时刻 $x + D$ 结束；
* 两名凶手在犯罪开始至结束的整个时间段内始终身处豪宅之中。（他们可能恰好在犯罪开始时刻进入豪宅，或恰好在犯罪结束时刻离开豪宅。）
假设两名凶手均来自这 $N$ 名嫌疑人，那么共有多少种可能的“两名凶手组合 + 犯罪开始时刻 $x$”的方案？注意：两名凶手的顺序不重要。
输入格式
输入从标准输入中按以下格式给出：
> $N$ $D$
> $S_1$ $T_1$
> $S_2$ $T_2$
> $\vdots$
> $S_N$ $T_N$
> $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
输入 #2
3 5 9 17 10 12 13 20
输出 #2
0
输入 #3
4 1 1 1000000 1 1000000 1 1000000 1 1000000
输出 #3
5999994
**样例 1 解释：**
本样例中有三名嫌疑人，犯罪持续时间为 2 个时间单位。
* 若嫌疑人 $1$ 和 $2$ 是罪犯，则他们两人均在宅邸内的时间段为 $[10, 12]$。若犯罪起始时间为 $10$，则可在 2 个时间单位内完成犯罪。
* 若嫌疑人 $1$ 和 $3$ 是罪犯，则他们两人均在宅邸内的时间段为 $[13, 17]$。若犯罪起始时间为 $13$、$14$ 或 $15$，则可在 2 个时间单位内完成犯罪。
* 若嫌疑人 $2$ 和 $3$ 是罪犯，则他们从未同时出现在宅邸内，因此该组合不可能实施犯罪。
因此，可能的两名罪犯及其犯罪起始时间的组合为：（嫌疑人 $1, 2$，时间 $10$）、（嫌疑人 $1, 3$，时间 $13$）、（嫌疑人 $1, 3$，时间 $14$）、（嫌疑人 $1, 3$，时间 $15$），共四种组合。
**样例 2 解释：**
嫌疑人的出入时间与样例输入 1 相同，但本次犯罪持续时间为 5 个时间单位。
无论哪两名嫌疑人为罪犯，他们共同在宅邸内的时长均短于犯罪所需时间，因此该犯罪不可能发生。
因此，可能的两名罪犯及其犯罪起始时间的组合数为零。（换言之，我们的假设错误，真正的罪犯已逃脱。）
**样例 3 解释：**
注意在较大规模数据下可能发生整数溢出。
### 约束条件
* $2 \leq N \leq 2 \times 10^5$
* $1 \leq S_i \leq T_i \leq 10^6$
* $1 \leq D \leq 10^6$
* 所有输入值均为整数。
本样例中有三名嫌疑人，犯罪持续时间为 2 个时间单位。
* 若嫌疑人 $1$ 和 $2$ 是罪犯，则他们两人均在宅邸内的时间段为 $[10, 12]$。若犯罪起始时间为 $10$，则可在 2 个时间单位内完成犯罪。
* 若嫌疑人 $1$ 和 $3$ 是罪犯，则他们两人均在宅邸内的时间段为 $[13, 17]$。若犯罪起始时间为 $13$、$14$ 或 $15$，则可在 2 个时间单位内完成犯罪。
* 若嫌疑人 $2$ 和 $3$ 是罪犯，则他们从未同时出现在宅邸内，因此该组合不可能实施犯罪。
因此，可能的两名罪犯及其犯罪起始时间的组合为：（嫌疑人 $1, 2$，时间 $10$）、（嫌疑人 $1, 3$，时间 $13$）、（嫌疑人 $1, 3$，时间 $14$）、（嫌疑人 $1, 3$，时间 $15$），共四种组合。
**样例 2 解释：**
嫌疑人的出入时间与样例输入 1 相同，但本次犯罪持续时间为 5 个时间单位。
无论哪两名嫌疑人为罪犯，他们共同在宅邸内的时长均短于犯罪所需时间，因此该犯罪不可能发生。
因此，可能的两名罪犯及其犯罪起始时间的组合数为零。（换言之，我们的假设错误，真正的罪犯已逃脱。）
**样例 3 解释：**
注意在较大规模数据下可能发生整数溢出。
### 约束条件
* $2 \leq N \leq 2 \times 10^5$
* $1 \leq S_i \leq T_i \leq 10^6$
* $1 \leq D \leq 10^6$
* 所有输入值均为整数。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？