Destroyer Takahashi

题目描述

在一个由 $N$ 行和 $10^9$ 列组成的网格小镇中，有 $N$ 面墙，编号为 $1$ 到 $N$。
第 $i$ 面墙位于从上数第 $i$ 行中从左数第 $L_i$ 列到第 $R_i$ 列的范围内。（参见样本输入输出 $1$ 中的图。） Takahashi 决定要摧毁所有 $N$ 面墙。
凭借他的超凡力量，他的一拳可以同时破坏连续的 $D$ 列。

更正式地，他可以选择一个介于 $1$ 到 $10^9 - D + 1$（含）之间的整数 $x$，来对位于第 $x$ 列到第 $(x + D - 1)$ 列（包括部分覆盖在该范围内的）的所有尚未被摧毁的墙造成破坏。

当墙的一部分被破坏时，整面墙会因这一击而被摧毁。
（参见样本输入输出 $1$ 中的图。） Takahashi 至少需要多少次出拳才能摧毁所有墙？

输入格式

输入由标准输入给出，格式如下： $N$ $D$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出格式

输出摧毁所有墙所需的最少出拳次数。

3 3
1 2
4 7
5 9

2

3 3
1 2
4 7
4 9

1

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

3

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq D \leq 10^9$ $1 \leq L_i \leq R_i \leq 10^9$ 输入中的所有值均为整数。下图描述了样本输入 $1$ 中墙的排列情况。 他可以用两拳摧毁所有墙，例如如下方法。（下文中 $\lbrack a, b \rbrack$ 表示从第 $a$ 列到第 $b$ 列的区间。）

首先，出拳 $\lbrack 2, 4 \rbrack$。存在于 $\lbrack 2, 4 \rbrack$ 中的墙 —— 第 1 面和第 2 面 —— 被损坏并摧毁。 其次，出拳 $\lbrack 5, 7 \rbrack$。存在于 $\lbrack 5, 7 \rbrack$ 中的墙 —— 第 3 面 —— 被损坏并摧毁。

也可以通过下面的方式用两拳摧毁所有墙：

首先，出拳 $\lbrack 7, 9 \rbrack$ 来摧毁第 2 面和第 3 面。 其次，出拳 $\lbrack 1, 3 \rbrack$ 来摧毁第 1 面。
与样本输入/输出 $1$ 的区别是第 3 面墙现在覆盖的是 $\lbrack 4, 9 \rbrack$，而不是 $\lbrack 5, 9 \rbrack$.
在这种情况下，他可以出拳 $\lbrack 2, 4 \rbrack$ 来用一次出拳摧毁所有墙。

标签: AtCoder|abc230D

来源

AtCoder|abc230D