D - Destroyer Takahashi

Contest Duration: 2021-12-03(Fri) 12:00 - 2021-12-03(Fri) 13:40 (local time) (100 minutes) Back to Home

D - Destroyer Takahashi Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $400$ 点

問題文

$N$ 行 $10^9$ 列の格子状の区画に区切られた街に $N$ 枚の壁があり、 $1$ から $N$ までの番号が割り振られています。
壁 $i$ は上から $i$ 行目、左から $L_i$ 列目から $R_i$ 列目の範囲にあります。(入出力例 $1$ の図も参考にしてください。)

高橋君は $N$ 枚の壁をすべて破壊することにしました。
超人的な腕力を持つ高橋君は、 $1$ 回のパンチで連続する $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$

出力

すべての壁を破壊するのに必要なパンチの最少回数を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

入力例 $1$ に対応する壁の配置を図示したものが下図です。

たとえば次のようにパンチを放つことで、 $2$ 回のパンチですべての壁を破壊することができます。(以下の説明では、 $a$ 列目から $b$ 列目までの範囲を $\lbrack a, b \rbrack$ と表記します。)

まず、 $\lbrack 2, 4 \rbrack$ にパンチを放つ。 $\lbrack 2, 4 \rbrack$ に存在する壁である壁 $1$ と壁 $2$ はダメージを受け、破壊される。
次に $\lbrack 5, 7\rbrack$ にパンチを放つ。 $\lbrack 5, 7\rbrack$ に存在する壁 $3$ はダメージを受け、破壊される。

また、次の方法でもすべての壁を $2$ 回のパンチで破壊することができます。

まず、 $\lbrack 7, 9 \rbrack$ にパンチを放ち、壁 $2$ と壁 $3$ を破壊する。
次に、 $\lbrack 1, 3 \rbrack$ にパンチを放ち、壁 $1$ を破壊する。

入力例 2Copy

Copy

出力例 2Copy

Copy

入出力例 $1$ と比べると、壁 $3$ の範囲が $\lbrack 5, 9 \rbrack$ から $\lbrack 4, 9 \rbrack$ に変わりました。
この場合は $\lbrack 2, 4 \rbrack$ にパンチを放つことで $1$ 回ですべての壁を破壊できます。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

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 3Copy

Copy

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

Sample Output 3Copy

Copy