Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
from math import *
import bisect
n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0

def init(a, b, h, k=0, l=0, r=n_max):
  if b <= l or r <= a:
    return health[k]
  health[k] = health[k] + h
  if r - l <= 1:
    return health[k]
  vl = init(a, b, h, 2 * k + 1, l, (l + r) // 2)
  vr = init(a, b, h, 2 * k + 2, (l + r) // 2, r)
  health[k] = vl + vr
  return health[k]
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l and r <= b:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]

def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)

p = sorted(tuple(map(int, input().split())) for _ in range(n))
for i, (_, h) in enumerate(p):
  init(i, i+1, h)

c = 0
j = 0
for i in range(n):
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j >= n or p[j][0] - x > 2 * d + 1:
    j += 1
  add(i, j, -m)
print(c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    if flag==1:
        h = X[cur][1]+delta
    else:
        h = X[cur][1]+delta+B[cur]
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,ind):
        delta += B[i]
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = ind
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    if flag==1:
        h = X[cur][1]+delta
    else:
        h = X[cur][1]+delta+B[cur]
    if h<=0:
        delta += B[cur]
        flag = 0
        cur += 1
        continue
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,ind):
        delta += B[i]
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = ind
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,ind):
        delta += B[i]
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = ind
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta+B[cur]
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,ind):
        delta += B[i]
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = ind
print(cnt)

Submission status: Wrong Answer

Solution code:
from math import *
import bisect
n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0

def init(a, b, h, k=0, l=0, r=n_max):
  if b <= l or r <= a:
    return health[k]
  health[k] = health[k] + h
  if r - l <= 1:
    return health[k]
  vl = init(a, b, h, 2 * k + 1, l, (l + r) // 2)
  vr = init(a, b, h, 2 * k + 2, (l + r) // 2, r)
  health[k] = vl + vr
  return health[k]
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l and r <= b:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]

def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)

p = sorted(tuple(map(int, input().split())) for _ in range(n))
for i, (_, h) in enumerate(p):
  init(i, i+1, h)

c = 0
for i in range(n):
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  w = bisect.bisect(p, (x+2*d+1, 0))
  add(i, w, -m)
print(c)

Submission status: Wrong Answer

Solution code:
from math import *
import bisect
n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0

def init(a, b, h, k=0, l=0, r=n_max):
  if b <= l or r <= a:
    return health[k]
  health[k] = health[k] + h
  if r - l <= 1:
    return health[k]
  vl = init(a, b, h, 2 * k + 1, l, (l + r) // 2)
  vr = init(a, b, h, 2 * k + 2, (l + r) // 2, r)
  health[k] = vl + vr
  return health[k]
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l or b <= r:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]

def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)

p = sorted(tuple(map(int, input().split())) for _ in range(n))
for i, (_, h) in enumerate(p):
  init(i, i+1, h)

c = 0
for i in range(n):
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  w = bisect.bisect(p, (x+2*d+1, 0))
  add(i, w, -m)
print(c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,ind):
        delta += B[i]
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = ind
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法1 - 貪欲法
"""
キューを使った貪欲法で間に合わせる。
que = [[ダメージ量,そのダメージがどこまで使えるか],...]
とすることにより、高速にダメージ管理をすることができる。
"""

que = deque()
ans = 0
dmg = 0

for i in range(n):
    while que:
        lim = que.popleft()
        if lst1[i][0] > lim[1]:
            dmg -= lim[0]
        else:
            break
    
    if lst1[i][1] > dmg:
        need = math.ceil((lst1[i][1]-dmg)/a)
        ans += need
        dmg += need*a
        que.append([need*a,lst1[i][0]+2*d])

print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
enemies = [list(map(int, input().split())) for _ in range(N)]
enemies.sort(key=lambda x: x[0])
count = 0

for i, e in enumerate(enemies):
  if e[1] <= 0:
    continue
  
  c = (e[1] + (A - 1)) // A
  count += c
  
  for d in enemies[i+1:]:
    if d[0] > e[0] + D * 2 + 1:
      break
    
    d[1] -= c * A
    
print(count)

Submission status: Wrong Answer

Solution code:
from math import *
import bisect
n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0

def init(a, b, h, k=0, l=0, r=n_max):
  if b <= l or r <= a:
    return health[k]
  health[k] = health[k] + h
  if r - l <= 1:
    return health[k]
  vl = init(a, b, h, 2 * k + 1, l, (l + r) // 2)
  vr = init(a, b, h, 2 * k + 2, (l + r) // 2, r)
  health[k] = vl + vr
  return health[k]
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l or b <= r:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]

def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)

p = sorted(tuple(map(int, input().split())) for _ in range(n))
for i, (_, h) in enumerate(p):
  init(i, i+1, h)

c = 0
for i in range(n):
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  w = bisect.bisect(p, (x+2*d+1, 0))
  add(x, w, -m)
print(c)

Submission status: Wrong Answer

Solution code:
import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法2 - imos法
"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""
x = []
for i in lst1:
    x.append(i[0])

#process1
index = 0
reach = []
for i in range(n):
    index = bisect.bisect_left(x,lst1[i][0]+2*d)
    reach.append(index)

#process2
ans = 0
imos = [0]*(n+2) #その座標に効いている魔法の回数(ダメージ量ではない)

for i in range(n):
    if imos[i]*a < lst1[i][1]: #ダメージが足りないなら
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]+1] -= need #届かなくなったとこでマイナス
        ans += need
    imos[i+1] += imos[i] #累積和を逐一とる

print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append([x,h])
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    if XH[i][1]<0:
        continue
    else:
        H=XH[i][1]
        a=problemA(H)
        ans+=a
        for j in range(i+1,N):
            if XH[j][1]>0 and XH[i][0]+2*D>=XH[j][0]:
                XH[j][1]-=a*A
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append((x,h))
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
cnt=[0]*N
for i in range(N):
    for j in range(i+1,N):
        if XH[i][0]+2*D>=XH[j][0]:
            cnt[j]+=problemA(XH[i][1])
        else:
            break
    H=XH[i][1]-cnt[i]*A
    if H>0:
        ans+=problemA(H)
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(i) for i in input().split()]
XH=[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    XH.append((x,h))
XH.sort()

def problemA(H):
    if H%A==0:
        ans=H//A
    else:
        ans=H//A+1
    return ans

ans=0
l=0
cnt=[0]*N
for i in range(N):
    for j in range(i+1,N):
        if XH[i][0]+2*D>=XH[j][0]:
            cnt[j]+=problemA(XH[i][1])

    H=XH[i][1]-cnt[i]*A
    if H>0:
        ans+=problemA(H)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
X = [None]*N
H = [None]*N
XD = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
mg = (np.array(mg)).T
X = mg[0]
H = mg[1]
for i in range(N):
  XD[i] = bisect_right(X[i+1:],X[i]+2*D) + i
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  if H[i]>0:
    k = (H[i]+A-1)//A
    ans +=k
    H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))




bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    # damage = bomb_ruisekiwa[bomb_bisect[i]] * a
    damage = bomb_ruisekiwa[bomb_bisect[i]] * a
    if h[i] - damage > 0:
        bomb = (h[i]-damage)//a + ((h[i]-damage)%a != 0)
    if i == 0:
        bomb_ruisekiwa[i] = bomb
    else:
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Submission status: Wrong Answer

Solution code:
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

print(bomb_bisect)


bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    # damage = bomb_ruisekiwa[bomb_bisect[i]] * a
    damage = bomb_ruisekiwa[bomb_bisect[i]] * a
    if h[i] - damage > 0:
        bomb = (h[i]-damage)//a + ((h[i]-damage)%a != 0)
    if i == 0:
        bomb_ruisekiwa[i] = bomb
    else:
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,d,a = LI()
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,h in xh]
que = deque()
for i,[x,h] in enumerate(xh):
    r = br(X,x+2*d)
    que.append((h,i,r))

ans = 0
lst = [0]*(n+1)
while que:
    h,l,r = que.popleft()
    tmp = max(0,(h - lst[l]) // a)
    ans += tmp
    lst[l] += tmp*a
    lst[r] -= tmp*a
    lst[l+1] += lst[l]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,d,a = LI()
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,h in xh]
que = deque()
for i,[x,h] in enumerate(xh):
    r = br(X,x+2*d)
    que.append((h,i,r))

ans = 0
lst = [0]*(n+1)
while que:
    h,l,r = que.popleft()
    tmp = max(0,(h - lst[l]) // a)
    ans += tmp
    lst[l] += tmp
    lst[r] -= tmp
    lst[l+1] += lst[l]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X = []
H = []
for x,h in XH:
    h = (h+A-1)//A
    X.append(x)
    H.append(h)
if D == 0:
    print(sum(H))
else:
    area = []
    for i in range(N):
        area.append(bisect.bisect_right(X,X[i]+2*D))
    print(area)
    suma = [0 for i in range(N+1)]
    for i in range(N):
        suma[i] += H[i]-suma[i]
        for j in range(i+1,area[i]):
            suma[j] += H[i]-suma[i]
    print(max(suma[:-1]))

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH=[]

for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])

XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]
import numpy as np
from bisect import bisect_left
H=np.array(H)
ans=0
import math
for i in range(N):
  if H[i]<=0:
    continue
  else:
    xj=2*D+X[i]
    j=bisect_left(X, xj)
    att=math.ceil(H[i]/A)
    H[i:(j+1)]-=A*att
    ans+=att
#print(H)
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH=[]

for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])

XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]
import numpy as np
from bisect import bisect_left
H=np.array(H)
ans=0
import math
for i in range(N):
  if H[i]>0:
    xj=2*D+X[i]
    j=bisect_left(X, xj)
    att=math.ceil(H[i]/A)
    H[i:(j+1)]-=A*att
    ans+=att
#print(H)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**11
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M+1)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**18
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0],reverse=True)
i = 0
ans = 0
while i<N:
  k = (mg[i][1]+A-1)//A
  ans +=k
  for j in range(i+1,N):
    if mg[j][0]<=mg[j][0]+2*D:
      mg[j][1]=max(0,mg[j][1]-k*A)
    else:
      break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**12
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M+M-1)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**12
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x-h+d*2*M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**12
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**11
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M+M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d*2*M)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**12
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from bisect import bisect
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,s))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,n))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,h))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,x))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,a))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,d))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=-h//a
    c[i]-=t*a
    c[bisect(z,(x+d+d,10e9))]+=t*a
    s-=t
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=0--max(0,h)//a
    c[i]+=t*a
    c[bisect(z,(x+d+d,0))]-=t*a
    s+=t
print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    enemy = dict()
    for _ in range(n):
        x, h = map(int, read().split())
        enemy[x] = h
    cnt = 0
    while enemy:
        x = np.array(list(enemy.keys()))
        px = x.min()
        ph = enemy[px]
        cnt += (ph + a - 1) // a
        for i in x[(px <= x) & (x <= px + 2 * d)]:
            if enemy[i] > ph:
                enemy[i] -= ph
            else:
                del enemy[i]
        if not enemy:
            break
        x = np.array(list(enemy.keys()))
        px = x.max()
        ph = enemy[px]
        cnt += (ph + a - 1) // a
        for i in x[(px - 2 * d <= x) & (x <= px)]:
            if enemy[i] > ph:
                enemy[i] -= ph
            else:
                del enemy[i]
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import bisect
import sys
input = sys.stdin.readline

N,D,A=map(int,input().split())  

XH=[[0,0] for _ in range(N)]
for i in range(N):
    x,h=map(int,input().split())
    XH[i][0]=x
    XH[i][1]=h
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]



ans=0
S=[0]*(N+1)#累積和


for i in range(N):
    if S[i]<X[i]:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        num=(XH[i][1]-S[i])//A
        if (XH[i][1]-S[i])%A!=0:
            num+=1
        ans+=num
        dam=num*A
        #imosで遅延
        S[Lb]+=dam
        S[Rb]-=dam
    S[i+1]+=S[i]
        
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  h=l[i][1]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j
      tmp=j
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1] if ma[i]!=i else left
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Wrong Answer

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  h=l[i][1]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j
      tmp=j
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Wrong Answer

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
ma=[0]*N
tmp=1
for i in range(N):
  value=0
  x=l[i][0]
  h=l[i][1]
  for j in range(tmp,N):
    if abs(l[j][0]-(x+D))>D:
      ma[i]=j
      tmp=j
      break
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  for j in range(i,ma[i]):
    l[j][1]-=time*A
  ans+=time
print(ans)