102303: [AtCoder]ABC230 D - Destroyer Takahashi
Description
Score : $400$ points
Problem Statement
In a town divided into a grid with $N$ rows and $10^9$ columns, there are $N$ walls, numbered $1$ to $N$.
Wall $i$ ranges from the $L_i$-th column to the $R_i$-th column from the left in the $i$-th row from the top. (See also the figure at Sample Input and Output $1$.)
Takahashi has decided to destroy all $N$ walls.
With his superhuman strength, his one punch can damage consecutive $D$ columns at once.
- More formally, he can choose an integer $x$ between $1$ and $10^9 - D + 1$ (inclusive) to damage all walls that exist (or partly exist) in the $x$-th through $(x + D - 1)$-th columns and are not yet destroyed.
When a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.
(See also the figure at Sample Input and Output $1$.)
At least how many times does Takahashi need to punch to destroy all walls?
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq D \leq 10^9$
- $1 \leq L_i \leq R_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $D$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
Output
Print the minimum number of punches needed to destroy all walls.
Sample Input 1
3 3 1 2 4 7 5 9
Sample Output 1
2
The figure below describes the arrangements of walls in Sample Input $1$.
He can destroy all walls with two punches, such as the following. (Below, $\lbrack a, b \rbrack$ denotes the range from the $a$-th through $b$-th columns.)
- First, punch $\lbrack 2, 4 \rbrack$. The walls existing in $\lbrack 2, 4 \rbrack$ ― Walls $1$ and $2$ ― are damaged and destroyed.
- Second, punch $\lbrack 5, 7 \rbrack$. The wall existing in $\lbrack 5, 7 \rbrack$ ― Wall $3$ ― is damaged and destroyed.
It is also possible to destroy all walls with two punches in this way:
- First, punch $\lbrack 7, 9 \rbrack$ to destroy Walls $2$ and $3$.
- Second, punch $\lbrack 1, 3 \rbrack$ to destroy Wall $1$.
Sample Input 2
3 3 1 2 4 7 4 9
Sample Output 2
1
The difference from Sample Input/Output $1$ is that Wall $3$ now covers $\lbrack 4, 9 \rbrack$, not $\lbrack 5, 9 \rbrack$.
In this case, he can punch $\lbrack 2, 4 \rbrack$ to destroy all walls with one punch.
Sample Input 3
5 2 1 100 1 1000000000 101 1000 9982 44353 1000000000 1000000000
Sample Output 3
3
Input
题意翻译
在一个 $N$ 行 $10^9$ 列的网格中有 $N$ 面墙,编号为 $1$ 到 $N$。其中,编号为 $i$ 的墙的左端点位于 $(i,L_i)$ ——即第 $i$ 行第 $L_i$ 列,右端点位于 $(i,R_i)$。 你的拳头一次可以打破 **连续** 的 $D$ 列里面的所有墙,也就是说,如果你用拳头击中了第 $x$ 列,那么所有 一部分在第 $x$ 到第 $x+D-1$ 列里的墙 会被破坏。如果一座墙的一小部分被破坏了,整座墙就会倒塌。问题是,最少你需要打几拳才能让 $N$ 座墙全都倒塌? Translated by @xiaomuyunOutput
问题描述
一个由$N$行和$10^9$列组成的网格中,有$N$堵墙,编号为$1$到$N$。
第$i$堵墙从上数第$i$行的第$L_i$列到第$R_i$列(见样例输入和输出1的图)。
高桥君决定摧毁所有$N$堵墙。
凭借他的超人力量,他的一拳可以同时破坏连续$D$列。
- 更正式地说,他可以选择一个在$1$和$10^9 - D + 1$(包括)之间的整数$x$,来破坏所有存在(或部分存在)在第$x$列到第$(x + D - 1)$列之间的墙,并且这些墙还没有被破坏。
当一部分墙被破坏时,整堵墙都会被拳头的冲击力摧毁。
(见样例输入和输出1的图)。
高桥君至少需要打多少次才能摧毁所有的墙呢?
限制条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq D \leq 10^9$
- $1 \leq L_i \leq R_i \leq 10^9$
- 输入中的所有值都是整数。
输入
从标准输入按照以下格式给出输入:
$N$ $D$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
输出
输出摧毁所有墙所需的最少拳数。
样例输入1
3 3 1 2 4 7 5 9
样例输出1
2
下图描述了样例输入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。
样例输入2
3 3 1 2 4 7 4 9
样例输出2
1
与样例输入/输出1的区别在于,墙3现在覆盖了$\lbrack 4, 9 \rbrack$,而不是$\lbrack 5, 9 \rbrack$。
在这种情况下,他可以打$\lbrack 2, 4 \rbrack$用一次拳摧毁所有墙。
样例输入3
5 2 1 100 1 1000000000 101 1000 9982 44353 1000000000 1000000000
样例输出3
3