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:
import math
n,d,a = map(int,input().split())

lst1 = [list(map(int,input().split())) for i in range(n)]

lst2 = []
ans = 0
lst1.sort()
rang = [-d,d]
left = 0
for i in range(n):
    for j in range(left,len(lst2)):
        if lst2[j][1] <lst1[i][0]:
            left += 1 
        elif lst2[j][0] <= lst1[i][0] <= lst2[j][1]:
            if lst1[i][0]-lst2[j][2] > 0:
                lst1[i][1]-=lst2[j][2]
            else:
                continue
    now = lst1[i][0]
    lst2.append([now,now+d*2,math.ceil(lst1[i][1]/a)*a])
    ans += math.ceil(lst1[i][1]/a)


print(ans)

Submission status: Wrong Answer

Solution code:
N, D,A = map(int, input().split())
P = sorted([ list(map(int,input().split(" "))) for i in range(N)])
cnt = 0
k = 0
d=[]
for i in range(N-1):
    d.append(P[i+1][0]-P[i][0])
for i in range(N):
    if P[i][1]>0:
        k = -(-P[i][1]//A)
        cnt += k 
        for j in range(0,N-i-1):
            if d[i + j]<= 2*D:
                 P[i+j+1][1] += -k*A
            else:
                break            
print(cnt)

Submission status: Wrong Answer

Solution code:
from math import *
n, d, a = map(int, input().split())
p = []
for _ in range(n):
  p.append(tuple(map(int, input().split())))

p = sorted(p)
c=0
for i in range(n):
  x, h = p[i]
  m = ceil(h/a)
  c+=m
  m = m*a
  for i in range(i+1, n):
    if x + d*2 < p[i][0]:
      break
    p[i] = (p[i][0], p[i][1] - m)
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
n,d,a=map(int,input().split())
x,h=zip(*sorted(tuple(map(int,input().split())) for _ in range(n)))
x=np.array(x)
h=np.array(h)
q=deque()
res=0
s=0
for i,xi in enumerate(x):
    while q:
        q0=q[0]
        if q0[0] < xi:
            s-=q0[1]
            q.popleft()
        else:
            break
    hi=h[i]-s
    ci=-(-hi//a)
    res+=ci
    q.append((xi+2*d,hi))
    s+=hi
    
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from bisect import bisect_left as bi_l

n, d, a, *xh = map(int, sys.stdin.read().split())
xh = [(x, ceil(h / a)) for x, h in sorted(zip(*[iter(xh)] * 2))]

def main():
    cnt = 0
    l = 0
    r = []
    s = []
    tmp = 0
    i = 0
    while l < n:
        x, h = xh[l]
        j = bi_l(r, x)
        if j > i:
            tmp -= s[i]
            i = j
        if h - tmp <= 0:
            l += 1
            continue
        cnt += h - tmp
        r.append(x + d * 2)
        s.append(h - tmp)
        tmp += h - tmp
        l += 1
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

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

# mod = 998244353
# mod = 1000000007

n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    

deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    
    stop = 1
    while stop == 1 and len(deq) > 0:
        if deq[-1][0] < monster_x[i]:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0
    
    monster_h[i] -= totaldamage
    if monster_h[i] > 0:
        index = monster_x[i] + 2*d
        deq.appendleft([index, monster_h[i]])
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f* a
        monster_h[i] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=heapq.heappop(xh)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  while True:
    if not xh:
      break
    y,z=heapq.heappop(xh)
    if y < t:
      if z>c:
        z-=c
        pool.append((y,z))
    else:
      pool.append((y,z))
      break
  for i in pool:
    heapq.heappush(xh,i)
print(ans)

Submission status: Wrong Answer

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

# mod = 998244353
# mod = 1000000007

n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    
print(monster_x)

deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    
    stop = 1
    while stop == 1 and len(deq) > 0:
        if deq[-1][0] < monster_x[i]:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0
    
    monster_h[i] -= totaldamage
    if monster_h[i] > 0:
        index = monster_x[i] + 2*d
        deq.appendleft([index, monster_h[i]])
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f* a
        monster_h[i] = 0

print(ans)

Submission status: Wrong Answer

Solution code:

N, D, A=(int(i) for i in input().split())
P=[[int(i) for i in input().split()] for  _ in range(N)]
P=sorted(P, key=lambda x:x[0])

ans=0

for i in range(N):
    if P[i][0]>0:
        if P[i][1]%A==0:
            bomb=P[i][1]//A
        else:
            bomb=P[i][1]//A+1
        ans+=bomb
        for j in range(i,N):
            if P[j][0]<=P[i][0]+2*D:
                P[j][1]-=A*bomb
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n, d, a = map(int, input().split())
xh = []
x_list = []
for i in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
    x_list.append(x)
xh.sort()
count = 0
min_x = 0
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    flag = True
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    for i in range(min_x, bisect.bisect(x_list, place + d)):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            if flag == True:
                min_x += 1
        else:
            flag = False
        xh[i][1] = new_h
print(count)

Submission status: Wrong Answer

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from fractions import gcd
e = enumerate

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

ans = 0
for i, xh in e(XH):
    x, h = xh[0], xh[1]
    if h%A==0:
        cnt = h//A
    else:
        cnt = h//A + 1
    ans += cnt
#    XH[i] = 0

    for j, xhi in e(XH[i+1:]):
        xi, hi = xhi[0], xhi[1]
        if xi <= 2*D + x:
            XH[i+1+j][1] -= (cnt*A)
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = [int(s) for s in input().split()]
d = D*2
mons = []
for i in range(N):
    X, H = [int(s) for s in input().split()]
    H = (H-1)//A + 1
    mons.append([X,H])
mons.sort()

left = 0
ans = mons[0][1]
s = mons[0][1]

right = 1
while right < N:
    x, h = mons[right]
    bar = x-d
    while mons[left][0] < bar:
        s -= mons[left][1]
        left += 1
    if h > s:
        att = h-s
        ans += att
        s += att
        mons[right][1] = att
    right += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_dict = [0]*N
hp_dict = dict()
for j in range(N):
    monster_place, monster_hp = map(int, input().split())
    place_dict[j] = monster_place
    hp_dict[j] = monster_hp
ans = 0

place_dict = sorted(place_dict)

# print(place_dict)
for i in range(N):
    place = place_dict[i]
    if hp_dict[i] <= 0:
        continue
    else:
        bomb = math.ceil(hp_dict[i] / A)
        # print(bomb)
        ans += bomb
        for k in range(i, N):
            if place_dict[k] > place + 2 * D:
                break

            if hp_dict[k] <= 0:
                continue
            else:
                hp_dict[k] -= bomb * A


print(ans)
# print(hp_dict)

Submission status: Wrong Answer

Solution code:
N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
j = 0
while True:
  if j+1>=N:
    break
  if XH[j+1][0]<=x+2*D:
    j+=1
  else:
    break
l[0]=j
for i in range(1,N):
  x = XH[i][0]
  j = l[i-1]
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  l[i]=j
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:l[a]+1:]-=b*A
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
N, D, A = map(int,input().split())
xx = []
hh = []
for i in range(N):
    x1, h1 = map(int,input().split())
    h2 = h1 // A
    if h1 % A != 0:
        h2 += 1
    xx.append(x1)
    hh.append(h2)

u = np.argsort(xx)
x = []
h = []
for i in u:
    x.append(xx[i])
    h.append(hh[i])
    
ans = 0
d = 0
r = -1
for i in range(N):
    if r < x[i]:
        d = h[i]
        ans += d
        r = x[i]+(2 * D)
    elif h[i] > d:
        d += h[i]
        ans += h[i]
    else:
        continue
    
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,d,a = map(int,input().split())

lst1 = [list(map(int,input().split())) for i in range(n)]

lst2 = []
ans = 0
lst1.sort()
rang = [-d,d]
left = 0
for i in range(n):
    for j,k,l in lst2[left:]:
        if k <lst1[i][0]:
            left += 1 
        elif j <= lst1[i][0] <= k:
            if lst1[i][0]-l > 0:
                lst1[i][1]-=l
            else:
                continue
    now = lst1[i][0]
    lst2.append([now,now+d*2,math.ceil(lst1[i][1]/a)*a])
    ans += math.ceil(lst1[i][1]/a)


print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = map(int, input().split())

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append((X, H))

    XHN.sort()

    ans = 0
    for i in range(N):
        X, H = XHN[i]
        attack_c = H // -A * -1
        ans += attack_c
        for j in range(i, N):
            if j <= i + D:
                XHN[j] = (X, H - A * attack_c)
            else:
                break

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
N, D, A = map(int,input().split())
xx = []
hh = []
for i in range(N):
    x1, h1 = map(int,input().split())
    h2 = h1 // A
    if h1 % A != 0:
        h2 += 1
    xx.append(x1)
    hh.append(h2)

u = np.argsort(xx)
x = []
h = []
for i in u:
    x.append(xx[i])
    h.append(hh[i])
    
ans = 0
d = 0
r = -1
for i in range(N):
    if r < x[i]:
        d = h[i]
        ans += d
        r = x[i]+(2 * D)
    elif h[i] > d:
        d += h[i]
        ans += h[i]
        r = x[i]+(2 * D)
    else:
        continue
    
print(ans)

Submission status: Wrong Answer

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

cnt = 0
for i in range(n):
    x,h = mons[i]
    h -= damages[i]
    if h<0:
        continue
    left_x = x
    left_idx = i
    right_x = x + 2*d
    tmp=0
    while(1):
        if right_idx+tmp == n or mons[right_idx+tmp][0]>right_x:
            right_idx += tmp
            break
        tmp+=1
    c = int(h//a + int(bool(h%a)))
    damage = a*c
    cnt += c
    d_list = [damage*(i>=left_idx)*(i<=right_idx) for i in range(n)]
    damages = list(map(lambda x,y:x+y,damages,d_list))
print(cnt)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monster = []
for _ in range(N):
    x, h = map(int, input().split())
    h = h // A
    if h % A != 0:
        h += 1
    monster.append((x, h))
# hは爆弾の回数
monster = sorted(monster, key=lambda x: [x[0], -x[1]])
rightest = monster[0][0] + D  # 最初のモンスターのdだけ右に奥
now_bakudan = monster[0][1]
ans = monster[0][1]
# 倒せないモンスターのDだけ右に爆弾を置く
for x, h in monster:
    if x > rightest+D:  # 爆弾が届いていないなら
        now_bakudan = 0
    if h > now_bakudan:
        ans += h-now_bakudan
        now_bakudan += h
        rightest = x+D

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=heapq.heappop(xh)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  while True:
    if not xh:
      break
    y,z=heapq.heappop(xh)
    if y < t:
      if z>c:
        z-=c
        pool.append((y,z))
    else:
      pool.append((y,z))
      break
  for i in pool:
    heapq.heappush(xh,i)
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = map(int, input().split())

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append((X, H))

    XHN.sort()

    ans = 0
    for i in range(N):
        X, H = XHN[i]
        attack_c = H // -A * -1
        ans += attack_c
        for j in range(i, N):
            if j <= i + D:
                XHN[j] = (X, H - A * attack_c)


    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
M = []
for i in range(N):
    x, h = map(int, input().split())
    M.append([x, h])
M.sort(key=lambda a: a[0])

ans = 0
target = 0
while True:
    cur = M[target][0] + D
    attack = -(-M[target][1] // A)
    ans += attack
    damage = attack * A
    for i in range(target+1, N):
        if cur - D < M[i][0] < cur + D:
            if M[i][1] > damage:
                target = i
                M[target][1] -= damage
                break
        else:
            target = i
            break
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import sys
input = sys.stdin.readline
N, D, A = [int(x) for x in input().split()]
XH = []
for _ in range(N):
    tmp = [int(x) for x in input().split()]
    XH.append(tmp)
XH.sort()
left_idx = 0
left = XH[0][0]
cnt = 0
while True:
    right = left + 2 * D
    if A >= XH[left_idx][1]:
        damage = A
        cnt += 1
    else:
        damage = (XH[left_idx][1] // A + XH[left_idx][1] % A) * A
        cnt += XH[left_idx][1] // A + XH[left_idx][1] % A
    maxH = XH[left_idx][1]
    flag = 1
    for i in range(left_idx, N):
        if XH[i][0] > right:
            break
        else:
            XH[i][1] -= damage
            if XH[i][1] > maxH:
                maxH = XH[i][1]
                left = XH[i][0]
                left_idx = i
                flag = 0
    if flag:
        for i in range(N):
            if XH[i][1] > 0:
                left_idx = i
                maxH = XH[i][1]
                left = XH[i][0]
                flag = 0
        if flag:
            print(cnt)
            break

Submission status: Wrong Answer

Solution code:
import bisect
N, D, A = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = sorted(L)
X = [0]*N
H = [0]*N
for i in range(N):
  X[i] = L[i][0]
  H[i] = L[i][1]
ind = L[0][0]+D
flag = [True]*N
cnt = 0
for i in range(N):
  b = bisect.bisect_right(X, ind+D)
  if flag[i]:
    if H[i]%2==0:
      c = H[i]//A
      flag[i] = False
      cnt += c
      for j in range(i+1,b):
        H[j] -= c*A
        if H[j] > 0:
          ind = X[j]+D
        else:
          flag[j] = False
          if j+1 < N:
            ind = X[j+1]+D
    else:
      c = H[i]//A
      cnt += c
      flag[i] = False
      for j in range(i+1,b):
        H[j] -= c*A
        if H[j] > 0:
          ind = X[j]+D
        else:
          flag[j] = False
          if j+1 < N:
            ind = X[j+1]+D
print(cnt)

Submission status: Wrong Answer

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

# mod = 998244353
# mod = 1000000007

n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    


deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    monster_h[i] -= totaldamage

    stop = 1
    while stop == 1 and len(deq) > 0:

        if deq[-1][0] == i:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0

    if monster_h[i] > 0:
        index = bisect.bisect_left(monster_x, monster_x[i]+2*d)
        deq.appendleft([index, monster_h[i]])
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f* a
        monster_h[i] = 0



print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monster = []
for _ in range(N):
    x, h = map(int, input().split())
    h = h // A
    if h % A != 0:
        h += 1
    monster.append((x, h))
# hは爆弾の回数
monster = sorted(monster, key=lambda x: [x[0], -x[1]])
rightest = monster[0][0] + D  # 最初のモンスターのdだけ右に奥
now_bakudan = monster[0][1]
ans = monster[0][1]
# 倒せないモンスターのDだけ右に爆弾を置く
for x, h in monster:
    if x > rightest+D:  # 爆弾が届いていないなら
        now_bakudanw = 0
    if h > now_bakudan:
        ans += h-now_bakudan
        now_bakudan += h
        rightest = x+D

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N, D, A = map(int, input().split())
XHlist = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
utan = -1
satan = 10**9
help = 0
ans = 0
for i in range(N):
    X, H = XHlist[i]
    soko = ceil(H / A)
    if X <= utan:
        soko = max(0, soko - help)
    if soko > 0:
        ans += soko
        utan = X + 2 * D
        help = soko
    # print(i, soko, utan, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

tg = sorted(tg, key=lambda x:x[0])
bit = BIT(n+2)
result = 0
ind = 0
for i in range(n):
    c = tg[i][1] - bit.sum(i+1)
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    if ind < c:
        ind = c
    for j in range(ind, n):
        if tg[j][0] <= wd:
            ind = j
        else:
            break
    bit.add(d+1, c)
    bit.add(ind+2, -c)
print(result)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)

  def sum(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  ans += remain[i]-bit.sum(i+1)
  bit.add(i+1,remain[i]-bit.sum(i+1))
  bit.add(br+1,-remain[i]+bit.sum(i+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect

N,D,A=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
List.sort()
arr = []
Harr = [0] * (N+1)

for i in range(N):
  X = List[i][0]
  H = List[i][1]
  H = math.ceil(H / A)
  arr .append(X)
  Harr[i] = H
  
cnt = 0
for i in range(len(arr)):
  while Harr[i] > 0:
    a = bisect.bisect_right(arr, int(arr[i])+2*D)
    for j in range((a-i)):
      Harr[i+j] -= int(Harr[i])
    cnt += int(Harr[i])
print(int(cnt))

Submission status: Wrong Answer

Solution code:
import math
n,d,a = map(int,input().split())
d *= 2
e = []
for i in range(n):
  x,h = map(int,input().split())
  e.append([x,math.ceil(h/a)])
e.sort()
ans = 0
for i in range(n):
  at = e[i][1]
  if at > 0:
    ans += at
    hani = e[i][0] + 2
    for j in range(i,n):
      if e[j][0] <= hani:
        e[j][1] -= at
      else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

b=0
now=0
stronger=now
end_i=0

while True:
    now_h=xh[now][1]
    stronger=now
    included=0

    use_bomb=now_h//a+1
    if now_h%a==0:
        use_bomb-=1
    b+=use_bomb

    for i in range(now+1,n):
        end_i+=1
        if xh[i][0]>xh[now][0]+2*d:
            break
        else:
            included+=1
            if now_h<xh[i][1]:
                stronger=i
            xh[i][1]-=use_bomb*a

    if stronger==now:
        now+=included+1
    else:
        now=stronger
    if now>=n:
        break
print(b)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
cum = [0]*N
dam = 0
for i in range(N):
    dam += cum[i]
    H[i] -= dam
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_left(X,x+2*D)
    if i+1 < N:
        cum[i+1] += damage 
    if ind+1 < N:
        cum[ind+1] -=damage 

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect
N,D,A = map(int,input().split())
X = np.zeros(N,dtype=int)
H = np.zeros(N,dtype=int)
for i in range(N):
    X[i],H[i] = map(int,input().split())
idx = np.argsort(X)
X = X[idx]
H = H[idx]
numl = H // A
numl[H % A != 0] += 1

now = 0
count = 0

while(1):
    while(H[now] <= 0):
        now += 1
        if(now >= N):
            print(count)
            exit()
    
    tx = X[now] + D
    num = numl[now]
    idxl = bisect.bisect_left(X,tx-D)
    idxr = bisect.bisect_right(X,tx+D)
    H[idxl:idxr] -= num * A
    count += num

Submission status: Wrong Answer

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

class BIT:
    def __init__(self, n=None):
        # 1-index
        if n is None:
            n = (1 << 24) - 1
        self.n = n
        self.dat_a = [0] * (2 * self.n - 1)
        self.dat_b = [0] * (2 * self.n - 1)

    def add(self, a, b, x, k=0, l=0, r=None):
        # Add x to [a, b)
        if r is None:
            r = self.n

        if a <= l and r <= b:
            self.dat_a[k] += x
        elif l < b and a < r:
            self.dat_b[k] += (min(b, r) - max(a, l)) * x
            self.add(a, b, x, k * 2 + 1, l, (l + r) // 2)
            self.add(a, b, x, k * 2 + 2, (l + r) // 2, r)
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun sum of [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            return self.dat_a[k] * (r - l) + self.dat_b[k]
        
        res = (min(b, r) - max(a, l)) * self.dat_a[k]
        res += self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        res += self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return res


ans = 0
bit = BIT()
X.sort(key=lambda x:x[0])
for x, h in X:
    res = h - bit.query(x, x + 1)
    if res <= 0:
        continue
        
    cnt = -(-res // A)
    bit.add(x, x + 2 * D + 1, cnt * A)
    ans += cnt
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a  = map(int,input().split())
x_b = []
x_b2 = []
x = [0]*n
h_b = []
h = [0]*n
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x_b.append({'key':i, 'val':x_temp})
    x_b2.append(x_temp)
    h_b.append(h_temp)

x_b.sort(key = lambda x_b : x_b['val'])

print(x_b)

for i in range(n):
    ind = x_b[i]['key']
    x[i] = x_b2[ind]
    h[i] = h_b[ind]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]):
            h[i] -= at_num * a
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

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

#とりあえず左から順番に範囲ギリギリで頃していく。どうせTLE
mochikoshis = deque()
ans = 0
for i in range(N):
    popleftcnt = 0
    for mochikoshi in mochikoshis:
        if enemies[i][0] <= mochikoshi[0]:
            enemies[i][1] -= mochikoshi[1]
        else:
            popleftcnt += 1

    kari = enemies[i][1]
    for i in range(popleftcnt):
        mochikoshis.popleft()
    if 1 <= kari:
        tmp = math.ceil(enemies[i][1]/A)
        ans += tmp
        mochikoshis.append((enemies[i][0]+2*D,tmp*A))

print(ans)

Submission status: Wrong Answer

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

# mod = 998244353
# mod = 1000000007

n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    


deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    monster_h[i] -= totaldamage


    stop = 1
    while stop == 0 and len(deq) > 0:

        if deq[-1][0] == i:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0

    if monster_h[i] > 0:
        index = bisect.bisect_left(monster_x, monster_x[i]+2*d)
        deq.appendleft([index, monster_h[i]])
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f* a
        monster_h[i] = 0



print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from bisect import bisect_left as bi_l

n, d, a, *xh = map(int, sys.stdin.read().split())
xh = [(x, ceil(h / a)) for x, h in sorted(zip(*[iter(xh)] * 2))]

def main():
    cnt = 0
    l = 0
    r = []
    s = [0]
    tmp = 0
    i = 0
    while l < n:
        x, h = xh[l]
        j = bi_l(r, x)
        if j > i:
            tmp -= s[j]
            i = j
        if h - tmp <= 0:
            l += 1
            continue
        cnt += h - tmp
        r.append(x + d * 2)
        s.append(h - tmp)
        tmp = h
        l += 1
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
X.sort()
cnt = 0
if X[0][1] % A == 0:
  cnt = X[0][1] // A
else:
  cnt = X[0][1] // A + 1
F = X[0][0] + D
j = 0
for i in range(N):
  if X[i][0] > F + D:
    j = i
    if X[i][1] % A == 0:
      cnt += X[i][1] // A
    else:
      cnt += X[i][1] // A + 1
    F = X[i][0] + D
print(cnt)

Submission status: Wrong Answer

Solution code:
def bomb(enemy_lst, pos, num, dist, attack):
  included_enemy = list(map(lambda x: pos-dist <= x[0] <= pos+dist,
                            enemy_lst))
  tmp_lst = []
  for i in range(num):
    if included_enemy[i]:
      tmp_lst.append(enemy_lst[i])
    else:
      tmp_lst.append([enemy_lst[i][0], 0])
  
  count = int(max(list(map(lambda x:x[1] / attack, 
                           tmp_lst))))
  tmp_lst = []
  max_flag = 0
  for i in range(num):
    if included_enemy[i]:
      tmp_lst.append([enemy_lst[i][0], 0])
      max_flag = i
    else:
      tmp_lst.append(enemy_lst[i])
  tmp_lst.append([tmp_lst[num-1][0]+D, 0])
  
  return count, tmp_lst, max_flag

def check(enemy_lst):
  return all(list(map(lambda x: x[1]==0, enemy_lst)))

data = list(map(int, input().split()))
N = data[0]
D = data[1]
A = data[2]

lst = []
for i in range(N):
  lst.append(list(map(int, input().split())))
lst = sorted(lst, key=lambda x:x[0])
lst.append([lst[N-1][0]+D, 0])

pos = lst[0][0] + D
count = 0
while True:
  tmp_count, lst, flag = bomb(lst, pos, N, D, A)
  count += count
  
  if check(lst):
    break
  else:
    pos = lst[flag+1][0] + D

print(count)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
M = []
for i in range(N):
    x, h = map(int, input().split())
    M.append([x, h])
M.sort(key=lambda a: a[0])

ans = 0
target = 0
while True:
    cur = M[target][0] + D
    # attack = ceil(M[target][1]/A)
    attack = -(-M[target][1] // A)
    ans += attack
    damage = attack * A
    for i in range(target+1, N):
        if cur - D <= M[i][0] <= cur + D:
            if M[i][1] > damage:
                target = i
                M[target][1] -= damage
                break
        else:
            target = i
            break
    else:
        break

print(ans)