Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=[1]
while stack:
    p=stack.pop()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack=[i]+stack

print('Yes')
for i in ans[1:]:
    print(i)

Fixed submission:
from collections import deque
n,m = map(int,input().split())
tree=[[] for _ in range(n+1)]
ans=[0]*n 
for _ in range(m):
    a,b=map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
    
checked=[False]*(n+1)
checked[1]=True
stack=deque([1])
while stack:
    p=stack.popleft()
    for i in tree[p]:
        if checked[i]:
            continue
        ans[i-1]=p
        checked[i]=True
        stack.append(i)

print('Yes')
for i in ans[1:]:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))

ans = 0
for i in range(n):
    x = a[i]
    if x >= n-i:
        continue
    else:
        for j in range(i+x+1,n):
            if a[j]+x == j-i:
                ans += 1
print(ans)

Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
l = [0]*n
r = [0]*n
for i in range(n):
    l[i] = i+a[i]
    r[i] = i-a[i]
    
l=Counter(l)
r=Counter(r)
ans = 0
for i in range(max(r.keys())+1):
    ans += l[i]*r[i]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if a[i]+a[j] == j-i:
            ans += 1
print(ans)

Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
l = [0]*n
r = [0]*n
for i in range(n):
    l[i] = i+a[i]
    r[i] = i-a[i]
    
l=Counter(l)
r=Counter(r)
ans = 0
for i in range(max(r.keys())+1):
    ans += l[i]*r[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
mod = 2019
a = [[int(s[0]),1]]
count = 0
for i in s[1:]:
    b = []
    c = 0
    for j in a:
        d = (j[0]*10+int(i))%2019
        if d == int(i):
            c = 1
            b.append([d,j[1]+1])
            if d == 0:
                count += j[1]+1
        else:
            b.append([d,j[1]])
            if d == 0:
                count += j[1]
    if c == 0:
        b.append([int(i),1])
    a = b
    
print(count)

Fixed submission:
from collections import Counter
s = input()
a = [0]
mod = 2019
for i,j in enumerate(s[::-1]):
    a.append(a[-1]+int(j)*pow(10,i,mod))
    a[-1] %= mod
b = Counter(a)
ans = 0
for i in b.values():
    ans += i*(i-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
dp = [[0]*(len(s)+1) for _ in range(2019)]
mod = 2019
num = 0
for i in s:
    num += 1
    for j in range(2019):
        dp[(j*10+int(i))%mod][num] = dp[j][num-1]
    dp[int(i)][num] += 1
    
print(sum(dp[0]))

Fixed submission:
from collections import Counter
s = input()
a = [0]
mod = 2019
for i,j in enumerate(s[::-1]):
    a.append(a[-1]+int(j)*pow(10,i,mod))
    a[-1] %= mod
b = Counter(a)
ans = 0
for i in b.values():
    ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
dp = [[0]*k for _ in range(n)]
dp[0] = [1]*k

gcd = [[0]*k for _ in range(k)]
for i in range(k):
    for j in range(k):
        if i == j:
            gcd[i][j] = i+1
        else:
            if i > j:
                gcd[i][j] = gcd[i-j-1][j]
            else:
                gcd[i][j] = gcd[i][j-i-1]
        
for i in range(1,n):
    for j in range(k):
        if dp[i-1][j] != 0:
            for l in range(k):
                dp[i][gcd[j][l]-1] += dp[i-1][j]

ans = 0
mod = 10**9+7
for i,j in enumerate(dp[n-1]):
    ans += (i+1)*j
    ans %= mod

print(ans)

Fixed submission:
n,k = map(int,input().split())
dp = [0]*k
mod = 10**9 + 7
ans = 0
for i in range(k,0,-1):
    dp[i-1] += pow(k//i,n,mod)
    for j in range(k//i,1,-1):
        dp[i-1] -= dp[i*j-1]
    ans += dp[i-1]*i
    ans %= mod
    
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
x,y,a,b,c = map(int,input().split())
P = deque(sorted(list(map(int,input().split())),reverse=True)[:x])
Q = deque(sorted(list(map(int,input().split())),reverse=True)[:y])
R = deque(sorted(list(map(int,input().split())),reverse=True))
p = P.pop()
q = Q.pop()
r = R.popleft()
ans = 0
while (p < r or q < r) and r != 0:
    ans += r
    if len(R) != 0:   
        r = R.pop()
    else:
        r = 0
    if p < q:
        if len(p) != 0:   
            p = P.pop()
        else:
            p = 10**10
    else:
        if len(Q) != 0:   
            q = Q.pop()
        else:
            q = 10**10
            
ans += sum(P)+sum(Q)
if p != 10**10:
    ans += p
if q != 10**10:
    ans += q
print(ans)

Fixed submission:
from collections import deque
x,y,a,b,c = map(int,input().split())
P = deque(sorted(list(map(int,input().split())),reverse=True)[:x])
Q = deque(sorted(list(map(int,input().split())),reverse=True)[:y])
R = deque(sorted(list(map(int,input().split())),reverse=True))
p = P.pop()
q = Q.pop()
r = R.popleft()
ans = 0

while p < r or q < r:
    ans += r
    if len(R) != 0:   
        r = R.popleft()
    else:
        r = 0
    if p < q:
        if len(P) != 0:   
            p = P.pop()
        else:
            p = 10**10
    else:
        if len(Q) != 0:   
            q = Q.pop()
        else:
            q = 10**10
            
ans += sum(P)+sum(Q)
if p != 10**10:
    ans += p
if q != 10**10:
    ans += q
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
x,y,a,b,c = map(int,input().split())
P = deque(sorted(list(map(int,input().split())),reverse=True)[:x])
Q = deque(sorted(list(map(int,input().split())),reverse=True)[:y])
R = deque(sorted(list(map(int,input().split())),reverse=True))
p = P.pop()
q = Q.pop()
r = R.popleft()
ans = 0
while (p < r or q < r) and r != 0:
    ans += r
    if len(R) != 0:   
        r = R.pop()
    else:
        r = 0
    if p < q:
        p = P.pop()
    else:
        q = Q.pop()
ans += sum(P)+sum(Q)+p+q
print(ans)

Fixed submission:
from collections import deque
x,y,a,b,c = map(int,input().split())
P = deque(sorted(list(map(int,input().split())),reverse=True)[:x])
Q = deque(sorted(list(map(int,input().split())),reverse=True)[:y])
R = deque(sorted(list(map(int,input().split())),reverse=True))
p = P.pop()
q = Q.pop()
r = R.popleft()
ans = 0

while p < r or q < r:
    ans += r
    if len(R) != 0:   
        r = R.popleft()
    else:
        r = 0
    if p < q:
        if len(P) != 0:   
            p = P.pop()
        else:
            p = 10**10
    else:
        if len(Q) != 0:   
            q = Q.pop()
        else:
            q = 10**10
            
ans += sum(P)+sum(Q)
if p != 10**10:
    ans += p
if q != 10**10:
    ans += q
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[[0]*2 for _ in range(s)] for _ in range(n)]
mod = 998244353
if a[0] <= s:
    dp[0][a[0]-1][0] = 1
    dp[0][a[0]-1][1] = 1

for i in range(1,n):
    for j in range(s):
        if a[i] < j+1:
            dp[i][j][0] = dp[i-1][j-a[i]][0] + dp[i-1][j][0] 
            dp[i][j][1] = dp[i-1][j-a[i]][0] + dp[i-1][j][0] + dp[i-1][j][1]
        elif a[i] == j+1:
            dp[i][j][0] = dp[i-1][j][0] + i + 1
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1] + i + 1
        else:
            dp[i][j][0] = dp[i-1][j][0]
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]
        dp[i][j][0] %= mod   
        dp[i][j][1] %= mod
        
print(dp[n-1][s-1][1])

Fixed submission:
n,s = map(int,input().split())
a = list(map(int,input().split()))
c = [0]*(s+1)
ans = 0
mod = 998244353
for i in range(n):
    c_=c.copy()
    if a[i] <= s:
        for j in range(a[i],s+1):
            c[j] += c_[j-a[i]]
        c[a[i]] += i+1
    ans += c[s]
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
n,p = map(int,input().split())
s = input()
count = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            count += i+1
else:
    u = [0]*p
    u[0] += 1
    for i in range(n):
        u[int(s[i:])%p] += 1
    
    for i in u:
        count += i*(i-1)//2
    
print(count)

Fixed submission:
s = input()

if s[0]==s[1] and s[0]==s[2]:
    print('No')
else:
    print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
s = deque(input())
q = int(input())
for _ in range(q):
    Q = list(map(str,input().split()))
    if int(Q[0]) == 1:
        if len(s) > 1:
            s=deque(list(s)[::-1])
    else:
        if int(Q[1]) == 1:
            s.appendleft(Q[2])
        else:
            s.append(Q[2])

            
print("".join(s))

Fixed submission:
from collections import deque
s = deque(input())
q = int(input())
k = 0

for _ in range(q):
    Q = list(map(str,input().split()))
    if int(Q[0]) == 1:
        if k == 0:
            k = 1
        else:
            k = 0
    else:
        if k == 0:
            if int(Q[1]) == 1:
                s.appendleft(Q[2])
            else:
                s.append(Q[2])
        else:
            if int(Q[1]) == 1:
                s.append(Q[2])
            else:
                s.appendleft(Q[2])


if k == 1:
    s = list(s)[::-1]
    
print("".join(s))
Buggy python submission (verdict: Runtime Error):
N,R=map(int,input().split())
if N >= 10:
    print(R)
else:
    print(R+100*(10-K))

Fixed submission:
N,R=map(int,input().split())
if N >= 10:
    print(R)
else:
    print(R+100*(10-N))
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
x = np.array(sorted(list(map(int, input().split()))),dtype = 'int64')

s = []
for p in range(x[0],x[-1]):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))

Fixed submission:
import numpy as np
N = int(input())
x = np.array(sorted(list(map(int, input().split()))),dtype = 'int64')

s = []
for p in range(x[0],x[-1]+1):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
x = np.array(sorted(list(map(int, input().split()))))

s = []
for p in range(x[0],x[-1]):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))

Fixed submission:
import numpy as np
N = int(input())
x = np.array(sorted(list(map(int, input().split()))),dtype = 'int64')

s = []
for p in range(x[0],x[-1]+1):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
x = np.array(list(map(int, input().split())))

s = []
for p in range(x[0],x[-1]):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))

Fixed submission:
import numpy as np
N = int(input())
x = np.array(sorted(list(map(int, input().split()))),dtype = 'int64')

s = []
for p in range(x[0],x[-1]+1):
    s.append(np.sum((x-p)*(x-p)))
    
print(min(s))
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

def calc(y, n, m):
    if n == 0:
        return 1
    elif n%2 == 0:
        l = calc(y, n/2, m)
        return (l**2)%m
    else:
        return (calc(y, n-1, m)*y)%m
    
def calc2(a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*calc(y, m-2, m))%m

print(2**n-1-calc2(a,10**2+7)-calc2(b,10**2+7))

Fixed submission:
n,a,b = map(int,input().split())
    
def calc(n, a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

m = 10**9+7
x = pow(2,n,m)-1
print((x-calc(n,a,m)-calc(n,b,m))%m)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())

def calc(n, a, m):
    x = 1
    y = 1
    if a > n//2:
        a = n-a
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

m = 10**9+7
if k >= n-1:
    print(calc(2*n-1, n-1, m))
else:
    s = 0
    for i in range(n-k-1):
        s += calc(n-1,i,m)*calc(n,i+1,m)
    print((calc(2*n-1, n-1, m)-s)%m)

Fixed submission:
n,k = map(int,input().split())

def calc(n,m):
    y = [1]*(n+1)
    for i in range(n):
        y[i+1] = (y[i]*(i+1))%m
        
    return y

def calc2(n,a,m,y):
    x = (y[a]*y[n-a])%m
    return (y[n]*pow(x, m-2, m))%m

m = 10**9+7
y = calc(2*n-1,m)
if k >= n-1:
    print(calc2(2*n-1, n-1, m, y))
else:
    s = 0
    for i in range(n-k-1):
        s += calc2(n-1,i,m,y)*calc2(n,i+1,m,y)
    print((calc2(2*n-1, n-1, m, y)-s)%m)

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())

def calc(n, a, m):
    x = 1
    y = 1
    for i in range(a):
        x = (x*(n-i))%m
        y = (y*(i+1))%m
    return (x*pow(y, m-2, m))%m

m = 10**9+7
if k >= n-1:
    print(calc(2*n-1, n-1, m))
else:
    s = 0
    for i in range(n-k-1):
        s += calc(n-1,i,m)*calc(n,i+1,m)
    print((calc(2*n-1, n-1, m)-s)%m)

Fixed submission:
n,k = map(int,input().split())

def calc(n,m):
    y = [1]*(n+1)
    for i in range(n):
        y[i+1] = (y[i]*(i+1))%m
        
    return y

def calc2(n,a,m,y):
    x = (y[a]*y[n-a])%m
    return (y[n]*pow(x, m-2, m))%m

m = 10**9+7
y = calc(2*n-1,m)
if k >= n-1:
    print(calc2(2*n-1, n-1, m, y))
else:
    s = 0
    for i in range(n-k-1):
        s += calc2(n-1,i,m,y)*calc2(n,i+1,m,y)
    print((calc2(2*n-1, n-1, m, y)-s)%m)
Buggy python submission (verdict: Runtime Error):
k,q = map(int,input().split())
d = list(map(int,input().split()))
n = [0]*q
x = n.copy()
m = n.copy()
for i in range(q):
    n[i],x[i],m[i] = map(int,input().split())
    
for i in range(q):
    a = [x[i]%m[i]]*n[i]
    count = 0
    for j in range(n[i]-1):
        a[j+1] = (a[j] + d[j%k])%m[i]
        if a[j+1] > a[j]:
            count+=1
    print(count)

Fixed submission:
import numpy as np

k,q = map(int,input().split())
d = np.array(list(map(int,input().split())))
n = [0]*q
x = n.copy()
m = n.copy()
for i in range(q):
    n[i],x[i],m[i] = map(int,input().split())
    
for i in range(q):
    d_ = d%m[i]
    j = np.sum(d_ * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k])
    s = np.sum(np.sum(d_==0) * ((n[i]-1)//k)) + np.sum(d_[:(n[i]-1)%k]==0)
    count = n[i] - 1 - (j+x[i]%m[i])//m[i] - s
    print(count)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N,K = map(int,input().split())
a = np.array(input().split(),np.int64)
a = np.sort(a)
zero = a[a==0]
pos = a[a>0]
neg = a[a<0]

def f(x):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

right = 10**18
left = -10**18
while right-left>1:
    mid = (right + left)//2
    if f(mid)<K:
        left = mid
    else:
        right = mid
        
print(int(right))

Fixed submission:
A, B, C = map(int, input().split())

if A == B:
  if A == C:
    print('No')
  else:
    print('Yes')
elif A == C:
  print('Yes')
elif B == C:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int,input().split()))

i = 0
ans = 1
while i < N-1:
    for j in range(N-i-1):
        if a[i] == a[i+j+1]:
            ans = 0
            break
    if ans == 0:
        break
    i +=1
    
if ans == 1:
    print('YES')
else:
    print('NO')

Fixed submission:
from collections import Counter

N = int(input())
a = list(map(int,input().split()))
c=Counter(a)
ans = max(c.values())
    
if ans == 1:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
p = list(map(int,input().split()))

s = 0
for i in range(n-k+1):
    a = sum(p[i:i+k])
    if a > s:
        s = a
        
print((s+k)/2)

Fixed submission:
n,k=map(int,input().split())
p = list(map(int,input().split()))

s = 0
a = sum(p[:k])
for i in range(n-k+1):
    if i != 0:
        a = a-p[i-1]+p[i+k-1]
    if a > s:
        s = a
        
print((s+k)/2)
Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
n_len = len(str(n))

x = [1]*(n_len)
for i in range(n_len-1):
    x[i+1] = x[i]*(i+1)

def calc(i,j):
    return x[i]/x[j]/x[i-j]*9**(j)
    
count = 0
non_zero = 0
for ind,i in enumerate(str(n)):
    if i != '0':
        non_zero += 1
        if n_len-ind-1 > k-non_zero:
            count += calc(n_len-ind-1,k-non_zero+1)
        if non_zero < k:
            count += calc(n_len-ind-1,k-non_zero)*(int(i)-1)
        elif non_zero == k:
            count += int(i)
            break
    
print(int(count))

Fixed submission:
n = input()
k = int(input())
n_len = len(n)
dp0 = [[0]*k for i in range(n_len)]
dp1 = [[0]*k for i in range(n_len)]
for i in range(k):
    if i == 0:
        dp0[0][i]=int(n[0])-1
        dp1[0][i]=1
    else:
        dp0[0][i]=0
        dp1[0][i]=0

for i in range(1,n_len):
    for j in range(k):
        if j == 0:
            dp0[i][j]=9 + dp0[i-1][0] + dp1[i-1][0]*min(1,int(n[i]))
            dp1[i][j]=dp1[i-1][0] if int(n[i]) == 0 else 0
        else:
            dp0[i][j]=dp0[i-1][j-1]*9 + dp1[i-1][j-1]*max(0,int(n[i])-1) + dp0[i-1][j] + dp1[i-1][j]*min(1,int(n[i]))
            dp1[i][j]=dp1[i-1][j-1] if int(n[i]) != 0 else dp1[i-1][j]
            
print(dp0[n_len-1][k-1]+dp1[n_len-1][k-1])
Buggy python submission (verdict: Time Limit Exceeded):
r1,c1,r2,c2 = map(int,input().split())

n = [1]*(r2+c2+1)
mod = 10**9 + 7
for i in range(r2+c2):
    n[i+1] = (n[i]*((i+1)%mod))%mod
    
def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

ans = 0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        ans += calc(i,j)
        ans %= mod
        
print(ans)

Fixed submission:
r1,c1,r2,c2 = map(int,input().split())

n = [1]*(r2+c2+3)
mod = 10**9 + 7
for i in range(r2+c2+2):
    n[i+1] = (n[i]*((i+1)%mod))%mod

def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

ans = calc(r2+1,c2+1)-calc(r2+1,c1)-calc(r1,c2+1)+calc(r1,c1)
ans %= mod

print(ans)

Buggy python submission (verdict: Runtime Error):
r1,c1,r2,c2 = map(int,input().split())
n = [[1]*(c2+1) for i in range(r2+1)]
mod = 10**9 + 7
ans = 0
for r in range(r2):
    for c in range(c2):
        n[r+1][c+1] = (n[r][c+1] + n[r+1][c])%mod
        if r >= r1-1 and c >= c1-1:
            ans += n[r+1][c+1]
            ans %= mod
            
print(ans)

Fixed submission:
r1,c1,r2,c2 = map(int,input().split())

n = [1]*(r2+c2+3)
mod = 10**9 + 7
for i in range(r2+c2+2):
    n[i+1] = (n[i]*((i+1)%mod))%mod

def calc(r,c):
    x = n[r+c]%mod
    y = (n[r]*n[c])%mod
    return (x*(pow(y,mod-2,mod)%mod))%mod

ans = calc(r2+1,c2+1)-calc(r2+1,c1)-calc(r1,c2+1)+calc(r1,c1)
ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

def calc(x,h):
    if 2*d >= x[-1]-x[0]:
        b = np.max(h)
        ans = b//a + min(1,b%a)
    else:
        ans1 = h[0]//a + min(1,h[0]%a)
        ans2 = h[-1]//a + min(1,h[-1]%a)
        ans = ans1 + ans2
        h[:np.searchsorted(x,x[0]+2*d,side='right')] -= ans1*a
        h[np.searchsorted(x,x[-1]-2*d,side='left'):] -= ans2*a
        c = np.where(h > 0)[0]
        if len(c) > 0:
            x_ = x[c[0]:c[-1]+1]
            h_ = h[c[0]:c[-1]+1]
            ans += calc(x_,h_)
    
    return ans

print(int(calc(x,h)))

Fixed submission:
from collections import deque
from math import ceil

n,d,a = map(int,input().split())
xh = sorted([list(map(int,input().split())) for _ in range(n)])

q = deque()
ans = 0
count = 0
total = 0
for x,h in xh:
    while q:
        if q[0][0] < x:
            total -= q.popleft()[1]
        else:
            break
    
    if total < ceil(h/a):
        count = ceil(h/a)-total
        ans += count
        total += count
        q.append((x+2*d,count))

print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

def calc(x,h):
    if 2*d >= x[-1]-x[0]:
        b = np.max(h)
        ans = b//a + min(1,b%a)
    else:
        ans1 = h[0]//a + min(1,h[0]%a)
        ans2 = h[-1]//a + min(1,h[-1]%a)
        ans = ans1 + ans2
        h[:np.searchsorted(x,x+2*d,side='right')] -= ans1*a
        h[np.searchsorted(x,x[-1]-2*d,side='left'):] -= ans2*a
        c = np.where(h > 0)[0]
        if len(c) > 0:
            x_ = x[c[0]:c[-1]+1]
            h_ = h[c[0]:c[-1]+1]
            ans += calc(x_,h_)
    
    return ans

print(int(calc(x,h)))

Fixed submission:
from collections import deque
from math import ceil

n,d,a = map(int,input().split())
xh = sorted([list(map(int,input().split())) for _ in range(n)])

q = deque()
ans = 0
count = 0
total = 0
for x,h in xh:
    while q:
        if q[0][0] < x:
            total -= q.popleft()[1]
        else:
            break
    
    if total < ceil(h/a):
        count = ceil(h/a)-total
        ans += count
        total += count
        q.append((x+2*d,count))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ma = max(a)

p = [0]*10**6
for i in a:
    for j in range(2,ma+1):
        count = 0
        while i%j == 0:
            count += 1
            i /= j
        if count > p[j-1]:
            p[j-1] = count
            
k=1
for i in range(10**6):
    if p[i] != 0:
        k *= (i+1)**p[i]

ans = 0
for i in a:
    ans += k/i
    
print(int(ans)%(10**9+7))

Fixed submission:
n = int(input())
a = list(map(int,input().split()))

def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
    
def lcm(x,y):
    return x//gcd(x,y)*y

l = 1
for i in a:
    l = lcm(i,l)
    
ans = 0
for i in a:
    ans += l//i
    
print(ans%(10**9+7))