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: Runtime Error

Solution code:
import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
count = 0
min_x = 0
x = [xh[i][0] for i in range(n)]
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, 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: Runtime Error

Solution code:
import math
import numpy as np


num_monster, bomb_size, attack = map(int, input().split())

b = bomb_size * 2 + 1

monsters = {}
for _ in range(0, num_monster):
    pos, hp = map(int, input().split())
    monsters[pos] = math.ceil(hp / attack)

positions = sorted(monsters.keys())

damage = np.zeros([10**9 + 1])
bomb = 0

for pos in positions:
    rest = monsters[pos] - damage[pos]
    if rest > 0:
        bomb += rest
        damage[pos:pos+b] += rest

print(bomb)

Submission status: Runtime Error

Solution code:
import numpy as np
n,d,a=map(int,input().split())
flag=np.zeros(10**9+1)
XH=[list(map(int,input().split())) for _ in range(n)]
XH.sort(key=lambda A:A[0])
cnt=0
for i in range(n):
    kaisu=0
    x,h=XH[i]
    if flag[x]==0:
        kaisu=(h+a-1)//a
        flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
        cnt+=kaisu
    else:
        if flag[x]<h:
            h-=flag[x]
            kaisu=(h+a-1)//a
            flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
            cnt+=kaisu
print(cnt)

Submission status: Runtime Error

Solution code:
import math
import numpy as np


num_monster, bomb_size, attack = map(int, input().split())

b = bomb_size * 2 + 1

monsters = {}
for _ in range(0, num_monster):
    pos, hp = map(int, input().split())
    monsters[pos] = math.ceil(hp / attack)

positions = sorted(monsters.keys())

damage = np.zeros([10**9 + 1], dtype=np.int32)
bomb = 0

for pos in positions:
    rest = monsters[pos] - damage[pos]
    if rest > 0:
        bomb += rest
        damage[pos:pos+b] += rest

print(bomb)

Submission status: Runtime Error

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(T)
print(int(cnt))

Submission status: Runtime Error

Solution code:
import math

N, D, A = map(int, input().split())

L = list()

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

L.sort()
s = 0

for i,(x, h) in enumerate(L):
  num = math.ceil(h/A)
  s += num
  if i+1 != len(L) and num != 0:
    for j,(jx,jh) in enumerate(L[i+1:]):
      if jx > x+D+D:
        break
      L[i+j+1][1] = max(0,jh - num*A)
      if L[i+j+1][1] == 0:
        L.pop(i+j+1)
print(s)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 1
    bit = defaultdict(int)
    for i in range(n):
        x, h = xh[i]
        h -= bit[i]
        if h > 0:
            t = (h - 1) // a + 1
            for ldi in range(i, n):
                if x + 2 * d >= xh[ldi][0]:
                    bit[ldi] += t * a
                    continue
                break
            ans += y
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
n, d, a = map(int,input().split())
dic = {}
pixes = []

for i in range(n):
  x, y = map(int,input().split())
  pixes.append(x)
  dic[x] = y

pixes.sort()
ans = 0

while(pixes != []):
  a = pixes[0]
  b = pixes[len(pixes)-1]
  monstera = dic[a]
  monsterb = dic[b]
  
  if (b - a) <= 2 * d:
    if max(dic.values()) % a == 0:
      ans += max(dic.values()) // a
    else:
      ans += max(dic.values()) // a + 1
    pixes = []
  else:
    if monstera >= monsterb:
      if monstera % a == 0:
        attack = monstera
        ans += monstera // a
      else:
        attack = (monstera // a + 1) * a
        ans += monstera // a + 1
      for i in dic:
        if i <= 2 * d:
          if dic[i] <= attack:
            pixes.remove(i)
          else:
            dic[i] -= attack
    else:
      if monsterb % a == 0:
        attack = monsterb
        ans += monsterb // a
      else:
        attack = (monsterb // a + 1) * a
        ans += monstera // a + 1
      for i in dic:
        if n - i <= 2 * d:
          if dic[i] <= attack:
            pixes.remove(i)
          else:
            dic[i] -= attack

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, D, A = map(int, input().split())

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

last = max(Xlist)
mon = np.zeros(max(Xlist)+1)
for i in range(N):
    mon[Xlist[i]] = Hlist[i]

ans = 0
for n in range(N):
    idx = min(last, Xlist[n]+2*D) + 1
    if mon[Xlist[n]] < 0:
        mon[Xlist[n]] = 0

    if mon[Xlist[n]]%A==0:
        a = mon[Xlist[n]]//A
    else:
        a = mon[Xlist[n]]//A + 1
    mon[Xlist[n]:idx] -= a * A
    ans += a


print(int(ans))

Submission status: Runtime Error

Solution code:
import math
import numpy as np


num_monster, bomb_size, attack = map(int, input().split())

b = bomb_size * 2 + 1

monsters = {}
for _ in range(0, num_monster):
    pos, hp = map(int, input().split())
    monsters[pos] = math.ceil(hp / attack)

positions = sorted(monsters.keys())

damage = np.zeros(10**9 + 1, dtype=np.int32)
bomb = 0

for pos in positions:
    rest = monsters[pos] - damage[pos]
    if rest > 0:
        bomb += rest
        damage[pos:pos+b] += rest

print(bomb)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right


class SegTree:

    def __init__(self, a_list, x_list):
        assert max(a_list) <= 10 ** 7
        assert min(a_list) >= 0
        self.n = 1
        m = max(a_list)
        while self.n <= m:
            self.n *= 2
        self.dat_a = [0] * (self.n * 2)
        self.dat_b = [0] * (self.n * 2)
        for a, x in zip(a_list, x_list):
            self._add(a, a + 1, x, 0, 0, self.n)

    def _add(self, a, b, x, k, left, right):
        # add k for [a, b)
        if a <= left and right <= b:
            self.dat_a[k] += x
        elif left < b and a < right:
            self.dat_b[k] += (min(b, right) - max(a, left)) * x
            self._add(a, b, x, k * 2 + 1, left, (left + right) // 2)
            self._add(a, b, x, k * 2 + 2, (left + right) // 2, right)

    def _query_sum(self, a, b, k, left, right):
        if b <= left or right <= a:
            return 0
        elif a <= left and right <= b:
            return self.dat_a[k] + (right - left) * self.dat_b[k]
        else:
            res = (min(b, right) - max(a, left)) * self.dat_a[k]
            res += self._query_sum(a, b, k * 2 + 1, left, (left + right) // 2)
            res += self._query_sum(a, b, k * 2 + 2, (left + right) // 2, right)
            return res

    def add(self, a, b, x):
        return self._add(a, b, x, 0, 0, self.n)

    def query_sum(self, a, b):
        return self._query_sum(a, b, 0, 0, self.n)

    def return_value(self, a):
        return self.query_sum(a, a + 1)


def solve(n, d, a, xh_list):
    res = 0
    xh_list_s = sorted(xh_list, key=lambda x: x[0])
    x_list_s = [xh[0] for xh in xh_list_s]
    h_list_s = [xh[1] for xh in xh_list_s]

    sg = SegTree(list(range(n)), h_list_s)

    for i in range(n):
        v = sg.return_value(i)
        if v > 0:
            t = (v - 1) // a + 1
            res += t
            j = bisect_right(x_list_s, x_list_s[i] + 2 * d)
            sg.add(i, j, - t * a)
    return res


def main():
    n, d, a = map(int, input().split())
    xh_list = []
    for _ in range(n):
        x, h = map(int, input().split())
        xh_list.append(x, h)
    res = solve(n, d, a, xh_list)
    print(res)


def test():
    assert solve(3, 3, 2, [(1, 2), (5, 4), (9, 2)]) == 2
    assert solve(9, 4, 1, [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 2), (7, 3), (8, 4), (9, 5)]) == 5
    assert solve(3, 0, 1, [(300000000, 1000000000), (100000000, 1000000000), (200000000, 1000000000)]) == 3000000000


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

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
ma = XH[-1][0]
l = np.array([0]*(ma+5))
for xh in XH:
  l[xh[0]]=xh[1]
  

for xh in XH:
  x = xh[0]
  if x+2*D<=ma:
    a = l[x]
    if a<=0:
      continue
    else:
      b = math.ceil(a/A)
      ans += b
      l[x:x+2*D+1:]-=b*A
  else:
    a = l[x]
    if a<=0:
      continue
    else:
      b=math.ceil(a/A)
      ans += b
      l[x::]-=b*A
      
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

N, D, A = map(int, readline().split())
m = map(int,read().split())
XH = list(zip(m,m))
heapq.heapify(XH)
width = 2*D

ans = 0
while len(XH) != 0:
  xh_min = heapq.heappop(XH)
  # left + D の位置で攻撃する
  left = xh_min[0]
  right = left + width
  nAttack = (xh_min[1] + A - 1) // A
  damage = nAttack * A
    
  target = []
  while len(XH) != 0:
    xh = heapq.heappop(XH)
    if xh[0] <= right:
      if xh[1] > damage:
        target.append(xh)
    else:
      heapq.heappush(XH, xh)
      break
  if len(XH) == 0:
    maxH = max(xh_min[1], target[-1][1])
    nAttack = (maxH + A - 1) // A
    ans += nAttack
  else:
    ans += nAttack
    for t in target:
      heapq.heappush(XH, (t[0], t[1] - damage))
  
print(ans)

Submission status: Runtime Error

Solution code:
import math
input = sys.stdin.readline
N, D, A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
ans = 0
for i in range(N):
    if XH[i][1] > 0:
        p = XH[i][0]
        t = A*math.ceil(XH[i][1] / A)
        ans += math.ceil(XH[i][1] / A)
        for l in range(i, N):
            if XH[l][0] <= p + 2 * D:
                XH[l][1] -= t
            else:
                break
print(ans)

Submission status: Runtime Error

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 << 20) - 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: Runtime Error

Solution code:
from bisect import bisect_right


class SegTree:

    def __init__(self, a_list, x_list):
        assert max(a_list) <= 10 ** 7
        assert min(a_list) >= 0
        self.n = 1
        m = max(a_list)
        while self.n <= m:
            self.n *= 2
        self.dat_a = [0] * (self.n * 2)
        self.dat_b = [0] * (self.n * 2)
        for a, x in zip(a_list, x_list):
            self._add(a, a + 1, x, 0, 0, self.n)

    def _add(self, a, b, x, k, left, right):
        # add k for [a, b)
        if a <= left and right <= b:
            self.dat_a[k] += x
        elif left < b and a < right:
            self.dat_b[k] += (min(b, right) - max(a, left)) * x
            self._add(a, b, x, k * 2 + 1, left, (left + right) // 2)
            self._add(a, b, x, k * 2 + 2, (left + right) // 2, right)

    def _query_sum(self, a, b, k, left, right):
        if b <= left or right <= a:
            return 0
        elif a <= left and right <= b:
            return self.dat_a[k] + (right - left) * self.dat_b[k]
        else:
            res = (min(b, right) - max(a, left)) * self.dat_a[k]
            res += self._query_sum(a, b, k * 2 + 1, left, (left + right) // 2)
            res += self._query_sum(a, b, k * 2 + 2, (left + right) // 2, right)
            return res

    def add(self, a, b, x):
        return self._add(a, b, x, 0, 0, self.n)

    def query_sum(self, a, b):
        return self._query_sum(a, b, 0, 0, self.n)

    def return_value(self, a):
        return self.query_sum(a, a + 1)


def solve(n, d, a, xh_list):
    res = 0
    xh_list_s = sorted(xh_list, key=lambda x: x[0])
    x_list_s = [xh[0] for xh in xh_list_s]
    h_list_s = [xh[1] for xh in xh_list_s]

    sg = SegTree(list(range(n)), h_list_s)

    for i in range(n):
        v = sg.return_value(i)
        if v > 0:
            t = (v - 1) // a + 1
            res += t
            j = bisect_right(x_list_s, x_list_s[i] + 2 * d)
            sg.add(i, j, - t * a)
    return res


def main():
    n, d, a = map(int, input().split())
    xh_list = [map(int, input().split()) for _ in range(n)]
    res = solve(n, d, a, xh_list)
    print(res)


def test():
    assert solve(3, 3, 2, [(1, 2), (5, 4), (9, 2)]) == 2
    assert solve(9, 4, 1, [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 2), (7, 3), (8, 4), (9, 5)]) == 5
    assert solve(3, 0, 1, [(300000000, 1000000000), (100000000, 1000000000), (200000000, 1000000000)]) == 3000000000


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
import math
n,d,a=map(int,input().split())
XH=[]
for _ in range(n):
    x,h=map(int,input().split())
    h=math.ceil(h/a)
    XH.append([x,h])
XH.sort()
l=0
r=0
left=XH[0][0]
right=left+2*d
ans=XH[0][1]
c=XH[0][1]
L=[c]
while l<=n-1:
    left=XH[l][0]
    right=left+2*d
    if XH[r+1][0]<=right:
        cc=max(0,XH[r+1][1]-c)
        L.append(cc)
        c+=cc
        ans+=cc
        r+=1
        if r>=n-1:
            r-=1
            l+=1
    else:
        c-=L[l]
        l+=1
print(ans)

Submission status: Runtime Error

Solution code:
import math
import heapq
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 x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
            if len(hq) == 1:
                dx = x+2*D
                dd = t*A


print(ans)

Submission status: Runtime Error

Solution code:
N,D,A = list(map(int,input().split()))
data = []
for i in range(N):
    data.append(list(map(int,input().split())))
tmp = 0
i = 0
data.sort()
while data[-1][1] > 0:
    if data[i][1] > 0:
        tmpplus = (data[i][1] + A - 1) // A 
        tmp += tmpplus 
        for j in range(i,i+2*D):
            if data[j][1] > 0:
                data[j][1] -= tmpplus*A
        i = i+1
print(tmp)

Submission status: Runtime Error

Solution code:
import math
import heapq
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 x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
        if len(hq) == 1:
            dx = x+2*D
            dd = t*A


print(ans)

Submission status: Runtime Error

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])
  
  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[i] = 0
      max_flag = i
    else:
      tmp_lst[i] = enemy_lst[i]
  
  return count, tmp_lst, max_flag

def check(enemy_lst):
  return all(list(map(lambda x: x==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])

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: Runtime Error

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 << 18) - 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] - x[1])
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: Runtime Error

Solution code:
import math
import heapq
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 x: x[0])


hq = []
heapq.heapify(hq)  # リストhqのheap化
ans = 0
B = 0
dx = M[0][0]+2*D
dd = math.ceil(M[0][1]/A)*A
for i, (x, h) in enumerate(M):
    while x > dx:
        B -= dd
        if B == 0:
            break
        dx, dd = heapq.heappop(hq)
    if h > B:
        t = math.ceil((h-B)/A)
        ans += t
        B += t*A
        if i != 0:
            heapq.heappush(hq, (x+2*D, t*A))
        # if len(hq)==1:
        #     dx=x+2*D
        #     dd=t*A


print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, D, A = map(int, input().split())

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

last = max(Xlist)
mon = np.zeros(max(Xlist)+1)
for i in range(N):
    mon[Xlist[i]] = Hlist[i]

ans = 0
for n in range(N):
    idx = min(last, Xlist[n]+2*D) + 1
    if mon[Xlist[n]] < 0:
        mon[Xlist[n]] = 0

    if mon[Xlist[n]]%A==0:
        a = mon[Xlist[n]]//A
    else:
        a = mon[Xlist[n]]//A + 1
    mon[Xlist[n]:idx] -= a * A
    ans += a

print(int(ans))

Submission status: Runtime Error

Solution code:
import bisect

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

Submission status: Runtime Error

Solution code:
N, D, A= map(int, input().split())
XH = [0] * N
for i in range(N):
  XH[i] = list(map(int, input().split()))
XH = sorted(XH)  
#print(XH)
if XH[-1][0] > 10 ** 7:
  print("ERT")
bomb = [0] * (XH[-1][0] + D + 1)

for i in range(N):
  now = XH[i][0]
  x = max(0, now - D - 1)
  y = min(XH[-1][0], now + D)
  damage = sum(bomb[x: y]) * A
  #if i == 2:
    #print(damage, bomb, now - D - 1, now + D)
  if XH[i][1] > damage :
    ichi = XH[i][0] + D
    nokori = XH[i][1] - damage
    bomb_p = nokori // A
    if nokori % A != 0:
      bomb_p += 1
    bomb[ichi] += bomb_p
    
#print(bomb)    
print(sum(bomb))

Submission status: Runtime Error

Solution code:
from collections import deque
N,D,A = [int(i) for i in input().split()]
preXH = [[int(i) for i in input().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
Xs = [xxx[0] for xxx in XH]
ans = 0
DP = [0]*N#ダメイジの合計
for n,d in enumerate(DP):
    if d<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-d
        ans += bonu
        reach = XH[n][0] + 2*D
        for m in range(n,N):
            if XH[m][0] <= reach:
                DP[m] += bonu
            else:breakpoint
print(ans)

Submission status: Runtime Error

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
ma = XH[-1][0]
l = np.array([0]*(ma+5))
for xh in XH:
  l[xh[0]]=xh[1]
  

for xh in XH:
  x = xh[0]
  if x+2*D<=ma:
    a = l[x]
    if a<=0:
      continue
    else:
      b = math.ceil(a/A)
      ans += b
      l[x:x+2*D+1:]-=b*a
  else:
    a = l[x]
    if a<=0:
      continue
    else:
      b=math.ceil(a/A)
      ans += b
      l[x::]-=b*a
      
print(ans)

Submission status: Runtime Error

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
ma = XH[-1][0]
l = np.array([0]*(ma+5))
for xh in XH:
  l[xh[0]]=xh[1]
  

for xh in XH:
  x = xh[0]
  if x+D<=ma:
    a = l[x]
    if a<=0:
      continue
    else:
      b = math.ceil(a/A)
      ans += b
      l[x:x+2*D+1:]-=b*a
  else:
    a = l[x]
    if a<=0:
      continue
    else:
      b=math.ceil(a/A)
      ans += b
      l[x::]-=b*a
      
print(ans)

Submission status: Runtime Error

Solution code:
N, D, A= map(int, input().split())
XH = [0] * N
for i in range(N):
  XH[i] = list(map(int, input().split()))
XH = sorted(XH)  
#print(XH)
bomb = [0] * (XH[-1][0] + D + 1)

for i in range(N):
  now = XH[i][0]
  x = max(0, now - D - 1)
  y = min(XH[-1][0], now + D)
  damage = sum(bomb[x: y]) * A
  #if i == 2:
    #print(damage, bomb, now - D - 1, now + D)
  if XH[i][1] > damage :
    ichi = XH[i][0] + D
    nokori = XH[i][1] - damage
    bomb_p = nokori // A
    if nokori % A != 0:
      bomb_p += 1
    bomb[ichi] += bomb_p
    
#print(bomb)    
print(sum(bomb))

Submission status: Runtime Error

Solution code:
N, D, A= map(int, input().split())
XH = [0] * N
for i in range(N):
  XH[i] = list(map(int, input().split()))
XH = sorted(XH)  
#print(XH)
bomb = [0] * (XH[-1][0] + 1)

for i in range(N):
  now = XH[i][0]
  x = max(0, now - D - 1)
  y = min(XH[-1][0], now + D)
  damage = sum(bomb[x: y]) * A
  #if i == 2:
    #print(damage, bomb, now - D - 1, now + D)
  if XH[i][1] > damage :
    ichi = XH[i][0] + D
    nokori = XH[i][1] - damage
    bomb_p = nokori // A
    if nokori % A != 0:
      bomb_p += 1
    bomb[ichi] += bomb_p
    
#print(bomb)    
print(sum(bomb))

Submission status: Runtime Error

Solution code:
import collections

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()
# print(mons)
mons = collections.deque(mons)
count = 0
while mons[-1][0]-mons[0][0] > d:
    l = len(mons)
    if mons[0][1] > 0:
        left, att = mons[0]
        count += att
        for i in range(1, l):
            if mons[i][0]-left > d:
                break
            mons[i][1] -= att
    if mons[-1][1] > 0:
        right, att = mons[-1]
        count += att
        for i in range(l-1, 0,-1):
            if right - mons[i][0] > d:
                break
            mons[i][1] -= att
    mons.pop()
    mons.popleft()
rem = 0
for x,h in mons:
    rem = max(rem,h)
count += rem
print(count)

Submission status: Runtime Error

Solution code:

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
S = SegmentTree(N, 0, lambda x, y:x+y)
ans = 0
res = 0
from bisect import bisect
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect(X, x+D*2+1)
    cnt[j]+=n*A
    res+= n*A
    ans+=n
print(ans)

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
count = 0
min_x = 0
while sum([xh[i][1] for i in range(n)]):
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    check = min_x
    while xh[check][0] <= place + d:
        new_h = max(0, xh[check][1] - a * num)
        if new_h == 0:
            min_x += 1
        xh[check][1] = new_h
        check += 1
        if check == n:
            break
print(count)