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 numpy as np
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: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right
import numpy as np

n, d, a = map(int, input().split())
xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()
xh = np.array(xh)
xh = xh.T
x = xh[0][:]
h = xh[1][:]
l = 0
ret = 0
while l < n:
    xl = x[l]
    hl = h[l]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(x, xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    h[l:r] -= k * a
print(ret)

Submission status: Runtime Error

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+=(b+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: Runtime Error

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
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 = right
    right = left + 1

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

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
      sd[j]=e[i][1]+s-mx
      mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Runtime Error

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
    sd[j]=e[i][1]+s-mx
    mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Runtime Error

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=inp[1]//a
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
    sd[j]=e[i][1]+s-mx
    mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Runtime Error

Solution code:
from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())

Submission status: Runtime Error

Solution code:
import copy
import numpy as np
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)]
xh = sorted(xh, key=lambda x:(x[0]))
if d == 0:
    di = 0
else:
    di = 1 + 2*d
cnt = 0
while xh:
    c = xh.pop(0)
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    if ch % a == 0:
        cn = ch // a
    else:
        cn = 1 + ch // a
    cnt += copy.deepcopy(cn)
    for nx in range(cx+1, cx+di+1):
        for i in range(len(xh)):
            if xh[i][0] == nx:
                xh[i][1] -= a * cn
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] += x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


def main():

    N, D, A = in_nn()
    XH = sorted(in_nl2(N))
    X = [0] * N
    H = [0] * N

    for i in range(N):
        x, h = XH[i]
        X[i] = x
        H[i] = h

    seg = SegTree([0] * N, segfunc=lambda a, b: a + b, ide_ele=0)

    ans = 0
    for i in range(N):

        x, h = X[i], H[i]
        j = bisect.bisect_right(X, x + 2 * D)
        cnt_bomb = seg.query(0, i + 1)

        h -= A * cnt_bomb
        if h <= 0:
            continue

        cnt = -(-h // A)
        ans += cnt
        seg.update(i, cnt)
        seg.update(j, -cnt)

        # print(i, j)
        # print(seg.seg)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import *

N, D, A = map(int, input().split())
X = [0]
H = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append(X[-1] + x)
    H.append(h)

Imos = [0]*N
cnt = 0
damage = 0
res = 0
for i in range(N):
    h = H[i] - damage
    x = X[i+1]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = bisect_left(X, x+2*D) - 1
        Imos[p] += cnt
        damage = damage - Imos[i]*A + cnt * A
        res += cnt
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
from math import ceil

# n个怪物，d杀伤半径，a杀伤值
n, d, a = map(int,input().split())

ms = sorted([(pos, ceil(hp / a)) for pos, hp in [map(int, input().split()) for i in range(n)])
 
bombs = deque()
 
ans = 0
valid_bomb = 0
for pos, hp in ms:
  # 查看队列里的bomb是否对当前怪物有效
  while que and que[0][0] < pos:
    bomb_border, bomb_cnt = bombs.popleft()
    valid_bomb -= bomb_cnt
  
  # 还需新加多少bomb才能灭掉当前怪物
  bomb_cnt = max(0, hp - valid_bomb)
  valid_bomb += bomb_cnt
  ans += bomb_cnt
  
  # 新加的bomb放入队列
  if bomb_cnt > 0:
    que.append([pos + d * 2, bomb_cnt])
 
print(ans)

Submission status: Runtime Error

Solution code:

def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    
    # imos
    x_max = AB[-1][0] + (2*D+5)
    imos = [0] * x_max
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l-1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l+1)
            while R < N and AB[R][0] - x <= 2*D:
                R += 1
            d = h - imos[l]
            cnt = d//A
            imos[l] += cnt*A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def binary(N, LIST, num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(map(int, input().split()) for _ in range(n))
x = [i for i, j in xh]
h = [(j + a - 1) // a for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bnum = max(h[i] - (bsum[i - 1] + bomb[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bsum[i - 1] + bomb[i]
    ans += bnum
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import bisect


sys.setrecursionlimit(10 ** 6)


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n,d,a=map(int,input().split())
xh=[map(int,input().split()) for _ in range(n)]
xh.sort()
D=2*D
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-h%a)//a
    damage=a*nim
    ans+=num
    total+=damage
    q.append([x+D,damage])
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict


def main():
    input = stdin.buffer.readline
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = {}
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (x_max + 2 + 2 * d)
    for i in range(1, x_max + 1):
        if i in dp:
            summary[i] += dp[i]
            summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if i in dp and dp[i] > 0:
            count = 0
            if summary[i] % a == 0:
                count = summary[i] // a
            else:
                count = (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = [0] * (x_max + 2 + 2 * d)
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (x_max + 2 + 2 * d)
    for i in range(1, x_max + 1):
        summary[i] += dp[i]
        summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if dp[i] > 0:
            count = 0
            if summary[i] % a == 0:
                count = summary[i] // a
            else:
                count = (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 9
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = [0] * (MAX + 1 + 2 * d)
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (MAX + 1 + 2 * d)
    for i in range(1, min(x_max + 1, MAX + 1)):
        summary[i] += dp[i]
        summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if dp[i] > 0:
            count = 0
            if summary[i] % a == 0:
                count = summary[i] // a
            else:
                count = (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 9
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = [0] * (MAX + 1 + 2 * d)
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (MAX + 1 + 2 * d)
    for i in range(1, min(x_max + 1, MAX + 1)):
        summary[i] += dp[i]
        summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if dp[i] > 0:
            count = summary[i] // a if summary[i] % a == 0 else (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    MAX = 10 ** 9
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = [0] * (MAX + 1 + 2 * d)
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (MAX + 1 + 2 * d)
    for i in range(1, min(x_max + 1, MAX + 1)):
        summary[i] += dp[i]
        summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if dp[i] > 0:
            count = summary[i] // a if summary[i] % a == 0 else (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
from itertools import accumulate


def main():
    input = stdin.buffer.readline
    MAX = 2 * 10 ** 5
    n, d, a = map(int, input().split())
    x_arr = []
    h_arr = []
    for _ in range(n):
        xi, hi = map(int, input().split())
        x_arr.append(xi)
        h_arr.append(hi)
    x_max = max(x_arr)

    dp = [0] * (MAX + 1 + 2 * d)
    for x, h in zip(x_arr, h_arr):
        dp[x] = h

    ans = 0
    summary = [0] * (MAX + 1 + 2 * d)
    for i in range(1, min(x_max + 1, MAX + 1)):
        summary[i] += dp[i]
        summary[i + 1] -= dp[i]
        summary[i] += summary[i - 1]
        if dp[i] > 0:
            count = summary[i] // a if summary[i] % a == 0 else (summary[i] + 1) // a
            ans += count
            summary[i] -= count * a
            summary[i + 2 * d + 1] += count * a

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from operator import itemgetter
import math

readline= sys.stdin.readline
n,d,a=map(int,input().split())
xh=[list(map(int,readline().split())) for _ in range(n)]
xh.sort()
xh=np.array(xh)
x=xh[:,0]
h=xh[:,1]
start=0
i=0
while(1):
    if (start==n-1) and (h[start]==0):
        break
    if h[start]<=0:
        start+=1
        continue
    #binary search
    times=math.ceil(h[start]/a)
    left=start
    right=n-1
    mark=x[start]+2*d
    while(1):
        if right-left<=1:
            break
        mid=(left+right)//2
        if x[mid]>=mark:
            right=mid
        else:
            left=mid
    if x[right]<=mark:
        end=right
    else:
        end=left
    h[start:end+1]-=a*times
    i+=times
print(i)

Submission status: Runtime Error

Solution code:
import math
from bisect import bisect_left

n, d, a = map(int, input().split())
x_list = []
max_x = 0
for _ in range(n):
    x, h = map(int, input().split())
    x -= 1
    x_list.append([x, h])
    max_x = max(max_x, x)
x_list.sort()
xx = [x[0] for x in x_list]
ans = 0
for index_left, [x, h] in enumerate(c):
    if h > 0:
        ans += math.ceil(h / a)
        index_right = bisect_left(xx, x + (d * 2))
        for i in range(index_left, min(index_right + 1, n)):
            x_list[i][1] -= math.ceil(h / a) * a
print(ans)

Submission status: Runtime Error

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,d,a=map(int,input().split())
m=[]
for i in range(n):
  m.append([])
  a,b=map(int,input().split())
  m[-1].append(a)
  m[-1].append(b)
import math
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,d,a=map(int,input().split())
m=[]
for i in range(n):
  m.append([])
  x,h=map(int,input().split())
  c=math.ceil(h/a)
  while a*c<h:
    c+=1
  m[-1].append(x)
  m[-1].append(c)
m=sorted(m, key=lambda student: student[0])
leftcursor=0
rightcursor=0

t=0
ans=0
while leftcursor<n:
  l=m[leftcursor][0]
  r=l+2*d
  t=m[leftcursor][1]
  ans+=t
  if rightcursor<n:
    while m[rightcursor][0]<=r:
      rightcursor+=1
      if rightcursor>=n:
        break
  for i in range(leftcursor,rightcursor):
    m[i][1]-=t
  while m[leftcursor][1]<=0:
    leftcursor+=1
    if leftcursor>=n:
      break
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main() {
long long ans = 0;
long long N,D,A;
cin >> N >> D >> A;
vector<vector<long long>> enemies(N, vector<long long> (2));
for (int i = 0; i < N; i++)
{
    cin >> enemies.at(i).at(0) >> enemies.at(i).at(1);
}
sort(enemies.begin(),enemies.end(),[](const vector<long long> &alpha,const vector<long long> &beta){return alpha[0] < beta[0];});

queue<vector<long long>> damage;
long long dmg = 0;
for (int i = 0; i < N; i++){
    long long x = enemies.at(i).at(0);
    long long h = enemies.at(i).at(1);
    if (damage.empty()){
        long long bomb = (h+A-1)/A;
        ans += bomb;
        dmg += bomb*A;
        damage.push({x+2*D,bomb});
    }
    else{
        while (!damage.empty()){
            vector<long long> vec;
            vec = damage.front();
            long long d = vec.at(0);
            long long bomb = vec.at(1);
            if (d < x){
                dmg -= bomb*A;
                damage.pop();
            }
            else{
                break;
            }
        }
        if (h > dmg){
            long long bomb = (h-dmg+A-1)/A;
            dmg += bomb*A;
            damage.push({x+2*D,bomb});
            ans += bomb;
        }
        
    }
}

cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
from math import ceil
from collections import deque

n, d, a = map(int, input().split())
m = sorted([list(map(int, input().split())) for _ in range(n)])
m = [[x, ceil(h / A)] for x, h in m]

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * d, need])

print(ans)

Submission status: Runtime Error

Solution code:
import math
def main():
    N,D,A = map(int, input().split())
    X,H = [0]*N,[0]*N
    for i in range(N):
        x,H[i] = map(int, input().split())
        X[i] =  x-1
    # 座標X[i]のモンスターはceil(H[i]/A)回攻撃すれば倒せる
    # N=4, D=2
    # 0 1 2 3 4 5 6 7 8 9 10
    # 0 5 0 2 0 0 3 3 0 0 4 (倒すのに必要な回数; 全部0にすれば終了)
    # 0 0 0 0 0 0 3 3 0 0 4 (座標1~3のどこかで5回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 0 (座標8で4回爆破したあと)
    # ->よって5+4=9回が最小回数..?
    health = [0]*(max(X)+1)
    for i in range(N):
        health[X[i]] = math.ceil(H[i]/A)
    ans = 0
    for left in X:
        if health[left]>0:
            # left+Dで爆破を行う
            ans += health[left]
            health[left:left+2*D+1] = [max(0,p-health[left]) for p in health[left:left+2*D+1]]
    print(ans)

main()

Submission status: Runtime Error

Solution code:
from collections import deque
N, D, A = list(map(int, input().split()))
D *= 2
pair_xh = [[-1, -1] for _ in range(N)]
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))

q_lim_d = deque() # 累積和に含まれる攻撃範囲とダメージを保存する場所
total = 0 # 喰らいダメージの累積和
count = 0 # 攻撃回数
for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    while len(q_lim_d) and q_lim_d[0][0] < x: # 範囲外になったら喰らわないから累積和から外す
        total -= q[0][1]
        q_lim_d.pop()
    h -= total
    
    if h > 0: # 見てる敵の体力が0になる攻撃回数を求めその分を累積和に足す
        times = int((h + A - 1) / A) # 0にするのに必要な回数(切り上げ)
        count += times
        damage = A * times
        total += damage
        q_lim_d.append([x+D, damage])
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(key = lambda x:x[0])

cnt = 0
while len(xh) != 0:
    x, h = xh.pop(0)
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(len(xh)):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt
    while xh[0][1] < 1:
        xh.pop(0)
        if len(xh) == 0:
            break

print(cnt)

Submission status: Runtime Error

Solution code:
n_,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n_)]
"""
n_=2*1000
d=0 #pow(10,9)
a=1
xh=[[pow(10,9)//i,pow(10,9)] for i in range(1,1+n_)]
"""
xh.sort(key=lambda x:x[0])

#A1 ... AnのBIT(1-indexed)
n=xh[-1][0]
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    if idx==0:
      return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
  if idx==0:
    print('index 0!')
    return 
  while idx <= n:
      BIT[idx] += x
      idx += idx&(-idx)
  return

ans=0
for x,h in xh:
  fd=BIT_query(min(x+2*d,xh[-1][0]))-BIT_query(max(0,x-1))
  if h-fd<=0:
    pass
  else:
    c=(h-fd)//a
    BIT_update(min(x+2*d,xh[-1][0]),c*a)
    ans+=c
  pre_x=x
print(ans)

Submission status: Runtime Error

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
"""
n=2*100000
d=0
a=1
xh=[[pow(10,9)//i,pow(10,9)] for i in range(1,1+n)]
"""
xh.sort(key=lambda x:x[0])
import numpy as np
fd=np.zeros(2*d+1,np.int64) # fd[i]:ターゲットのモンスターから座標+i離れたところにいるモンスターに与えたダメージ
ans=0
pre_x=xh[0][0]
for x,h in xh:
  fdt=np.zeros(2*d+1,np.int64)
  if 0<x-pre_x and x-pre_x<2*d+1:
    fdt[:-x+pre_x]=fd[x-pre_x:]
  fd=fdt
  if h-fd[0]<=0:
    pass
  else:
    c=(h-fd[0]+a-1)//a
    fd+=c*a
    ans+=c
  pre_x=x
print(ans)

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(key=lambda x:x[0])
import numpy as np
fd=np.zeros(xh[-1][0]+1,np.int64) # fd[i]:座標iにいるモンスターに与えたダメージ
ans=0
for x,h in xh:
  if h-fd[x]<=0:
    continue
  else:
    c=(h-fd[x]+a-1)//a
    fd[x:min(xh[-1][0]+1,x+2*d+1)]+=c*a
    ans+=c
print(ans)

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(key=lambda x:x[0])
import numpy as np
fd=np.zeros(xh[-1][0]+1,np.int64) # fd[i]:座標iにいるモンスターに与えたダメージ
ans=0
for x,h in xh:
  if h-fd[x]<=0:
    continue
  else:
    c=(h-fd[x]+a-1)//a
    fd[x:x+2*d+1]+=c*a
    ans+=c
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A))+1
lst.sort(key=itemgetter(0))
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A))+1
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)