← 返回题目列表

AtCoder · abc024_b

B. 自动门

中文机器翻译题面 查看原题

問題文

ABC Market是高桥王国最受欢迎的超市。 入口处设有自动门。

当有人经过时,这扇自动门会自动打开,然后从那里 它将保持打开状态直到 T 秒,然后自动关闭。 当门打开时有新人经过时, 其保持打开状态 T 秒的时间将会延长。

今天是诺贝 N 一位顾客经过自动门。 i 人经过的时间是ABC Market开盘后。 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