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 collections import deque
N,D,A = map(int,input().split());INF = float("inf")
Z = []
for i in range(N):
  x,h = map(int,input().split())
  Z.append([x,h])
Z.sort()
ZZ = reversed(Z)
Z = deque(Z)
ZZ = deque(ZZ)
#print(Z)
ans = 0
pos = 0
right = - INF
while Z:
  target,life = Z.popleft()
  if right < target: #爆弾の右端よりもターゲットが右にいると爆風が当たらない。
    kaisu = (life+A-1)//A
    ans += kaisu
    bomb = kaisu*A
    right = target + 2*D
  else:
    if life <= bomb: #一つ前の爆弾で巻き込まれて死んだ
      #pos += 1
      continue
    else: #当たっているが倒しきれてない。
      life -= bomb
      kaisu = (life+A-1)//A
      ans += kaisu
      bomb = kaisu*A
      right = target + 2*D
temp = ans

ans = 0
pos = 0
left = INF
while ZZ:
  target,life = ZZ.popleft()
  if target < left: #爆弾の右端よりもターゲットが左にいると爆風が当たらない。
    kaisu = (life+A-1)//A
    ans += kaisu
    bomb = kaisu*A
    left = target - 2*D
  else:
    if life <= bomb: #一つ前の爆弾で巻き込まれて死んだ
      #pos += 1
      continue
    else: #当たっているが倒しきれてない。
      life -= bomb
      kaisu = (life+A-1)//A
      ans += kaisu
      bomb = kaisu*A
      left = target - 2*D

print(min(ans,temp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int,input().split());INF = float("inf")
Z = []
for i in range(N):
  x,h = map(int,input().split())
  Z.append([x,h])
Z.sort()
ZZ = reversed(Z)
Z = deque(Z)
ZZ = deque(ZZ)
#print(Z)
ans = 0
pos = 0
right = - INF
while Z:
  target,life = Z.popleft()
  if right < target: #爆弾の右端よりもターゲットが右にいると爆風が当たらない。
    kaisu = (life+A-1)//A
    ans += kaisu
    bomb = kaisu*A
    right = target + 2*D
  else:
    if life <= bomb: #一つ前の爆弾で巻き込まれて死んだ
      #pos += 1
      continue
    else: #当たっているが倒しきれてない。
      life -= bomb
      kaisu = (life+A-1)//A
      ans += kaisu
      bomb = kaisu*A
      right = target + 2*D
temp = ans

ans = 0
pos = 0
right = - INF
while ZZ:
  target,life = ZZ.popleft()
  if right < target: #爆弾の右端よりもターゲットが右にいると爆風が当たらない。
    kaisu = (life+A-1)//A
    ans += kaisu
    bomb = kaisu*A
    right = target + 2*D
  else:
    if life <= bomb: #一つ前の爆弾で巻き込まれて死んだ
      #pos += 1
      continue
    else: #当たっているが倒しきれてない。
      life -= bomb
      kaisu = (life+A-1)//A
      ans += kaisu
      bomb = kaisu*A
      right = target + 2*D

print(min(ans,temp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int,input().split());INF = float("inf")
Z = []
for i in range(N):
  x,h = map(int,input().split())
  Z.append([x,h])
Z.sort()
Z = deque(Z)
#print(Z)
ans = 0
pos = 0
right = - INF
while Z:
  target,life = Z.popleft()
  if right < target: #爆弾の右端よりもターゲットが右にいると爆風が当たらない。
    kaisu = (life+A-1)//A
    ans += kaisu
    bomb = kaisu*A
    right = target + 2*D
  else:
    if life <= bomb: #一つ前の爆弾で巻き込まれて死んだ
      #pos += 1
      continue
    else: #当たっているが倒しきれてない。
      life -= bomb
      kaisu = (life+A-1)//A
      ans += kaisu
      bomb = kaisu*A
      right = target + 2*D
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        if len(dam_list) != 0 and i == dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        if len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,D,A = map(int,input().split())
XH_ls = [[0,0] for _ in range(N)]
for i in range(N):
    x,h = map(int,input().split())
    XH_ls[i][0] = x
    XH_ls[i][1] = h

# X_lsが小さい順にソートする
XH_ls.sort(key = lambda x:x[0])
# XとHをそれぞれ1dlistに
X_ls = [0] * N
H_ls = [0] * N
for i in range(N):
    X_ls[i] = XH_ls[i][0]
    H_ls[i] = XH_ls[i][1]

left_edge = X_ls[0]
HP_max = H_ls[0]
total_Attack = 0
nex = 1
last_attack = -1
while nex < N:
    # 跨げないので、left_edgeからnex-1までを攻撃する
    if H_ls[nex] - left_edge > 2*D:
        total_Attack += -(-HP_max//A)
        left_edge = X_ls[nex]
        HP_max = H_ls[nex]
        last_attack = nex
        #print(nex,"attack",-(-HP_max//A),total_Attack)
        
    # 跨げるので右へ
    else:
        HP_max = max(HP_max,H_ls[nex])
        #print(nex,"skip")
        
    nex += 1

total_Attack += -(-HP_max//A)
#print(nex,"attack",-(-HP_max//A),total_Attack)

print(total_Attack)

Submission status: Wrong Answer

Solution code:
N,D,A = map(int,input().split())
X_ls = [0] * N
H_ls = [0] * N
for i in range(N):
    x,h = map(int,input().split())
    X_ls[i] = x
    H_ls[i] = h

X_ls.sort()
left_edge = X_ls[0]
HP_max = H_ls[0]
total_Attack = 0
nex = 1
last_attack = -1
while nex < N:
    # 跨げないので、left_edgeからnex-1までを攻撃する
    if H_ls[nex] - left_edge > 2*D:
        total_Attack += -(-HP_max//A)
        left_edge = X_ls[nex]
        HP_max = H_ls[nex]
        last_attack = nex
        #print(nex,"attack",-(-HP_max//A),total_Attack)
        
    # 跨げるので右へ
    else:
        HP_max = max(HP_max,H_ls[nex])
        #print(nex,"skip")
        
    nex += 1

total_Attack += -(-HP_max//A)
#print(nex,"attack",-(-HP_max//A),total_Attack)

print(total_Attack)

Submission status: Wrong Answer

Solution code:
"""
lazyseg使う方法とかもあるが、imos法使うのが簡単そう。
座標圧縮は必須。
"""
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()

coordinates = set()
for x,h in XH:
    coordinates.add(x)
    coordinates.add(x+2*D+1)

compress = {x:i for i,x in enumerate(sorted(coordinates))}

imos = [0]*(len(compress))
damage = 0
cur = 0
ans = 0
for x,h in XH:
    compX = compress[x]
    while cur < compX:
        damage += imos[cur]
        cur += 1
    rest = h-damage
    if rest > 0:
        add = A*ceil(rest/A)
        ans += int(ceil(rest/A))
        imos[cur] += add
        right = compress[x+2*D+1]
        imos[right] -= add
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH = [tuple(map(int,input().split())) for _ in range(N)]

XH = sorted(XH)

x0,x2 = 0,0
damage = 0
ans = 0
for i in range(N):
  x,h = XH[i]
  if i == 0:
    x0,x2 = x+D,x+2*D
    n = (h+A-1)//A
    damage = n*A
    ans += n
    continue
  if x <= x2:
    h -= damage
    if h<= 0:
      continue
  x0,x2 = x+D,x+2*D
  n = (h+A-1)//A
  damage = n*A
  ans += n
  
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

n,d,a=map(int,input().split())

lst=[]
lstx=[]
lsth=[]

for i in range(n):
  x,h=map(int,input().split())
  lst.append([x,h])

lst.sort(key=lambda x:x[0])
for x,h in lst:
  lstx.append(x)
  lsth.append(h)


ans=0

while lst:
  lst.pop(0)
  x=lstx.pop(0)
  h=lsth.pop(0)
  if h<=0:
    continue
  ans+=math.ceil(h/a)
  pin=bisect.bisect_left(lstx,x+2*d+1)
  lsth[:pin]=list(map(lambda x:x-ans*a,lsth[:pin]))


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    N, D, A = map(int, input().split())
    mlist = []
    for _ in range(N):
        x, h = map(int, input().split())
        mlist.append([x, (h+A-1)//A])
    mlist.sort(key=lambda x: x[0])
    db = deque()
    dnotb = deque()
    left = mlist[0][0]
    ans = 0
    for monster in mlist:
        if monster[0] <= left+2*D:
            db.append(monster)
        else:
            dnotb.append(monster)
    ans = 0
    while db or dnotb:
        if not db:
            monster = dnotb.popleft()
            monster[1] += ans
            db.append(monster)
        bmonster = db.popleft()
        ans = max(ans, bmonster[1])
        while dnotb:
            if dnotb[0][1] <= bmonster[0]+2*D:
                monster = dnotb.popleft()
                monster[1] += ans
                db.append(monster)
            else:
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    N, D, A = map(int, input().split())
    mlist = []
    for _ in range(N):
        x, h = map(int, input().split())
        mlist.append([x, (h+A-1)//A])
    mlist.sort(key=lambda x: x[0])
    db = deque()
    dnotb = deque()
    left = mlist[0][0]
    ans = 0
    for monster in mlist:
        if monster[0] <= left+2*D:
            db.append(monster)
        else:
            dnotb.append(monster)
    ans = 0
    while db or dnotb:
        if not db:
            monster = dnotb.popleft()
            monster[1] += ans
            db.append(monster)
        bmonster = db.popleft()
        while dnotb:
            if dnotb[0][1] <= bmonster[0]+2*D:
                monster = dnotb.popleft()
                monster[1] += ans
                db.append(monster)
            else:
                break
        ans = max(ans, bmonster[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
for i in range(N):
    l[i][1] = -((-l[i][1])//A)*A

cnt = 0
for i in range(N):
    if i < N-1:
        j = i+1
        while l[j][0]-l[i][0] <= 2*D:
            if l[j][1] >= l[i][1]:
                l[j][1] -= l[i][1]
            else:
                l[j][1] = 0
            j += 1
            if j >= N:
                break
    cnt += l[i][1]//A

print(cnt)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())


def is_ok(arg):
    return h[arg][0] <= h[i][0] + d*2

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n, d, a = MAP()
h = [LIST() for i in range(n)]
h = sorted(h, key=itemgetter(0))
attack = 0

ans = 0
for i in range(n):
    bomb = ceil( (h[i][1] - attack) / a )
    if bomb > 0:
        j = meguru_bisect(n, i)
        h[min(j, n-1)].append(-bomb)
        attack += bomb*a
        ans += bomb
    try:
        attack += h[i][2]*a
    except:
        pass

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = list(map(int, input().split()))
mons = dict()
monX = []
bomb = []
for i in range(N):
  temp = (list(map(int, input().split())))
  mons[temp[0]] = temp[1]
  monX.append(temp[0])

def quicksort(arr):
  if len(set(arr)) <= 2:
    return arr
  left = []
  center = arr.pop(0)
  right = []
  for i in arr:
    if i > center:
      right.append(i)
    else:
      left.append(i)
  left = quicksort(left)
  right = quicksort(right)
  left.append(center)
  left.extend(right)
  return left

monX = quicksort(monX)
res = 0
dmg = 0
for i in monX:
  hp = mons[i]
  temp = dict()
  pvot = 0
  for j, var in enumerate(bomb):
    if i > var[0]:
      dmg -= var[1]
      pvot = j + 1
    else:
      break
  if pvot != 0:
    bomb = bomb[pvot:]
  hp -= dmg
  if hp > 0:
    num = math.ceil(hp / A)
    res += num
    bomb.append([i + 2 * D, num * A])
    dmg += num * A
print(res)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = list(map(int, input().split()))
mons = dict()
monX = []
bomb = dict()
for i in range(N):
  temp = (list(map(int, input().split())))
  mons[temp[0]] = temp[1]
  monX.append(temp[0])

def quicksort(arr):
  if len(set(arr)) <= 2:
    return arr
  left = []
  center = arr.pop(0)
  right = []
  for i in arr:
    if i > center:
      right.append(i)
    else:
      left.append(i)
  left = quicksort(left)
  right = quicksort(right)
  left.append(center)
  left.extend(right)
  return left

monX = quicksort(monX)
res = 0
for i in monX:
  hp = mons[i]
  temp = dict()
  for j in bomb:
    if i <= j:
      hp -= bomb[j]
      temp[j] = bomb[j]
  bomb = temp
  if hp > 0:
    num = math.ceil(hp / A)
    res += num
    bomb[i + 2 * D] = num * A
print(res)

Submission status: Wrong Answer

Solution code:
import copy
N, D, A = list(map(int, input().split()))
mons = dict()
monX = []
bomb = dict()
for i in range(N):
  temp = (list(map(int, input().split())))
  mons[temp[0]] = temp[1]
  monX.append(temp[0])

def quicksort_2d(arr):
  temp = []
  for i in arr:
    temp.append(i[0])
  temp = quicksort(temp)
  res = []
  print(temp)
  for i in temp:
    res.append(arr[i])
  return res

def quicksort(arr):
  if len(set(arr)) <= 2:
    return arr
  left = []
  center = arr.pop(0)
  right = []
  for i in arr:
    if i > center:
      right.append(i)
    else:
      left.append(i)
  left = quicksort(left)
  right = quicksort(right)
  left.append(center)
  left.extend(right)
  return left

monX = quicksort(monX)
res = 0
for i in monX:
  hp = mons[i]
  temp = dict()
  for j in bomb:
    if i <= j:
      hp -= bomb[j]
      temp[j] = bomb[j]
  bomb = temp
  if hp > 0:
    num = int(hp / A) + int(hp % A)
    res += num
    bomb[i + 2 * D] = num * A
print(res)

Submission status: Wrong Answer

Solution code:
from bisect import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
ans=0
h=[0]*(n+1)
for i in range(n):
  j=bisect_left(mon,[mon[i][0]+2*d,INF])
  b=(mon[i][1]-h[i]+a-1)//a if mon[i][1]-h[i]>0 else 0
  h[i]+=b*a
  ans+=b
  if j<n:h[j]=-b*a
  h[i+1]+=h[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
i=0
ans=0
h=[0]*(n+1)
for i in range(n):
  j=bisect_left(mon,[mon[i][0]+2*d,INF])
  b=max(mon[i][1]-h[i]+a-1,0)//a
  h[i]+=b*a
  ans+=b
  if j<n:h[j]=-b*a
  h[i+1]+=h[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
i=0
ans=0
while i<n:
  j=bisect_left(mon,[mon[i][0]+2*d,INF])
  h=max(mon[i:j],key=lambda x:x[1])[1]
  if h!=mon[j-1][1] or i==j-1:
    ans+=(h+a-1)//a
    i=j
  else:
    h=max(mon[i:j-1],key=lambda x:x[1])[1]
    ans+=(h+a-1)//a
    mon[j-1][1]-=(h+a-1)//a*a
    if mon[j-1][1]>0:i=j-1
    else:i=j
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
i=0
ans=0
while i<n:
  j=bisect_left(mon,[mon[i][0]+2*d+1,INF])
  h=max(mon[i:j],key=lambda x:x[1])[1]
  if h!=mon[j-1][1] or i==j-1:
    ans+=(h+a-1)//a
    i=j
  else:
    h=max(mon[i:j-1],key=lambda x:x[1])[1]
    ans+=(h+a-1)//a
    mon[j-1][1]-=(h+a-1)//a*a
    if mon[j-1][1]>0:i=j-1
    else:i=j
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import*
INF=10**9+1
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
i=0
ans=0
while i<n:
  j=bisect_left(mon,[mon[i][0]+2*d+1,INF])
  b=max(mon[i:j],key=lambda x:x[1])[1]
  if b!=mon[j-1][1] or i==j-1:
    ans+=(b+a-1)//a
    i=j
  else:
    b=max(mon[i:j-1],key=lambda x:x[1])[1]
    ans+=(b+a-1)//a
    mon[j-1][1]-=b//a*a
    if mon[j-1][1]:i=j-1
    else:i=j
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math
N, D, A = map(int, input().split())
cusum = [0] * (N+1)
X = []
XH =[]
for i in range(N):
    xi, hi = map(int, input().split())
    X += [xi]
    XH += [(xi, hi)]
X = sorted(X)
XH = sorted(XH)
cusumD = 0
ans = 0
for i, (xi, hi) in enumerate(XH):
    cusumD -= cusum[i]
    hi -= cusumD
    r = bisect.bisect_right(X, xi+2*D)
    b = int(math.ceil(hi/A))
    d = b * A
    ans += b
    cusumD += d
    cusum[r] += d
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice, count
from operator import itemgetter

def resolve(in_):
    N, D, A = map(int, next(in_).split())
    XH = [tuple(map(int, line.split())) for line in islice(in_, N)]
    XH.sort(key=itemgetter(0))
    assert N == len(XH)

    left_index = 0
    left = XH[left_index]
    right_index = 0
    right = XH[right_index]
    right_index = 0
    next_index = 0

    damage = 0
    health = left[1] - damage

    D2 = D * 2

    ans = 0
    while left_index < N:
        left = XH[left_index]
        health = left[1] - damage
        while right_index < N and XH[right_index][0] <= left[0] + D2:
            right = XH[right_index]
            if right[1] > health:
                next_index = right_index
            right_index += 1
        bomb = -(-(left[1] - damage) // A)  # math.ceil((left[1] - damage) / A)
        ans += bomb
        damage = bomb * A
        if next_index == left_index:
            # 爆弾の範囲のモンスターは全滅しているが、その先に残っていないかどうか確認がいる
            next_index = right_index
            damage = 0
        left_index = next_index

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice, count
from operator import itemgetter

def resolve(in_):
    N, D, A = map(int, next(in_).split())
    XH = [tuple(map(int, line.split())) for line in islice(in_, N)]
    XH.sort(key=itemgetter(0))
    assert N == len(XH)

    left_index = 0
    left = XH[left_index]
    right_index = 0
    right = XH[right_index]
    right_index = 0
    next_index = 0

    damage = 0
    health = left[1] - damage

    D2 = D * 2

    ans = 0
    while left_index < N:
        left = XH[left_index]
        health = left[1] - damage
        while right_index < N and XH[right_index][0] <= left[0] + D2:
            right = XH[right_index]
            if right[1] > health:
                health = right[1]
                next_index = right_index
            right_index += 1
        bomb = -(-(left[1] - damage) // A)  # math.ceil((left[1] - damage) / A)
        ans += bomb
        damage = bomb * A
        if next_index == left_index:
            # 爆弾の範囲のモンスターは全滅しているが、その先に残っていないかどうか確認がいる
            next_index = right_index
            damage = 0
        left_index = next_index

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import islice, count
from operator import itemgetter

def resolve(in_):
    N, D, A = map(int, next(in_).split())
    XH = [tuple(map(int, line.split())) for line in islice(in_, N)]
    XH.sort(key=itemgetter(0))
    assert N == len(XH)

    left_index = 0
    left = XH[left_index]
    right_index = 0
    right = XH[right_index]
    right_index = 0
    next_index = 0

    damage = 0
    health = left[1] - damage

    D2 = D * 2

    ans = 0
    while left_index < N:
        left = XH[left_index]
        while right_index < N and XH[right_index][0] <= left[0] + D2:
            right = XH[right_index]
            if right[1] > health:
                health = right[1]
                next_index = right_index
            right_index += 1
        bomb = -(-(left[1] - damage) // A)  # math.ceil((left[1] - damage) / A)
        ans += bomb
        damage = bomb * A
        health -= damage
        if health <= 0:  # next_index == left_index:
            # 爆弾の範囲のモンスターは全滅しているが、その先に残っていないかどうか確認がいる
            next_index = right_index
            damage = 0
        left_index = next_index

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

heapq.heapify(xh)
cnt = 0
while xh:
    c = heapq.heappop(xh)
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    i = 0
    while xh and i < len(xh):
        nx = xh[i][0]
        if nx <= cx + 2*d:
            xh[i][1] -= cn * a
            i += 1
        else:
            break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

heapq.heapify(xh)
cnt = 0
while xh:
    c = heapq.heappop(xh)
    cx, ch = c[0], c[1]
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    while xh:
        ne = heapq.heappop(xh)
        nx, nh = ne[0], ne[1]
        if nx <= cx + 2*d:
            nh -= cn * a
            if nh > 0:
                tmp.append([nx, nh])
        else:
            tmp.append([nx, nh])
            for i in range(len(tmp)):
                heapq.heappush(xh, tmp[i])
            break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

# 爆発範囲がとても広く、全ての爆発が右端まで及ぶとひとまず考える
# 各xを見る際に、影響の及ばない爆発分のダメージは引く

# 合計の爆発回数
ans = 0
# 爆発ダメージの合計
total_damage = 0
# 各爆発の情報
dq = deque()

# 左端から順にモンスターを見る
for x, h in XH:
    # 爆発が及ばない場合
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    # 爆発させる必要がある場合
    if total_damage < h:
        # 残っているHPに更新
        h -= total_damage
        # 必要な爆発回数
        cnt = math.ceil(h // A)
        ans += cnt
        # 爆発回数 * 単発のダメージ
        dmg = cnt * A
        total_damage += dmg
        # [爆発で与えるダメージ、及ぶ範囲の右端]
        dq.append((dmg, x + D * 2))

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

heapq.heapify(xh)
cnt = 0
while xh:
    c = heapq.heappop(xh)
    cx, ch = c[0], c[1]
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += cn
    tmp = []
    while xh:
        ne = heapq.heappop(xh)
        nx, nh = ne[0], ne[1]
        if nx <= cx + 2*d:
            nh -= cn * a
            if nh > 0:
                tmp.append([nx, nh])
        else:
            tmp.append([nx, nh])
            for i in range(len(tmp)):
                heapq.heappush(xh, tmp[i])
            break
    
print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

heapq.heapify(xh)
cnt = 0
while xh:
    c = heapq.heappop(xh)
    cx, ch = c[0], c[1]
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += cn
    tmp = []
    while xh:
        ne = heapq.heappop(xh)
        nx, nh = ne[0], ne[1]
        if nx <= cx + 2*d:
            nh -= cn * a
            if nh > 0:
                tmp.append([nx, nh])
        else:
            for i in range(len(tmp)):
                heapq.heappush(xh, tmp[i])
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
num=[]
for i in range(n):
    num.append(list(map(int,input().split())))
num.sort(key=lambda x: x[0])
for i in range(n):
    num[i][1]=-(num[i][1]//-a)
cnt=0
cnt2=0
num2=num[0][0]+(d*2)
ans=0
for i in range(n):
    yn=0
    for j in range(cnt,n):
        if num2<num[j][0]:
            cnt2=j-1
            yn=1
            break
    if yn==0:
        cnt2=n-1
    else:
        yn=0
    num3=num[cnt][1]
    ans+=num3
    for j in range(cnt,cnt2+1):
        num[j][1]-=num3
        if num[j][1]>0:
            cnt=j
            yn=1
    if yn==0:
        if cnt2+1!=n:
            cnt=cnt2+1
        else:
            break
    num2=num[cnt][0]+(d*2)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
import math
n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key = lambda x:x[0])
cnt = 0
queue = deque()
sum_bomb = 0
for i in range(n):
    while len(queue) != 0 and queue[0][0]<l[i][0]:
        sum_bomb -= queue[0][1] * a
        queue.popleft()
    l[i][1] -= sum_bomb
    if l[i][1] <= 0 :
        continue
    num = math.ceil(l[i][1]//a)
    right = l[i][0] + 2 * d
    queue.append([right, num])
    cnt += num
    sum_bomb += num * a
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, D, A = map(int, input().split())
X = [0] * N
for i in range(N):
    x, h = map(int, input().split())
    X[i] = (x, h)
X = sorted(X)

ans = 0
P = [0] * N
for i in range(N):
    x, h = X[i]
    left = i
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if X[mid][0] <= x + 2 * D:
            left = mid
        else:
            right = mid
    P[i] = left

total = 0
last = -1
for i in range(N):
    x, h = X[i]
    if i <= last:
        h -= total
    else:
        total = 0
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        total += damage
        last = P[i]
print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
X = [0] * N
for i in range(N):
    x, h = map(int, input().split())
    X[i] = (x, h)
X = sorted(X)

ans = 0
left = 0
right = 1
P = []
while left < N:
    while right < N and X[right][0] - X[left][0] <= 2 * D:
        right += 1
    P.append(right - 1)
    left += 1
    right = left + 1

total = 0
last = -1
for i in range(N):
    x, h = X[i]
    if i <= last:
        h -= total
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        total = damage
        last = P[i]
print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = j
        break
    k = nextk

print(ans)