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: Accepted

Solution code:
from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])

POS = [v[0] for v in L]
ES = [0]*(N+1)
ans, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > c:
        t = L[i][1]-c
        ans += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(ans)

Submission status: Accepted

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

def main():
    def isok(z,val):##適宜変更
        return (z-val<=2*d)
    def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok ##一番右のTrueのindex  Trueの個数はok+1こ

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] #bisect用の配列

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:##体力が残ってたら
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys,x) ##爆風が届くぎりぎりの位置
            if idx==-1:continue
            damage[i] +=a*c
            damage[idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n, d, a = map(int, input().split())

monsters = []
for i in range(n):
    x, h = map(int, input().split())
    monsters.append((x, h))

monsters.sort()

attack = 0
que = deque([])
attack_num = 0

for monster in monsters:
    xx, hh = monster
    while que and que[0][0] < xx - d:
        attack -= que[0][1]
        que.popleft()

    # print("a", x, h, attack, que)

    if hh - attack <= 0:
        continue

    a_times = (hh - attack - 1) // a + 1
    attack_num += a_times
    attack += a_times * a
    que.append((xx + d, a_times * a))

    # print("b", attack, attack_num, que)

print(attack_num)

Submission status: Accepted

Solution code:
import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
count = 0
ans = 0

N, D, A = map(int, input().split())
Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))
Monster = [[x, ceil(h/A)] for x, h in Monster]
Monster.sort()
que = deque([])

for x,h in Monster:
    # 範囲外となったダメージを削除する
    while que and x > que[0][0]:
        a, b = que.popleft()
        count -= b
    # 範囲内で既に起きたダメージを受ける
    need = max(0, h-count)
    ans += need
    count += need
    # 爆発が届く限界と起きた回数を記録しておく
    que.append([x + 2*D, need])
print(ans)

Submission status: Accepted

Solution code:
import bisect
n,d,a = map(int,input().split())
lst = []
x = []
for i in range(n):
    xi,hi = map(int,input().split())
    lst.append([xi,hi,0])
    x.append(xi)
lst.sort()
x.sort()
count = 0
cur = 0
for i in range(n):
    if lst[i][1]-cur > 0:
        num = -(-(lst[i][1]-cur)//a)
        count += num
        damage = a * num
        cur += damage
        index = bisect.bisect(x,x[i]+2*d)
        if index != n:
            lst[index-1][2] += damage
    cur -= lst[i][2]
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline


class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()

        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    def propagates(self, ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)

        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline


class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()

        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import deque


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    revert = deque()
    currentDamage = 0
    for m in M:
        while len(revert) > 0 and revert[0][0] < m[0]:
            currentDamage -= revert[0][1]
            revert.popleft()
        nextDamage = max(0, m[1] - currentDamage)
        needAttack = math.ceil(nextDamage/A)
        currentDamage += needAttack * A
        result += needAttack
        if needAttack > 0:
            revert.append((m[0]+2*D, needAttack*A))
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
n,d,a = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(n)]
m.sort()
l = [(x, ceil(h/a)) for x,h in m]

ans = 0
damage = 0
que = deque([])

for x,h in l:
    while que and que[0][0] < x:
            s,t = que.popleft()
            damage -= t
    need = max(0, h - damage)
    ans += need
    damage += need
    if need:
        que.append((x+2*d, need))
print(ans)

Submission status: Accepted

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 = []

    for i in range(N):
        x, h = map(int, input().split())
        monsters.append((x,h))

    seg = DualSegmentTree(N)
    monsters.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = monsters[i]
    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(X, 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: Accepted

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

monster.sort()

H=[monster[i][1] for i in range(0,N)]

right_2d=[0 for i in range(0,N)]
for i in range(0,N):
    start=i
    end=N-1
    while end-start>1:
        test=(end+start)//2
        if 2*D+monster[i][0]>=monster[test][0]:
            start=test
        else:
            end=test
    if 2*D+monster[i][0]>=monster[end][0]:
        right_2d[i]=end
    else:
        right_2d[i]=start

imos=[0 for i in range(0,N+1)]
ans=0
for i in range(0,N):
    H[i]-=imos[i]
    if H[i]>0:
        count=(H[i]+A-1)//A
        ans+=count
        imos[i]+=A*count
        imos[right_2d[i]+1]-=A*count

    imos[i+1]+=imos[i]

print(ans)

Submission status: Accepted

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]:
            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: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect

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

log=[]
loc=[]
ene=[]

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

log.sort(key=lambda x:x[0])

for X,H in log:
    loc.append(X)
    ene.append(H)

syokan=[0]*N

power=0
for i in range(N):
    temp=max(-((-ene[i]+power)//A),0)*A
    power+=temp
    
    rng=bisect.bisect_right(loc,loc[i]+2*D)
    syokan[min(rng-1,N-1)]+=temp
    
    power-=syokan[i]
    #print(syokan)
#print(syokan)
print(sum(syokan)//A)

Submission status: Accepted

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:
        continue
    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: Accepted

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 not h % a:
    #     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: Accepted

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]

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

Submission status: Accepted

Solution code:
from operator import itemgetter
from bisect import bisect_right
import sys
input = sys.stdin.readline

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]

# 尺取
d_range = [-1] * n
idx = 0
for i, (xi, hi) in enumerate(monster):
    while idx < n and xx[idx] - xi <= 2 * d:
        idx += 1
    d_range[i] = idx

ans = 0
imos = [0] * (n + 1)
for i, (xi, hi) in enumerate(monster):
    hi -= imos[i]
    if hi > 0:
        c = (hi + a - 1) // a
        ans += c
        idx = d_range[i]
        imos[i] += c * a
        imos[idx] -= c * a

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

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from bisect import bisect_right
import sys
input = sys.stdin.readline

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]
    if hi > 0:
        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: Accepted

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]
    if hi > 0:
        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: Accepted

Solution code:
import bisect

n, d, a = map(int, input().split())
XB = []
X = []
for _ in range(n):
    x, h = map(int, input().split())
    bomb = int(-(-h//a))
    XB.append([x, bomb])
    X.append(x)

XB = sorted(XB, key=lambda x:x[0])
X = sorted(X)

# x1+dがx2-d以上のときに、まとめてダメージを与えられる
# x2がダメージを受けうる、x1を二分探索する

X_range = [[-1]]

for i in range(1,n):
    now = X[i]
    # X[x_ind]以上の爆弾ダメージをX[i]は受ける
    x_ind = bisect.bisect_left(X, X[i]-2*d)
    if x_ind == i:
        X_range.append([-1])
    else:
        X_range.append([x_ind, i-1])

# print(X)

# 各箇所で何回爆弾を使用したのかを保持 -> 累積しておく
# X[i]を見るときに、X[i-1]~X[ind]間で使用した爆弾の個数を求める
# 足りない文はX[i]で爆発させる

Bomb = [XB[0][1]]
Bomb_rui = [0, XB[0][1]]

for i in range(1,n):
    need_bomb = XB[i][1]
    if X_range[i][0] == -1:
        Bomb.append(need_bomb)
        Bomb_rui.append(Bomb_rui[-1]+need_bomb)
    else:
        before_bomb = Bomb_rui[X_range[i][1]+1] - Bomb_rui[X_range[i][0]]
        if before_bomb >= need_bomb:
            Bomb.append(0)
            Bomb_rui.append(Bomb_rui[-1])
        else:
            need_bomb -= before_bomb
            Bomb.append(need_bomb)
            Bomb_rui.append(Bomb_rui[-1]+need_bomb)

ans = Bomb_rui[-1]
# print(Bomb)
# print(Bomb_rui)
# print(X_range)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

N, D, A = map(int, input().split())
monsters = [(-1, -1)]
for _ in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()
#print("monsters = {}".format(monsters))
"""
どうせ左端のモンスターはいつか倒さないといけない（かつ爆弾投下順は不問）ので、
左端のモンスターから順に、なるべく爆弾を右に寄せて落としていけば良い。

別解としてBITでも殴ってみた
"""
class BIT:
    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    """
    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)

"""
BITで区間に対する加算をする場合はimos法を利用することに注意する
"""

Damage = BIT(N)
ans = 0
for i in range(1, N + 1):
    x, h = monsters[i]
    d = Damage.sum(i) # モンスターiに入っているダメージ
    if d < h:
        times = ceil((h - d) / A)
        ans += times
        new_damage = times * A
        #print("ans+={} for monster {}".format(times, i))

        idx = bisect_right(monsters, (monsters[i][0] + 2 * D, 10**10))
        Damage.add(i, new_damage)
        if idx != N + 1:
            Damage.add(idx, -new_damage)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_right
from math import ceil

N, D, A = map(int, input().split())
monsters = []
for _ in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()
#print("monsters = {}".format(monsters))
"""
どうせ左端のモンスターはいつか倒さないといけない（かつ爆弾投下順は不問）ので、
左端のモンスターから順に、なるべく爆弾を右に寄せて落としていけば良い。

BITを使って区間に爆弾のダメージを追加して考えても良いが、
ここではimos法チックな回答を与える。

仮に全ての爆弾が前モンスターに攻撃を与えるとしよう。
すると各モンスターにどれだけ流れダメージが飛んできたかは累積和で求まる。->totalで累積ダメージを管理。
しかし今回は爆弾に有効範囲があるため、有効期限切れの爆弾ダメージはtotalから除く必要がある。
そこでキューに（爆弾のダメージが入る限界線、爆弾のダメージ）を追加していき、各モンスターを見たとき
爆弾の期限が切れていたらpopleftで期限切れ爆弾を捨てていく。
（それ以降のモンスターに対してもその爆弾は期限切れなので、永久に捨て去って問題ない）。

以下のサイトの解説が参考になりました↓
https://at274.hatenablog.com/entry/2020/02/01/060000
"""

total = 0
ans = 0
q = deque([])

for i in range(N):
    x, h = monsters[i]

    # 期限切れ爆弾を捨てていき、残ったまだ有効な爆弾分の累積ダメージをモンスターに与える
    while q and q[0][0] < x:
        total -= q[0][1]
        q.popleft()
    h -= total

    # まだモンスターも体力が残っていれば、爆弾で追加ダメージを与える
    if h > 0:
        # まずはモンスターをやっつける
        times = ceil(h / A)
        ans += times
        #print("ans+={} for monster {}".format(times, i))

        # その後後ろへの流れダメージをtotalに追加し、爆弾の有効範囲をキューに追加
        damage = times * A
        total += damage
        q.append((x + 2 * D, damage))

print(ans)

Submission status: Accepted

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


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


def compress(array):
    """座標圧縮したリストを返す"""
    array2 = sorted(set(array))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

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

info = sorted(info)
b = [info[i][0] for i in range(n)]
memo = compress([info[i][0] for i in range(n)])
bit = BIT(n)

for i in range(n):
    ind, val = info[i]
    bit.add(memo[ind], memo[ind] + 1, val)

ans = 0
for i in range(n):
    tmp = bit.get_val(i)
    if tmp <= 0:
        continue
    ans += -((-tmp) // a)
    nxt_ind = b[i] + 2 * d
    ii = bisect.bisect_right(b, nxt_ind)
    bit.add(i, ii, ((-tmp) // a) * a)
print(ans)

Submission status: Accepted

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 l < 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: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,D,A=map(int,input().split())
s=[tuple(map(int, input().split())) for i in range(N)]
s.sort()
d=2*D+1
t=0
p=0
l=[0]*N
a=0
for n,i in enumerate(s):
    while 1:
        if t<N and s[t][0]<i[0]+d:
            t+=1
        else:
            break
    h=i[1]-p*A
    if h>0:
        k=-(-h//A)
        a+=k
        p+=k
        l[t-1]+=k
    p-=l[n]
print(a)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, D, A = MI()
monsters = list()
for i in range(N):
    x, h = MI()
    monsters.append((x, (h + A - 1) // A))
monsters.sort()

X = [x for x, h in monsters]
ub = [0] * N
for i, x in enumerate(X):
    ub[i] = bisect_right(X, x + 2 * D)

dmg = [0] * N
accum = 0
ans = 0
for i, (x, h) in enumerate(monsters):
    h = h - max(0, accum + dmg[i])
    if h > 0:
        ans += h
        dmg[i] += h
        if ub[i] < N:
            dmg[ub[i]] -= h
    accum += dmg[i]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n,d,a=map(int,input().split())
l=[]
ans=0
for i in range(n):
    x,h=map(int,input().split())
    l.append((x,-(-h//a)))
l.sort()
back=[-1]
rui=[0]
for x,h in l:
    i=bisect_left(back,x)
    h-=rui[-1]-rui[i-1]
    if h<=0:
        continue
    ans+=h
    back.append(x+d*2)
    rui.append(rui[-1]+h)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left


def main():
    N, D, A = read_ints()
    XH = read_tuple(N)
    XH.sort()  # 座標でソート

    n_atk = []  # 何回攻撃するのが必要か
    X = []  # 座標アクセス用配列
    for x, h in XH:
        n_atk.append((h - 1) // A + 1)
        X.append(x)

    damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
    ans = 0
    # j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
    for i, (x, n) in enumerate(zip(X, n_atk)):
        damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
        atk = max(0, n - damege[i])  # iには何回攻撃したか
        ans += atk
        # 攻撃下回数を記録
        damege[i] += atk
        # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
        # while j < len(X) and X[j] < x + 2 * D + 1:  # あんま高速化しないね
        #     j += 1
        # damege[j] -= atk  # 効果切れを予約
        damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  # 二分探索で十分速い

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
# j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    if atk == 0:
        continue
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    # while j < len(X) and X[j] < x + 2 * D + 1:  # あんま高速化しないね
    #     j += 1
    # damege[j] -= atk  # 効果切れを予約
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  # 二分探索で十分速い


print(ans)