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 bisect
import numpy as np
n,d,a = map(int,input().split())
lis = []
for i in range(n):
    x, h = map(int, input().split())
    lis.append([x, h])
xs = []
hs = []

lis.sort()
for x,h in lis:
    xs.append(x)
    hs.append(h)
xs = np.array(xs)
hs = np.array(hs)

ans = 0
for i in range(len(hs)):
    idx = np.searchsorted(xs, xs[i]+2*d)
    sub = hs[i]//a if hs[i]%a==0 else hs[i]//a + 1

    hs[i:idx+1] = np.maximum(0,hs[i:idx+1]-(a * sub))

    ans += sub

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right

sys.setrecursionlimit(500000)


class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)
 
    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret

def main():
    N, D, A = map(int, input().split())
    monsters = []
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = map(int, input().split())
        monsters.append((X[i],H[i]))

    seg = DualSegmentTree(N)
    monsters.sort()
    ans = 0
    for i in range(N):
        tmp_dist = monsters[i][0] + 2 * D
        tmp_hp = int(monsters[i][1] - seg.query(i))
        if tmp_hp <= 0:
            continue
        idx = bisect_right(H, tmp_dist)
        cnt = tmp_hp // A if tmp_hp % A == 0 else tmp_hp // A + 1
        ans += cnt
        seg.update(i,idx,cnt*A)

    print(ans)
    


    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

class LazySegTree:
    '''
    0-indexedで実装していることに注意
    '''

    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2

        self.N = N
        self.node = [0] * (2 * self.N - 1)
        self.lazy = [0] * (2 * self.N - 1)

        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N - 2, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    # k番目のノードについて遅延評価を行う
    def eval(self, k, l, r):

        if self.lazy[k] != 0:
            self.node[k] += self.lazy[k]

            if r - l > 1:
                self.lazy[2 * k + 1] += self.lazy[k] / 2
                self.lazy[2 * k + 2] += self.lazy[k] / 2

            self.lazy[k] = 0

    # [a, b)にx加える
    def add(self, a, b, x, k = 0, l = 0, r = -1):
        if r < 0:
            r = self.N
        
        self.eval(k, l, r)

        if b <= l or r <= a:
            return

        if a <= l and r <= b:
            self.lazy[k] += (r - l) * x
            self.eval(k, l, r)
        else:
            self.add(a, b, x, 2*k + 1, l, (l + r)//2)
            self.add(a, b, x, 2*k + 2, (l + r)//2, r)
            self.node[k] = self.node[2*k+1] + self.node[2*k+2]

    # [a, b)の和を取得
    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or r <= a:
            return 0

        self.eval(k,l,r)
        if a <= l and r <= b:
            return self.node[k]

        vl = self.getsum(a, b, 2*k + 1, l, (l + r)//2)
        vr = self.getsum(a, b, 2*k + 2, (l + r)//2, r)

        return vl + vr
    
def main():
    N, D, A = map(int, input().split())
    monsters = []
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = map(int, input().split())
        monsters.append((X[i],H[i]))

    V = [0] * N
    seg = LazySegTree(V)
    monsters.sort()
    ans = 0
    for i in range(N):
        tmp_dist = monsters[i][0] + 2 * D
        tmp_hp = int(monsters[i][1] - seg.getsum(i,i+1))
        if tmp_hp <= 0:
            continue
        idx = bisect_right(H, tmp_dist)
        cnt = tmp_hp // A if tmp_hp % A == 0 else tmp_hp // A + 1
        ans += cnt
        seg.add(i,idx,cnt*A)

    print(ans)
    

    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i] - damage[i-1]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)

Submission status: Wrong Answer

Solution code:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i] - damage[i-1]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)
print(damage)

Submission status: Wrong Answer

Solution code:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if n > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i] - damage[i-1]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
m = []
for _ in range(n):
    x, h = map(int, input().split())
    c = []
    c.append(x - d)
    c.append(x + d)
    c.append(h)
    m.append(c)
m.sort()
j = 0
ans = 0
for i in range(n):
    x = m[i][1]
    y = m[i][2]
    while True:
        if j == n:
            j -= 1
            break
        if x <= m[j][0]:
            break
        j += 1
    if y > 0:
        c = y // a
        #print(c)
        if y % a != 0 and y > 0:
            c += 1
        #print(i, j)
        for k in range(i, j + 1):
            m[k][2] = m[k][2] - c * a
        #print(m)
        ans += c
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()
j = 0
cnt = [0] * n
taken = 0

# def problem(h):
#     if h <= 0:return 0
#     ans = h//a
#     if h%a :
#         ans += 1
#     return ans

for i in range(n):
    [x,h] = xh[i]
    while xh[j][0] + 2*d < x:
        taken -= cnt[j]
        j += 1
    if taken * a >= h:
        break
    if h % a == 0:
        cnt[i] = h//a - taken
    else:
        cnt[i] = h//a - taken + 1
    #cnt[i] = problem(h - taken * a)
    taken += cnt[i]
print(sum(cnt))

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()
j = 0
cnt = [0] * n
taken = 0

for i in range(n):
    [x,h] = xh[i]
    while xh[j][0] + 2*d < x:
        taken -= cnt[j]
        j += 1
    if taken * a >= h:
        break
    if not h % a:
        cnt[i] = h//a -taken
    else:
        cnt[i] = h//a - taken + 1
    taken += cnt[i]
print(sum(cnt))

Submission status: Wrong Answer

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

xh.sort()
que = deque()
cnt = [0] * n
flag = 1

for i in range(n):
    [x,h] = xh[i]
    if que:
        j = que.popleft()
        while xh[j][0] + 2*d < x:
            if not que:
                flag = 0
                j = i
                break
            j = que.popleft()
        if flag:
            que.appendleft(j)
        flag = 1
    else:
        j = i
    taken = sum(cnt[j:i])
    if taken * a >= h:
        break
    if not h % a:
        cnt[i] = h//a -taken
        que.append(i)
    else:
        cnt[i] = h//a - taken + 1
        que.append(i)
print(sum(cnt))

Submission status: Wrong Answer

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

m.sort()

x = [s[0] for s in m]
h = [s[1] for s in m]

dh = [0] * (n+1)
dh[0] = h[0]
for i in range(n-1):
    dh[i+1] = h[i+1] - h[i]

ans = 0
import bisect
for i in range(n):
    if i != 0:
        h[i] = h[i-1] + dh[i]
    if h[i] > 0:
        count = (h[i] + a - 1) // a
        ans += count
        damage = count * a
        h[i] -= damage
    r = bisect.bisect_right(x, x[i] + 2 * d)
    dh[r] += damage
print(ans)

Submission status: Wrong Answer

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

m.sort()

x = [s[0] for s in m]
h = [s[1] for s in m]

dx = [0] * n
for i in range(n-1):
    dx[i] = h[i+1] - h[i]

ans = 0
import bisect
for i in range(n):
    if i != 0:
        h[i] = h[i-1] + dx[i-1]
    if h[i] > 0:
        count = (h[i] + a - 1) // a
        ans += count
        damage = count * a
    r = bisect.bisect_right(x, x[i] + 2 * d)
    dx[i] -= damage
    dx[r-1] += damage
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from bisect import bisect_right
n, d, a = map(int, input().split())
monster = [tuple(map(int, input().split())) for _ in range(n)]
monster.sort(key=itemgetter(0))
xx = [xi for xi, hi in monster]

ans = 0
imos = [0] * (n + 1)
for i, (xi, hi) in enumerate(monster):
    hi -= imos[i]
    c = (hi + a - 1) // a
    ans += c
    idx = bisect_right(xx, xi + 2 * d)
    imos[i] += c * a
    imos[idx] -= c * a

    # update imos
    imos[i + 1] += imos[i]

print(ans)

Submission status: Wrong Answer

Solution code:
def binary_search(v, is_ok):
    """
    ソートしてから使え！！！
    v : list
        ある場所から左が条件を満たさず、右が条件を満たすように並んだ配列
    is_ok(x) : bool
        vの要素xが条件を満たすかどうかを返す関数
    """
    ng = -1             # 条件を満たさないiのうち今わかっている中で最大の値(v[0]が条件を満たすかもしれないので-1から)
    ok = len(v)         # 条件を満たすiのうち今わかっている中で最小の値(v[n-1]が条件を満たさないかもしれないのでnから)
    # okをできるだけ左に移動させてreturnする

    # ...... ng ok ......
    #          | ->
    # こうなるまで
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if is_ok(v[mid]):   # v[mid]はokであることがわかった
            ok = mid        # okを左に移動
        else:               # v[mid]はngであることがわかった
            ng = mid        # ngを右に移動

    return ok



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

yuukou = 0
mou_mukou = [0] * N + [0]
ans = 0

# lを左端としてn個爆弾を使う
def bomb(l, n):
    global ans, yuukou
    ans += n
    yuukou += n
    r = l + 2 * D
    mou_mukou[binary_search(X, lambda x: r < x)] += n


for i in range(N):
    yuukou -= mou_mukou[i]
    H[i] -= yuukou
    if H[i] > 0:
        bomb(X[i], H[i])

print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
H = [list(map(int, input().split())) for i in range(N)]
H.sort(key = lambda x:x[0])
INF = int(1e18)
H.append((INF, INF))

ans = 0
S = [0] * (N + 1)
l, r = 0, 0
while r < N:
    while H[r][0] - H[l][0] <= D * 2: r += 1
    h = H[l][1] - S[l]
    num = (h - 1) // A + 1 if h > 0 else 0
    ans += num
    S[l] += A * num
    S[r] -= A * num
    l += 1
    S[l] += S[l - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from math import ceil
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
x=[xh[i][0] for i in range(n)]
xh.sort(key=lambda y:y[0])
x.sort()
l=[0]*n
for i in range(n):
  j=bisect.bisect_right(x,x[i]+2*d)
  l[i]=j
ans=0
idx=0
while idx<n:
  max_h=0
  for i in range(idx,l[idx]):
    max_h=max(max_h,xh[i][1])
  ans+=ceil(max_h/a)
  idx=l[idx]
print(ans)

Submission status: Wrong Answer

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

xh.sort()
xs = [x for x, h in xh]

memo = [0 for _ in range(n)]

ans = 0

for j, (x, h) in enumerate(xh):
    memo[j] +=  memo[j-1]
    b = h - memo[j]
    if b > 0:
        c = (b + a - 1) // a
        memo[j] += c * a
        ans += c
        i = bisect.bisect_left(xs, x + 2 * d)
        if i < n:
            memo[i] -= c * a

print(ans)

Submission status: Wrong Answer

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

xh.sort()
xs = [x for x, h in xh]

memo = [0 for _ in range(n)]

ans = 0

for j, (x, h) in enumerate(xh):
    memo[j] = memo[j-1]
    b = h - memo[j]
    if b > 0:
        c = (b + a - 1) // a
        memo[j] += c * a
        ans += c
        i = bisect.bisect_left(xs, x + 2 * d)
        if i < n:
            memo[i] -= c * a

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
#%%
bound = [0]*N
idx = 0
right = 0
while idx<N:
    while right < N and (XH[right][0]-XH[idx][0])<=2*D:
        right += 1
    bound[idx] = right  
    idx += 1
def kiriage(n,m):
    return (n+(m-1))//m

heru = [0]*(N+1)
ans = 0
damage = 0
for i in range(N):
    damage -= heru[i]
    if XH[i][1]<=damage:
        continue
    cnt = kiriage(XH[i][1]-damage,A)
    ans += cnt
    damage += cnt*A
    heru[bound[i]] = cnt*A
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math

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

bound = [0]*N
idx = 0
right = 0
while idx<N:
    while right < N and (XH[right][0]-XH[idx][0])<=2*D:
        right += 1
    bound[idx] = right  
    idx += 1

heru = [0]*(N+1)
ans = 0
damage = 0
for i in range(N):
    damage -= heru[i]
    cnt = math.ceil((XH[i][1]-damage)/A)
    ans += cnt
    damage += cnt*A
    heru[bound[i]] = cnt*A
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
ans = 0
i = 0
while i < N:
    x, hp = monsters[i]
    i = bisect_right(position, x + 2*D)
    attack = div_ceil(hp, A)
    ans += attack
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
ans = 0
i = 0
while i < N:
    x, hp = monsters[i]
    if hp <= 0: continue
    i = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
import math
N, D, A = tuple(map(int, input().split(" ")))
XH = []
for _ in range(N):
    XH.append(list(map(int, input().split(" "))))

XH = numpy.array(XH, dtype="int64").T

ans = 0
for i in range(N):
    if XH[1][i] <= 0:
        continue

    bomb_count = math.ceil(XH[1][i] / A)
    ans += bomb_count

    in_range = (XH[0] <= XH[0][i]+2*D)
    XH[1] += in_range * (-bomb_count * A)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N,D,A = list(map(int, input().split()))
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
  # X,H

P.sort()

# P[i]において、x+D+1に爆弾をうったとき影響がある人を探索する（x+2D+1までに含まれるポイントを持つ）
left_i, right_i = 0, 1
EffectS = {} # key: i , value: list(i,j1,j2,...)
workS = set()
for i in range(N):
  workS.add(i) # self
  while True:
    if right_i >= N:
      break
    if P[i][0] + 2*D + 1 < P[right_i][0]:
      break
    workS.add(right_i)
    right_i += 1
  EffectS[i] = list(workS)
  workS.remove(i)

# iを走査して、左端にギリギリ入る範囲で何回爆弾をうつべきか、その場合のダメージ計算をすべてに実施、を繰り返す
ans = 0
for i in range(N):
  x, h = P[i]
  counts = ceil(h / A)
  ans += counts
  for damage in EffectS[i]:
    P[damage][1] -= counts * A
    
print(ans)

Submission status: Wrong Answer

Solution code:
N, D, a = [int(x) for x in input().split()]
XH = []
for _ in range(N):
    XH.append([int(x) for x in input().split()])
XH.sort()

#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 

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

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

#入力
n = N
A = [0] * N

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

#init
init(A)

import bisect

X = []
H = []
for i in XH:
    X.append(i[0])
    H.append(i[1])
ans = 0
for i in range(N):
    x, h = X[i], H[i]
    idx_left = bisect.bisect_left(X, x - 2 * D)
    idx_right = bisect.bisect_right(X, x + 2 * D)
    if query(idx_left, idx_right + 1) < h:
        cnt = h // a + int(h % a != 0)
        ans += cnt
        update(i, a * cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
x_ = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]
x_ = np.searchsorted(x,x+2*d,side='right')

ans = 0
for i in range(n):
    if h[i] > 0:
        num = math.ceil(h[i]//a)
        ans += num
        h[i:x_[i]] -= num*a
        
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

ans = 0
for i in range(n):
    if h[i] > 0:
        num = math.ceil(h[i]//a)
        ans += num
        h[i:][:np.searchsorted(x[i:],x[i]+2*d,side='right')] -= num*a
        
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

ans = 0
for i in range(n):
    if h[i] > 0:
        num = math.ceil(h[i]//a)
        ans += num
        h[i:np.searchsorted(x,x[i]+2*d,side='right')] -= num*a
        
print(int(ans))

Submission status: Wrong Answer

Solution code:
import math
import collections
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q):

        if q[0][0] < x:
            t = q.popleft()
            c -= t[1]
        else:
            break
    h -= c*A
    k = math.ceil(max(h, 0) / A)
    ans += k
    c += k
    q.append((x+(2*D), c))
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)]

enemy = {}
field = {}
for i, (Xi, Hi) in enumerate(XH):
    enemy[str(Xi)] = field.setdefault(str(Xi), 0) + Hi
    field[str(Xi)] = field.setdefault(str(Xi), 0)
    field[str(Xi + 2 * D + 1)] = field.setdefault(str(Xi + 2 * D + 1), 0)

poss = sorted(list(map(int, field.keys())))
# print("#", enemy)

ans = 0
state = 0
for pos in poss:
    key = str(pos)
    state += field[key]
    if state < enemy.setdefault(key, 0):
        bomb = enemy.setdefault(key, 0) - state
        # print("#", pos, ((bomb + A - 1) // A))
        ans += (bomb + A - 1) // A
        state += A * ((bomb + A - 1) // A)
        field[str(pos + 2 * D + 1)] -= (bomb + A - 1) // A

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, D, A= map(int,input().split())
X = [0] * N
H = [0] * N
Y = []
for i in range(N):
    X[i], H[i] = map(int, input().split())
    Y.append([X[i] ,math.ceil(H[i] / A)])
Y.sort()
d = 0

while len(Y) > 0:
    y_min = Y[0][1]
    c = 0
    d += y_min
    for i in range(len(Y)):
        if Y[i][0] < Y[0][0] + 2 * D + 1:
            Y[i][1] = Y[i][1] - y_min
            if Y[i][1] <= 0:
                c += 1
    del Y[0:c]
print(d)

Submission status: Wrong Answer

Solution code:
N, D, A = [int(x) for x in input().split(' ')]
m = []
for i in range(N):
  X, H = [int(x) for x in input().split(' ')]
  a = H // A + int(H % A >= 1)
  m.append([X, a])
m.sort(key=lambda x: x[0])
rng = 2 * D + 1
atk = 0
for i in range(N):
  if m[i][1] > 0:
    atk += m[i][1]
  else:
    continue
  for j in range(i+1, N):
    if m[j][0] - m[i][0] > rng:
      break
    m[j][1] -= m[i][1]
print(atk)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
import math
n, d, A = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
xh.sort(key=lambda x: x[0])

monster_x = []
monster_hp = []
for i in range(n):
    monster_x.append(xh[i][0])
    monster_hp.append(xh[i][1])

dist = 2 * d
ans = 0
damage = 0
cum_damage = [0] * (n + 1)
for i in range(n):
    cum_damage[i + 1] += cum_damage[i]
    damage = cum_damage[i + 1] * A
    if damage < monster_hp[i]:
        min_attack_num = math.ceil((monster_hp[i] - damage) / A) 
        index = bisect.bisect_right(monster_x, monster_x[i] + dist)
        cum_damage[i + 1] += min_attack_num
        if index < n:
            cum_damage[index] -= min_attack_num
        ans += min_attack_num

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
cnt=0
pos=0
damage=0
while 1:
  if pos==n:
    break
  l=arr[pos][0]
  r=l+2*d
  tmp=(arr[pos][1]+a-1)//a
  cnt+=tmp
  damage+=tmp*a
  pos+=1
  if pos==n:
    break
  while 1:
    if arr[pos][0]>r:
      damage=0
      break
    if arr[pos][1]>damage:
      arr[pos][1]-=damage
      break
    else:
      arr[pos][1]=0
      pos+=1
      if pos==n:
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
cnt=0
pos=0
while 1:
  if pos==n:
    break
  l=arr[pos][0]
  r=l+2*d
  tmp=(arr[pos][1]+a-1)//a
  cnt+=tmp
  damage=tmp*a
  pos+=1
  if pos==n:
    break
  while arr[pos][0]<=r:
    if arr[pos][1]<=damage:
      pos+=1
      if pos==n:
        break
    else:
      arr[pos][1]-=damage
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math

def main():
    n, d, a = [int(x) for x in sys.stdin.readline().split()]
    monsters = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]

    monsters.sort(key=lambda m: m[0])
    xs, hs = map(list, zip(*monsters))

    nbomb = 0
    for i in range(n):
        b = int(math.ceil(hs[i] / a))
        for j in range(i, n):
            if xs[j] - xs[i] > d * 2:
                break
            hs[j] -= b * a
        nbomb += b

    print(nbomb)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

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

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0:
        if bombs[0][0] < XH[i][0]:
            power -= bombs.popleft()[1]
        else:
            break

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)











"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

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

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)











"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計


for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A



print(ans)











"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D

# これより手前までを減らす
end = bisect.bisect_right(X, last)

while True:
    need = counting(XH[begin][1])
    ans += need
    

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break
                elif j == N-1:
                    end = N
                    break
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break
                elif j == N-1:
                    end = N
                    break







"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""