Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
from collections import deque
N, D, A = 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()))
pair_xh.sort(key = lambda x: x[0]) #座標でソート
 
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[-1][0] < x: # 範囲外になったら喰らわないから累積和から外す
        total -= q_lim_d[-1][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: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    down = [0] * (N+1)


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] = b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    down = [0] * (N+1)


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect_left(X,X[i]+2*D)] = b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(-x); XH.append((-x,h))
    XH.sort()
    X.sort()
    down = [0] * N


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] = b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    X.append(INF)
    down = [0] * N


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect_left(X,X[i]+2*D+1)-1] = b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()

    down = [0] * N


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] = b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

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()

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

print(cnt)

Submission status: Wrong Answer

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

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

monsters = sorted(monsters)

id = 0
ans = 0

while id < N:
    nowX, nowH = monsters[id][0], monsters[id][1]
    damage = 0

    if nowH > 0:
        damage += A * ((nowH + A -1) // A)
        ans += (nowH + A -1) // A

    next_id = id+1
    while next_id < N:
        if monsters[next_id][0] > nowX + 2*D: break

        monsters[next_id][1] -= damage
        if monsters[next_id][1] <= 0: break
        
        next_id += 1
        
    id = next_id

print(ans)

Submission status: Wrong Answer

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

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

xh.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)

bit = BitImos(n)
ans = 0
att = [0]*n
cnt = 0

for i in range(n):
    tmp = xh[i][0] + 2 * d
    while cnt < n:
        if xh[cnt][0] < tmp:
            cnt += 1
        else:
            break
    att[i] = min(cnt, n-1)

for i,xh1 in enumerate(xh):
    x,h = xh1
    if bit.get(i) < h:
        at = -(-(h - bit.get(i)) // a)
        ans += at
        bit.add(i, att[i]+1, at*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()
for i in range(N):
    XH[i][1]=-(-XH[i][1]//A)
X=[x for x,a in XH]
far=[0]*N
for i in range(N):
    far[i]=bisect.bisect_right(X,X[i]+2*D)-1

ans=0
for i in range(N):
    x=XH[i][0]
    hp=XH[i][1]
    if x<=0:
        continue
    for j in range(i,far[i]+1):
        XH[j][1]-=hp
    ans+=hp
print(ans)

Submission status: Wrong Answer

Solution code:
#problems2
#silver fox vs monster
import math
N,D,A=map(int,input().split())
d=[]
for _ in range(N):
    x,h=map(int,input().split())
    d.append((x,h))
d.sort(key=lambda x:x[0])

now_damage=0
from collections import deque
d=deque(d)
ans=0
d_field=deque()
while d:
    x=d.popleft()
    place,life=x
    if d_field:
        if d_field[0][0]<place:
            now_damage-=A*d_field[0][1]
            d_field.popleft()
        else:
            pass            
    if life<=now_damage:
        pass
    elif life>now_damage:
        K=math.ceil((life-now_damage)/A)
        ans+=K
        now_damage+=K*A
        d_field.append((2*D+place,K))        
print(ans)

Submission status: Wrong Answer

Solution code:
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.sort()
ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
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()
ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
ab = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    ab.append([x, h])
ab.sort()

hp_memo = []

for i in range(n):
    hp_memo.append(ab[i][1])

attack_count = 0

#print(hp_memo)

for i in range(n):
    if hp_memo[i] > 0:
        if hp_memo[i]%a==0:
            attack_count += (hp_memo[i]//a)
            damage = hp_memo[i]
        else:
            attack_count += 1+(hp_memo[i]//a)
            damage = (1+a)*(hp_memo[i]//a)
        right = ab[i][0]+(2*d)
        while i < n and ab[i][0] <= right :
            hp_memo[i] -= damage
            i += 1
        #print(hp_memo,damage)

print(attack_count)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
ab = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    ab.append([x, h])
ab.sort()

hp_memo = []

for i in range(n):
    hp_memo.append(ab[i][1])

attack_count = 0

dnage = 0

#print(hp_memo)

for i in range(n):
    if hp_memo[i] > 0:
        if hp_memo[i]%a==0:
            attack_count += (hp_memo[i]//a)
            damage = hp_memo[i]
        else:
            attack_count += 1+(hp_memo[i]//a)
            damage = hp_memo[i]%a+hp_memo[i]
        right = ab[i][0]+(2*d)
        while i < n and ab[i][0] <= right :
            hp_memo[i] -= damage
            i += 1
        #print(hp_memo,damage)

print(attack_count)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
ab = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    ab.append([x, h])
ab.sort()

hp_memo = []

for i in range(n):
    hp_memo.append(ab[i][1])

attack_count = 0

dnage = 0

print(hp_memo)

for i in range(n):
    if hp_memo[i] > 0:
        if hp_memo[i]%a==0:
            attack_count += (hp_memo[i]//a)
            damage = hp_memo[i]
        else:
            attack_count += 1+(hp_memo[i]//a)
            damage = hp_memo[i]%a+hp_memo[i]
        right = ab[i][0]+(2*d)
        while i < n and ab[i][0] <= right :
            hp_memo[i] -= damage
            i += 1
        #print(hp_memo,damage)

print(attack_count)

Submission status: Wrong Answer

Solution code:
import sys, heapq
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = [[int(_) for _ in input().split()] for _ in range(N)]
He = [[2 * x, h, 0] for x, h in XH]
heapq.heapify(He)
now = 0
ans = 0
while He:
    x, h, t = heapq.heappop(He)
    if t:
        now -= h
    else:
        if h - D * now > 0:
            diff = (h - now - 1) // A + 1
            now += diff
            ans += diff
            heapq.heappush(He, [x + 4 * D + 1, diff, 1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, collections
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = sorted([[int(_) for _ in input().split()] for _ in range(N)])
R = collections.deque([])
bombs_ = {}
for i, xh in enumerate(XH):
    R += [xh[0] + 2 * D + 1]
    while R[0] <= xh[0]:
        bombs_[R.popleft() - 2 * D - 1] = i
while R:
    bombs_[R.popleft() - 2 * D - 1] = i + 1
bombs = {}
for i, xh in enumerate(XH):
    bombs[i] = bombs_[XH[i][0]]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = sorted([[int(_) for _ in input().split()] + [0] for _ in range(N)])
XH2 = [[xh[0] + 2 * D + 1, i, 1] for i, xh in enumerate(XH)]
XH3 = sorted(XH + XH2)
bombs = [-1] * N
for i, xh in enumerate(XH3):
    if xh[2]:
        bombs[xh[1]] = i - xh[1]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = sorted([[int(_) for _ in input().split()] + [0] for _ in range(N)])
XH2 = [[xh[0] + 2 * D + 1, i, 1] for i, xh in enumerate(XH)]
XH3 = sorted(XH + XH2)
bombs = [-1] * N
for i, xh in enumerate(XH3):
    if xh[2]:
        bombs[xh[1]] = i - xh[1]


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def get_val(self, a):
        a += self.n
        res = self.dat[a]
        while a:
            if self.laz[a] != self.ei:
                res = self.g(res, self.laz[a])
            a //= 2
        return res

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#RMQ and RAQ
array = [(xh[1], 1) for xh in XH]
f = max
g = lambda a, b: (a[0] + a[1] * b, a[1])
h = lambda a, b: a + b
ti = (-float('inf'), 0)
ei = 0

LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
ans = 0
for i in range(N):
    this = LST.query(i, i + 1)[0]
    if this > 0:
        c = (this - 1) // A + 1
        ans += c
        LST.update(i, bombs[i], -A * c)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

n,d,a = map(int,input().split())
X = [0]*n
H = [0]*n

for i in range(n):
  X[i],H[i] = map(int,input().split())    
  
ans = 0
for i in range(n):
  if H[i] > 0:
    cnt = ceil(H[i] // a)
    dmg = cnt * a    
    for j in range(i+1,n):      
      if abs(X[j] - X[i]) <= d*2+1:        
        H[j] -= dmg
      else:
        break
    ans += cnt

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import operator


import operator


class SegmentTree():

    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [init_value for i in range(treesize)]
        # 遅延評価用の更新値キャッシュ
        self.is_dirty = [False for i in range(treesize)]
        self.uv = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, i+1, x)
        return st
    
    def _lazy_eval(self, k):
        """ノードの遅延評価"""
        if not self.is_dirty[k]:
            return
        n = len(self.st) // 2
        if k < n:
            self.uv[k * 2] = self.uv[k]
            self.is_dirty[k * 2] = True
            self.uv[k * 2 + 1] = self.uv[k]
            self.is_dirty[k * 2 + 1] = True
        self.st[k] = self.uv[k]
        self.uv[k] = 0
        self.is_dirty[k] = False
    
    def _update(self, a, b, value, k, l, r):
        """区間[a, b) に対する値の更新
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] = value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
    
    def update(self, a, b, value):
        """区間[a, b) に対する値の更新"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._update(a, b, value, k=1, l=0, r=n)
    
    def _add(self, a, b, value, k, l, r):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] = self.st[k] + value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._add(a, b, value, k=1, l=0, r=n)
    
    def _query(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query(a, b, k * 2, l, mid)
        rv = self._query(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._query(a, b, k=1, l=0, r=n)


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = SegmentTree(N)
    for i, (x, h) in enumerate(XH):
        st.update(i, i+1, h)

    ans = 0
    i = 0
    while i < N:
        l = XH[i][0]
        r = l + 2 * D + 1
        c = XH[i][1] // A + (XH[i][1] % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, l)
        ridx = bisect.bisect_left(X, r)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        i += 1
        while i < N:
            m = st.query(i, i+1)
            if m > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
import bisect
import operator


import operator


class SegmentTree():

    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [init_value for i in range(treesize)]
        # 遅延評価用の更新値キャッシュ
        self.is_dirty = [False for i in range(treesize)]
        self.uv = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, i+1, x)
        return st
    
    def _lazy_eval(self, k):
        """ノードの遅延評価"""
        if not self.is_dirty[k]:
            return
        n = len(self.st) // 2
        if k < n:
            self.uv[k * 2] = self.uv[k]
            self.is_dirty[k * 2] = True
            self.uv[k * 2 + 1] = self.uv[k]
            self.is_dirty[k * 2 + 1] = True
        self.st[k] = self.uv[k]
        self.uv[k] = 0
        self.is_dirty[k] = False
    
    def _update(self, a, b, value, k, l, r):
        """区間[a, b) に対する値の更新
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] = value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
    
    def update(self, a, b, value):
        """区間[a, b) に対する値の更新"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._update(a, b, value, k=1, l=0, r=n)
    
    def _add(self, a, b, value, k, l, r):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] += value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._add(a, b, value, k=1, l=0, r=n)
    
    def _query(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query(a, b, k * 2, l, mid)
        rv = self._query(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._query(a, b, k=1, l=0, r=n)


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = SegmentTree(N)
    for i, (x, h) in enumerate(XH):
        st.update(i, i+1, h)

    ans = 0
    i = 0
    while i < N:
        l = XH[i][0]
        r = l + 2 * D + 1
        c = XH[i][1] // A + (XH[i][1] % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, l)
        ridx = bisect.bisect_left(X, r)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        i += 1
        while i < N:
            m = st.query(i, i+1)
            if m > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))