Problem: 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.

Submission attempts (in order):
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
damage = np.array([0]*N)
b = 0
for i in range(N):
  if damage[i]>=xh[i, 1]:
    continue
  x, h = xh[i]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  damage[:bisect.bisect_right(xh[:, 0], r, i, N)] += times*A
  b += times
print(b)

import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  print(ds)
  b += times
print(b)

import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(x, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=int32)
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = h//A if h%A==0 else h//A+1
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
# Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Accepted