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):
from math import *

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)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max-1:n_max+n-1] = (h for _, h in p)

def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

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 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)
 

init2()
#for i, (_, h) in enumerate(p):
#  init(i, i+1, h)
c = 0
j = 0
import pdb; pdb.set_trace()
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 and p[j][0] - x <= 2 * d + 1:
    j += 1
  add(i, j, -m)
print(c)

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)

from math import *

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)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max:n_max+n] = p
def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

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)
 

init2()
#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)

from math import *

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)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max-1:n_max+n-1] = (h for _, h in p)

def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

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)
 

init2()
#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)

from math import *

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)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max-1:n_max+n-1] = (h for _, h in p)

def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

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)
 

init2()
#for i, (_, h) in enumerate(p):
#  init(i, i+1, h)
print(health)
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)

from math import *

n, d, a = map(int, input().split())
damage_diff = [0] * n
damage = 0
p = sorted(tuple(map(int, input().split())) for _ in range(n))

j = 0
c = 0

for i in range(n):
  damage -= damage_diff[i]
  
  x, h = p[i]
  h -= damage
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j < n and p[j][0] - x <= 2 * d:
    j += 1

  if j < n:
    damage_diff[j] += m
  damage += m
print(c)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted