B - 自動ドア
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。
この自動ドアは人が前を通りかかると自動で開き、そこから T 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに T 秒後まで開き続ける時間が延長されます。
今日はのべ N 人の客が自動ドアの前を通りかかりました。 i 番目の人が通りかかった時刻はABCマーケットが開店してから A_i 秒経った時刻です。
今日、この自動ドアが開いていた合計秒数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 A_2 : A_N
- 1 行目に今日自動ドアの前を通りかかった人数を表す整数 N(1 ≦ N ≦ 10^5) とドアが開き続ける時間を表す整数 T(1 ≦ T ≦ 10^5) が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の客が自動ドアの前を通りかかった時刻 A_i(1 ≦ A_i ≦ 10^6) が与えられる。
- A_1 ≦ A_2 ≦ … ≦ A_N が成り立つ。
部分点
この問題には部分点が設定されている。
- 1 ≦ T ≦ 100を満たすデータセットに正解した場合は 50 点が与えられる。
- 1 ≦ T ≦ 10^5を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。
出力
ドアが開いていた秒数を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
5 10 20 100 105 217 314
出力例1
45
時刻が 20 ~ 30、100 ~ 115、217 ~ 227、314 ~ 324 のときにドアが開いています。
入力例2
10 10 1 2 3 4 5 6 7 8 9 10
出力例2
19
入力例3
10 100000 3 31 314 3141 31415 314159 400000 410000 500000 777777
出力例3
517253