Problem:


Score : 300 points

Problem Statement

In a public bath, there is a shower which emits water for T seconds when the switch is pushed.

If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds.
Note that it does not mean that the shower emits water for T additional seconds.

N people will push the switch while passing by the shower.
The i-th person will push the switch t_i seconds after the first person pushes it.

How long will the shower emit water in total?

Constraints

1 ≤ N ≤ 200,000

1 ≤ T ≤ 10^9

0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9

T and each t_i are integers.

Input

Input is given from Standard Input in the following format:

N T
t_1 t_2 ... t_N

Output

Assume that the shower will emit water for a total of X seconds. Print X.

Sample Input 1

2 4
0 3

Sample Output 1

7

Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.

Sample Input 2

2 4
0 5

Sample Output 2

8

One second after the shower stops emission of water triggered by the first person, the switch is pushed again.

Sample Input 3

4 1000000000
0 1000 1000000 1000000000

Sample Output 3

2000000000

Sample Input 4

1 1
0

Sample Output 4

1

Sample Input 5

9 10
0 3 5 7 100 110 200 300 311

Sample Output 5

67



Sample input:
2 4
0 3


Sample output:
7

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
l=list(map(int,input().split()))
time=t
m=[0]
i=1
if len(l)==1:
    print(t)
else:
    while True:
        if l[i]-(time-m[-1])<0:
            time=time-(l[i]-(time-m[1]))+t
        else:
            m.append(time)
            time=t
        if i==n-1:
            break
        i+=1
    print(time if len(m)==1 else sum(m)+time)

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
y=max(a)+10+t
b=[0]*y
c=[0]*y
for i in a:
    b[i]+=1
    b[i+t]-=1
for i in range(len(b)):
    if i!=0:
        b[i]+=b[i-1]
d=[i for i in b if i>0]
print(len(d))

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
y=a[-1]+10+t
b=[0]*y
c=[0]*y
for i in a:
    b[i]+=1
    b[i+t]-=1
for i in range(len(b)):
    if i!=0:
        b[i]+=b[i-1]
d=[i for i in b if i>0]
print(len(d))

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
y=a[-1]+1+t
b=[0]*y
c=[0]*y
for i in a:
    b[i]+=1
    b[i+t]-=1
for i in range(len(b)):
    if i!=0:
        b[i]+=b[i-1]
d=[i for i in b if i>0]
print(len(d))

Submission status: Runtime Error

Solution code:
n,t = map(int,input().split())
a = list(map(int,input().split()))
s = t
for i in range(0,n):
  s += min(t,a[i+1]-a[i])
print(s)

Submission status: Runtime Error

Solution code:
N,T=(i for i in input().split())
t = [int(i) for i in input().split()]
a=0
for b in range(N):
    if t[b] < T
        a = a + t[b]
    else:
        a = a + T

print(a)

Submission status: Runtime Error

Solution code:
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=int(0)
for i in range(0,n):
    if n==i-1:
        ans+=t
        break
    ans+=min(t,a[i+1]-a[i])
print(ans)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split(" "))
t = list(map(int,input().split(" ")))
scope = [[t[0],t[0]+T]]

for i in range(1,N):
	if t[i] < scope[-1][1]:
		scope[-1][1] = t[i] + T

	else:
		scope.appned([t[i],t[i]+T])

total = 0
for begin,end in scope:
	total += (end - begin)

print(total)

Submission status: Runtime Error

Solution code:
def LI(): return [int(x) for x in input().split(" ")]
def LS(): return [str(x) for x in input().split(" ")]
def ItoS(L): return [str(x) for x in L]
def StoI(L): return [int(c) for c in L]


def solve():
    n, t = LI()
    T = LI()
    sentou = [0] * (T[-1] + t + 1)
    
    i = 0
    while i < len(T):
        sentou[T[i]] += 1
        sentou[T[i] + t] -= 1
        i += 1

    j = 1
    while j < len(sentou):
        sentou[j] += sentou[j - 1]
        j += 1

    print(n * t - (sum(sentou) - (sentou.count(1) + len(sentou) - sentou.count(1) - sentou.count(0))))

solve()

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split(" "))
t = list(map(int, input().split(" ")))

shower = 0

for i in range(1, N+1):
    if t[i] >= T:
        shower += T
    else:
        shower += t[i]

print(shower)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().filter(" "))
t = list(map(int, input().filter(" ")))

shower = 0

for i in range(1, N):
    if t[i+1]-t[i] >= T:
        shower += T
    else:
        shower += t[i+1]-t[i]

print(shower)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().filter(" "))
t = list(map(int, input().filter(" ")))

shower = 0

for i in range(1, N+1):
    if t[i+1]-t[i] >= T:
        shower += T
    else:
        shower += t[i+1]-t[i]

print(shower)

Submission status: Runtime Error

Solution code:
a, b, c = map(int, input().split(" "))


for i in range(1, c):
    if (a * i) % b == c:
        print("YES")
        break
else:
    print("NO")

a* (任意の整数) % b = cとできるか？

Submission status: Runtime Error

Solution code:
#N,Tの取得
N,M = map(int, input().split())
#秒のリストを取得
tl = list(map(int, input().split()))

bt = 0 #直前のスイッチを押した時間
gt = T #秒数総和
for t in tl(1:):
    if t - bt > T:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt #スイッチがオンのとき、前回からの経過時間を加算
    bt = t

print(str(gt))

Submission status: Runtime Error

Solution code:
#N,Tの取得
N,T = map(int, input().split()))

#秒のリストを取得
tl = list(map(int, input().split()))

bt = 0 #直前のスイッチを押した時間
gt = T #秒数総和
for t in tl(1:):
    if t - bt > T:
        gt += T #スイッチオフの時はT秒追加
    else:
        gt += t - bt #スイッチがオンのとき、前回からの経過時間を加算
    bt = t

print(str(gt))

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split(' '))
tlist = map(int, input().split(' '))

sum_time = 0
for i in range(1, len(tlist)):
    delta = tlist[i] - tlist[i-1]
    shower = delta if delta <= t else t
    sum_time += shower
sum_time += t
print(sum_time)

Submission status: Runtime Error

Solution code:
ini=map(int,raw_input().split())
a=map(int,raw_input().split())

sum=0

for i in range(ini[0]):
  if a{i]==0:
    pass
  else:
    if a[i]-a[i-1]>=ini[1]:
      sum+=ini[1]
    else:
      sum+= a[i]-a[i-1]

sum+=ini[1]

print sum

Submission status: Runtime Error

Solution code:

N, T =map(int, input().split())
ts =map(int, input().split())



amount =0


    
for index in range(N-1):
    t_sub = ts[index+1]-ts[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N,T =map(int,input().split())
t = map(int,input().split())
amount =0


    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N,T =map(int,input().split())
t = map(int,input().split())
amount =0


    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:

N,T =map(int,input().split())
t = input().split()
amount =0


    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
t = input().split()
amount =0

if t[0] <= T:
    amount+=t[0]
else:
    amount+=T
    
for index in range(N-1):
    t_sub = int(t[index+1])-int(t[index])
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split)
t = input().split()
int(amount) =0

if t[0] <= T:
    amount+=t[0]
else:
    amount+=T
    
for index in range(N-1):
    t_sub = int(t[index+1])-int(t[index])
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split)
t = input().split()
amount =0

if t[0] <= T:
    amount+=t[0]
else:
    amount+=T
    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
ts = list(map(int, input().split()))
s = 0;
for i in range(N):
    s += min(ts[i + 1], T)
print(s)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
t = list(map(str, input().split()))

_all = N * T
sabun = 0

for i in range(0, N):
    if T < t[i]:
        sabun += 0
    else:
        sabun += T - t[i]

print(_all - sabun)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
t = list(map(str, input().split()))

_all = N * T
sabun = 0

for i in range(0, N):
    if T < t[i]:
        sabun += 0
    elif:
        sabun += T - t[i]

print(_all - sabun)

Submission status: Runtime Error

Solution code:
##N T
#t1 t2 ... tN
N, T = map(int,input().split())
a = list(map(int, input().split()))
b = []
"""
for i in range(N):
    set1 = set()
    for j in range(T):
        set1.add(a[i] + j)
    b.append(set1)
d = set()
for n in range(len(b)):
    d = d | b[n]
"""
d = set()
for i in xrange(N):
    d = d | set(xrange(a[i], a[i] + T))


print(len(d))

Submission status: Runtime Error

Solution code:
N, T = list(map(int, input().split()))
t =  [int(input()) for i in range(N)]
ans = N*T
for i in t:
    if i < T:
        ans -= T - i
print(ans)

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
ti = map(int, input().split())
ttl = t
for i in range(n-1):
    ttl += min(ti[i+1]-ti[i], t)
print(ttl)