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 *

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)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import deque

N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

q = deque([])
s = 0

ans = 0
for i in range(N):
  print(q)
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import deque

N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

q = deque([])
s = 0

ans = 0
for i in range(N):
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  num_bombs = ceil(h / A)

  q.append((monsters[i][0] + 2 * D, num_bombs))
  s += num_bombs
  ans += num_bombs
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
ans = 0
a,s = 0,0
for i in range(N):
    x,h = L1[i]
    h -= a
    if h > 0:
        ans += h
        a += h
    if L2[s] == i:
        a -= L1[s][1]
        s += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, D, A = [int(i) for i in input().split()]
AB = np.array([list(map(int, input().split())) for _ in range(N)])
Xn = AB[:, 0]
inds =np.argsort(Xn)
Xn = Xn[inds]
Hn = AB[:, 1][inds]


for n in range(N):
  if n == 0:
    n_bomb = (Hn[n] + A - 1)//A
    n_bombs = n_bomb
    ri = Xn[n] + 2 * D
    rem_damage = n_bomb * A
  else:
    rem_damage = rem_damage if Xn[n] <= ri else 0
    n_bomb = (Hn[n] - rem_damage + A - 1)//A
    if n_bomb > 0:
      n_bombs += n_bomb
      ri = Xn[n] + 2 * D
      rem_damage = n_bomb * A
print(n_bombs)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, D, A = [int(i) for i in input().split()]
AB = np.array([list(map(int, input().split())) for _ in range(N)])
Xn = AB[:, 0]
inds =np.argsort(Xn)
Xn = Xn[inds]
Hn = AB[:, 1][inds]


for n in range(N):
  n_bomb = (Hn[n] + A - 1)//A
  if n == 0:
    n_bombs = n_bomb
    ri = Xn[n] + 2 * D
    cur_bombs = n_bomb
  else:
    n_bomb = n_bomb - (cur_bombs if Xn[n] <= ri else 0)
    if n_bomb > 0:
      n_bombs += n_bomb
      ri = Xn[n] + 2 * D
      cur_bombs = n_bomb
print(n_bombs)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
p = []
for i in range(n):
    x, h = map(int, input().split())
    p.append((x, h))

from collections import deque

p.sort()

q = deque()
total = 0
ans = 0
for i in range(n):
    x, h = p[i][0], p[i][1]
    while q and q[0][0] <= x:
        total -= q[0][1]
        q.popleft()
    h -= total
    if h > 0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        total += damage
        q.append((x+2*d, damage))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  #t = (T.get(i, i) - 1) // A + 1
  t = 1
  if t <= 0: continue
  ans += t
  #T.add(i, p, -t * A)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  #t = (T.get(i, i) - 1) // A + 1
  t = 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N,D,A = map(int,input().split())
mons = []
X = []
need = [0]*N

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

for i in range(N):
    X.append(mons[i][0])
    need[i] = mons[i][1] // A
    if mons[i][1] % A != 0: need[i] += 1

eliminated = 0
target = 0
ans = 0
while eliminated < N:
    need_bomb = need[target]
    bomb_range = bisect.bisect_right(X,X[target] + 2*D)
    kouho = []
    for i in range(target,bomb_range):
        need[i] -= need_bomb
        if need[i] <= 0:
            eliminated += 1
        else:
            kouho.append(i)
    if len(kouho) > 0:
        target = kouho[0]
    elif eliminated < N:
        target = bomb_range
    ans += need_bomb
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  #T.add(i, p, -t * A)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N,D,A = map(int,input().split())
mons = []
X = []; H = []
need = [0]*N

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

for i in range(N):
    X.append(mons[i][0]); H.append(mons[i][1])
    need[i] = mons[i][1] // A
    if mons[i][1] % A != 0: need[i] += 1

eliminated = 0
target = 0
ans = 0
while eliminated < N:
    need_bomb = need[target]
    bomb_range = bisect.bisect_right(X,X[target] + 2*D)
    for i in range(target,bomb_range):
        need[i] -= need_bomb
        if need[i] <= 0:
            eliminated += 1
            target += 1
    ans += need_bomb
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N,D,A = map(int,input().split())
mons = []
X = []; H = []
need = [0]*N

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

for i in range(N):
    X.append(mons[i][0]); H.append(mons[i][1])
    need[i] = h // A
    if h % A != 0: need[i] += 1

eliminated = 0
target = 0
ans = 0
while eliminated < N:
    for i in range(target,N):
        if need[i] > 0:
            target = i
            break
        else:
            eliminated += 1
    need_bomb = need[target]
    bomb_range = bisect.bisect_right(X,X[target] + 2*D)
    for i in range(target,bomb_range):
        need[i] -= need_bomb
    ans += need_bomb
print(ans)

Submission status: Wrong Answer

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

d *= 2
monster.sort()

count = 0
damage_total = 0
q = deque([])

for i in range(n):
    x = monster[i][0]
    h = monster[i][1]
    if len(q) > 0 and q[0][0] < x:
        damage_total -= q[0][1]
        q.popleft()

    h -= damage_total
    if h > 0:
        count_now = (h + a - 1) // a
        count += count_now
        damage_now = a * count_now
        damage_total += damage_now
        q.append([x + d, damage_now])

print(count)

Submission status: Wrong Answer

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

d *= 2
monster.sort()

count = 0
damage_total = 0
q = deque([])
for i in range(n):
    x = monster[i][0]
    h = monster[i][1]
    if len(q) > 0 and q[0][0] < x:
        damage_total -= q[0][1]
        q.popleft()

    h -= damage_total
    if h > 0:
        count_now = (h + a - 1) // a
        count += count_now
        damage_now = a * count_now
        damage_total += damage_now
        q.append([x + d, damage_now])

print(count)

Submission status: Wrong Answer

Solution code:
from math import ceil

N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

ans = 0
for i in range(N):
  if monsters[i][1] > 0:
    num_bomb = ceil(monsters[i][1] / A)
    ans += num_bomb

    j = i
    while j < N and monsters[j][0] <= monsters[i][0] + 2*D:
      monsters[j][1] -= ceil(num_bomb / A) * A
      j += 1
    

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]
x=[]
lis.sort()
for i in range(n):
  x.append(lis[i][0])
ran,cnt=2*d,0
s=[0]*(n+1)
i,j,k=0,0,0
while i<n:
  r=lis[i][0]+ran
  inde=bisect_right(x,r)
  while j<inde:
    if ceil(lis[j][1]/a)>cnt:
      k=max(k,bisect_right(x,lis[j][0]+ran))
      s[bisect_right(x,lis[j][0]+ran)]+=ceil(lis[j][1]/a)-cnt
      cnt=ceil(lis[j][1]/a)
    j+=1
  if k<=inde:
    cnt=0
  i=j
  k=0
for i in range(n):
  s[i+1]+=s[i]
print(s[n])

Submission status: Wrong Answer

Solution code:
def sol():
    import sys
    input=sys.stdin.readline
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd-1:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
                if w[i+j][1]>0:
                    break
    print(p[2])
if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    print(p[2])
"""
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd-1:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd-1:
                w[i+j][1]-=p[1]
"""

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
import bisect
N, D, A = map(int, input().split())
lst = []
lst_1 = []
lst_2 = []
q = deque()

for i in range(N):
	X, H = map(int, input().split())
	lst.append([X, H])
	
lst.sort(key = lambda x : x[0])

for i in range(N):
	lst_1.append(lst[i][0])
	lst_2.append(lst[i][1])
	
tot = 0
ans = 0
	
for i in range(N):
	x = lst_1[i]
	hp = lst_2[i]
	while q and q[0][0] < x:
		a, b = q.pop()
		tot -= b
	hp -= tot
	
	if hp > 0:
		num = (hp + A - 1) // A
		ans += num
		damage = num * A
		tot += damage
		q.append([x + 2 * D, damage])
		
print(ans)

Submission status: Wrong Answer

Solution code:
def sol():
    n,d,a=map(int,input().split())
    dd=d*2+1
    w=[]
    for i in range(n):
        x,h=map(int,input().split())
        w.append([x,h])
    w.sort()
    ans=0
    p=[0,0,0] #left,left_atack,ans
    i=-1
    while 1:
        i+=1
        if i>=n: break
        if w[i][1]<=0: continue
        p[0]=w[i][0]
        p[1]=((w[i][1]+a-1)//a)*a
        p[2]+=(w[i][1]+a-1)//a
        w[i][1]-=p[1]
        j=0
        while 1:
            j+=1
            if i+j>n-1 or w[i+j][0]>p[0]+dd:
                break
            elif i+j<=n-1 and w[i+j][0]<=p[0]+dd:
                w[i+j][1]-=p[1]
    print(p[2])

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]
x=[]
lis.sort()
for i in range(n):
  x.append(lis[i][0])
ran,ans,cnt=2*d,0,0
s=[0]*(n+1)
for i in range(n):
  r=lis[i][0]+ran
  inde=bisect_right(x,r)
  if inde!=i+1:
    if ceil(lis[i][1]/a)>cnt:
      s[inde]+=ceil(lis[i][1]/a)-cnt
      cnt=ceil(lis[i][1]/a)
  else:
    if ceil(lis[i][1]/a)>cnt:
      s[inde]+=ceil(lis[i][1]/a)-cnt
      cnt=0
for i in range(n):
  s[i+1]+=s[i]
print(s[n])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort()

over = [N] * N # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur < N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # これ以降関係のないダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h -= damage
    time = (h+A-1)//A
    answer += time
    damage += A * time
    reset[over[i]] += A * time

print(answer)
# 00

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
dd=d*2+1
w=[]
for i in range(n):
    x,h=map(int,input().split())
    w.append([x,h])
w.sort()
ans=0
p=[0,0,0] #left,left_atack,ans
i=-1
while 1:
    i+=1
    if i>=n: break
    if w[i][1]<=0: continue
    p[0]=w[i][0]
    p[1]=((w[i][1]+a-1)//a)*a
    p[2]+=(w[i][1]+a-1)//a
    w[i][1]-=p[1]
    j=0
    while 1:
        j+=1
        if i+j>n-1 or w[i+j][0]>p[0]+dd:
            break
        elif i+j<=n-1 and w[i+j][0]<=p[0]+dd:
            w[i+j][1]-=p[1]
print(p[2])

Submission status: Wrong Answer

Solution code:
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(n)]
x=[]
lis.sort()
for i in range(n):
  x.append(lis[i][0])
ran,ans,cnt=2*d,0,0
s=[0]*(n+1)
for i in range(n):
  r=lis[i][0]+ran
  inde=bisect_right(x,r)
  if inde!=i+1:
    if ceil(lis[i][1]/a)>cnt:
      s[inde]+=ceil(lis[i][1]/a)-cnt
      cnt=ceil(lis[i][1]/a)
  else:
    if ceil(lis[i][1]/a)>cnt:
      s[inde]+=ceil(lis[i][1]/a)-cnt
      cnt=0
for i in range(n):
  s[i+1]+=s[i]
print(s[n])

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
dd=d*2+1
w=[]
for i in range(n):
    x,h=map(int,input().split())
    w.append([x,h])
w.sort()
ans=0
p=[0,0,0] #left,left_atack,ans
i=0
for _ in range(n):
    if i>=n: break
    if w[i][1]<=0:
        i+=1
        continue
    p[0]=w[i][0]
    p[1]=((w[i][1]+a-1)//a)*a
    p[2]+=(w[i][1]+a-1)//a
    w[i][1]-=p[1]
    j=0
    while 1:
        j+=1
        if i+j>n-1 or w[i+j][0]>p[0]+dd:
            break
        elif i+j<=n-1 and w[i+j][0]<=p[0]+dd:
            w[i+j][1]-=p[1]
print(p[2])

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
dd=d*2+1
w=[]
for i in range(n):
    x,h=map(int,input().split())
    w.append([x,h])
w.sort()
ans=0
p=[0,0,0] #left,left_atack,ans
i=0
for _ in range(n):
    if i>=n: break
    if w[i][1]<=0:
        i+=1
        continue
    p[0]=w[i][0]
    p[1]=((w[i][1]+a-1)//a)*a
    p[2]+=(w[i][1]+a-1)//a
    w[i][1]-=p[1]
    j=0
    while 1:
        j+=1
        if i+j>n-1:
            break
        elif i+j<=n-1 and w[i+j][0]<=p[0]+dd:
            w[i+j][1]-=p[1]
print(p[2])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.readline

class BIT:
    '''
    区間加算BIT(区間加算・区間合計取得) 
    '''
    def __init__(self, N):
        # 添え字0は使えないので1-indexとして扱う
        N += 1
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N

    def _add(self, data, k, x):
        k += 1
        while k < self.N:
            data[k] += x
            k += k & -k

    def _get(self, data, k):
        k += 1
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        # 区間[l,r)に値xを追加

        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, -x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def query(self, l, r):
        # 区間[l,r)の和を取得
        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
            - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

def main():
    N, D, A = map(int, input().split())
    B = []

    for i in range(N):
        x, h = map(int, input().split())
        B.append((x,h))

    B.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = B[i]

    bit = BIT(N)
    ans = 0
    for i in range(N):
        H[i] -= bit.query(i, i+1)
        if H[i] <= 0:
            continue
        cnt = H[i] // A if H[i] % A == 0 else H[i] // A + 1
        index = bisect_right(X, X[i] + 2 * D)
        bit.add(i, index+1, cnt * A)
        ans += cnt

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh=sorted(xh)
count=0
for i, (x,h) in enumerate(xh):
    if xh[i][1] <= 0:
        continue
    if h%a == 0:
        num = h//a
    else:
        num = (h//a)+1
    count=count+num
    for j in range(i+1, n):
        if xh[j][1] <= 2*d+x:
            xh[j][1] = xh[j][1]-num*a
        else:
            break
print(count)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
xh = sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])


ans = 0
b = 0


while b < n:
    while xh[b][1] <= 0:
        if b == n-1:
            print(ans)
            exit()
        b += 1
    k = -(-xh[b][0]//a)
    for i in range(b ,min(b+ d*2+1,n)):
        if  xh[i][0] <= xh[b][0] + 2*d:
            xh[i][1] -= k*a
        else:
            break
    ans += k
    
    #TLE

Submission status: Wrong Answer

Solution code:
from collections import deque
n, d, a = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort()
d *= 2
ans, tot = 0, 0
q = deque()
for x, h in p:
    while (q and q[-1][0] < x):
        tot -= q[-1][1]
        q.pop()
    h -= tot
    if h>0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        tot += damage
        q.append((x+d, damage))
print(ans)

Submission status: Wrong Answer

Solution code:
def f_silver_fox_vs_monster():
    # 参考: https://atcoder.jp/contests/abc153/submissions/9773604
    from bisect import bisect_right
    from math import ceil
    N, D, A = [int(i) for i in input().split()]
    Monsters = sorted([[int(i) for i in input().split()] for j in range(N)])

    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """array[1] から array[index] までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """array[index] に value を加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    # リストは BIT に合わせて全部 1-indexed とする
    position = [0] + [row[0] for row in Monsters]
    hit_point = [0] + [row[1] for row in Monsters]
    # [k]: 左から k 番目の敵を爆発の左端で攻撃したときに届く右端の敵のインデックス
    pos_right = [0] + [bisect_right(position, pos + 2 * D) for pos in position]

    ans = 0
    bomb_damage = BIT(N + 1)  # bomb_damage.sum(k): 左から k 番目の敵に与えた累計ダメージ
    for i in range(1, N + 1):
        hp, damage, right = hit_point[i], bomb_damage.sum(i), pos_right[i]
        if hp - damage > 0:
            num_defeat = ceil((hp - damage) / A)  # 注目中の敵を倒すのに必要な爆発回数
            ans += num_defeat
            bomb_damage.add(i, num_defeat * A)
            # ここから右の敵はダメージが通っていないことを反映
            bomb_damage.add(right + 1, -num_defeat * A)
    return ans

print(f_silver_fox_vs_monster())

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort(key=lambda x: x[0])
idx = 0
idx_next = 0
ans = 0
while m[-1][-1] > 0:
    k = -(-m[idx][-1] // a)
    m[idx][-1] -= k * a
    dd = m[idx][0] + 2 * d
    ans += k
    idx_next = idx
    for i in range(idx + 1, n):
        if dd < m[i][0]:
            if idx_next == idx:
                idx_next = i
            break
        m[i][-1] -= k * a
        if idx_next == idx and m[i][-1] > 0:
            idx_next = i
    idx = idx_next
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort(key=lambda x: x[0])
idx = 0
idx_next = 0
ans = 0
while m[-1][-1] > 0:
    k = -(-m[idx][-1] // a)
    m[idx][-1] -= k * a
    dd = m[idx][0] + 2 * d
    ans += k
    idx_next = idx
    for i in range(idx + 1, n):
        if dd < m[i][0]:
            break
        m[i][-1] -= k * a
        if idx_next == idx and m[i][-1] > 0:
            idx_next = i
    idx = idx_next
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort(key=lambda x: x[0])
idx = 0
idx_next = 0
ans = 0
while m[-1][-1] > 0:
    k = -(-m[idx][-1] // a)
    dd = m[idx][0] + 2 * d
    idx_next = idx
    ans += k
    for i in range(idx, n):
        if dd < m[i][0]:
            break
        m[i][-1] -= k * a
        if m[i][-1] <= 0:
            idx_next = i
    idx = idx_next + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
# from numba import njit
i8 = np.int64

# @njit
def solve(X, H, D):
    xi = np.empty_like(X)
    hi = np.empty_like(H)
    p = 0
    N = X.shape[0]
    for i in range(1, N):
        if X[i] > X[i - 1]:
            xi[p] = X[i - 1]
            hi[p] = H[i - 1]
            p += 1
    xi[p] = X[N - 1]
    hi[p] = H[N - 1]
    p += 1
    area = 2 * D
    res = 0
    for i in range(p):
        if hi[i] > 0:
            res += hi[i]
            for j in range(i + 1, p):
                if xi[j] - xi[i] <= area:
                    hi[j] -= hi[i]
                else:
                    break
    return res

def main(X, H, D, A):
    arg = np.lexsort((X, H))
    X = X[arg]
    H = H[arg]
    H = (H - 1) // A + 1
    print(solve(X, H, D))

if __name__ == '__main__':
    stdin = np.fromstring(open(0).read(), i8, sep=' ')
    N, D, A = stdin[:3]
    XH = stdin[3:].reshape((-1, 2)).T
    ans = main(XH[0], XH[1], D, A)