/ 
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
出力
すべての壁を破壊するのに必要なパンチの最少回数を出力せよ。
入力例 1
3 3 1 2 4 7 5 9
出力例 1
2
入力例 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 を破壊する。
入力例 2
3 3 1 2 4 7 4 9
出力例 2
1
入出力例 1 と比べると、壁 3 の範囲が \lbrack 5, 9 \rbrack から \lbrack 4, 9 \rbrack に変わりました。
この場合は \lbrack 2, 4 \rbrack にパンチを放つことで 1 回ですべての壁を破壊できます。
入力例 3
5 2 1 100 1 1000000000 101 1000 9982 44353 1000000000 1000000000
出力例 3
3
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