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.

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,D,A = MI()
    XH = LLIN(N)
    XH.sort()
    q = deque()
    ans = 0
    now = 0
    for x,h in XH:
        while q and x > q[0][0]:
            now -= q.popleft()[1]
        h-=now
        if h>0:
            ans += (h+A-1)//A
            q.append((x+2*D, ((h+A-1)//A)*A))
            now += ((h+A-1)//A)*A
    print(ans)
    



if __name__ == '__main__':
    main()

Solution (Python):
N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)

Solution (Python):
from operator import itemgetter
from collections import deque
import sys


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


e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0
atk_que = deque()
atk_acm_p = 0

for i in range(n):
    while len(atk_que) > 0:
        if atk_que[0][0] < e[i][0]:
            atk_u,atk_p = atk_que.popleft()
            atk_acm_p -= atk_p
        else:
            break
    e[i][1] -= atk_acm_p
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk_p = a * atk_times
    atk_acm_p += atk_p
    atk_que.append([atk_u,atk_p])

print(atk_times_sum)

Solution (Python):
from operator import itemgetter
from collections import deque
import sys


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


e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0
atk_que = deque()
atk_acm_p = 0

for i in range(n):
    while len(atk_que) > 0:
        if atk_que[0][0] < e[i][0]:
            atk_u,atk_p = atk_que.popleft()
            atk_acm_p -= atk_p
        else:
            break
    e[i][1] -= atk_acm_p
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk_p = a * atk_times
    atk_acm_p += atk_p
    atk_que.append([atk_u,atk_p])

print(atk_times_sum)

Solution (Python):
import math
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])


xh.sort()
x = [xh[i][0] for i in range(n)]
h = [math.ceil(xh[i][1]/a) for i in range(n)]



bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]

for i in range(n):
    bomb = 0
    if i == 0:
        bomb = h[i]
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = bomb_ruisekiwa[i-1]
        else:
            damage = bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]
        if h[i] - damage > 0:
            bomb = h[i] - damage
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Solution (Python):
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Solution (Python):
import bisect

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

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])


xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]


bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]

for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Solution (Python):
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])


xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]



bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]

for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Solution (Python):
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])


xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]



bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]

for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Solution (Python):
import math
from collections import deque
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()


"""
キューを使った貪欲法で間に合わせる。
que = [[ダメージ量,そのダメージがどこまで使えるか],...]
とすることにより、高速にダメージ管理をすることができる。
"""

que = deque()
ans = 0
dmg = 0

for i in range(n):
    while que:
        lim = que.popleft()
        if lst1[i][0] > lim[1]:
            dmg -= lim[0]
        else:
            que.appendleft(lim)
            break
    
    if lst1[i][1] > dmg:
        need = math.ceil((lst1[i][1]-dmg)/a)
        ans += need
        dmg += need*a
        que.append([need*a,lst1[i][0]+2*d])

print(ans)

Solution (Python):
import collections

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

queue = collections.deque()
ans = 0
damage = 0

for x, h in XH:
    while queue and queue[0][0] < x:
        damage -= queue.popleft()[1]

    h -= damage
    if h > 0:
        count = -(-h // A)
        ans += count

        queue.append((x + 2*D, count * A))
        damage += count * A

print(ans)

Solution (Python):
import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()


"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""
x = []
for i in lst1:
    x.append(i[0])


index = 0
reach = []
for i in range(n):
    index = bisect.bisect_right(x,lst1[i][0]+2*d)
    reach.append(index)


ans = 0
imos = [0]*(n+1) 

for i in range(n):
    if imos[i]*a < lst1[i][1]: 
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]] -= need 
        ans += need
    imos[i+1] += imos[i] 

print(ans)

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    buf = sys.stdin.buffer

    n, d, a = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))

    bomb_area = []
    bomb_power = []
    bomb_length = 0
    total_damage = 0
    ans = 0
    idx = 0
    for pos, hp in monsters:
        while idx < bomb_length:
            area = bomb_area[idx]
            if area < pos:
                power = bomb_power[idx]
                total_damage -= power
                idx += 1
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp - total_damage + a - 1) // a
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
            bomb_length += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    from collections import deque
    buf = sys.stdin.buffer
    
    n, d, a = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))
    
    bomb_area = deque([])
    bomb_power = deque([])
    total_damage = 0
    ans = 0
    for pos, hp in monsters:
        while bomb_area:
            area = bomb_area[0]
            if area < pos:
                bomb_area.popleft()
                power = bomb_power.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp - total_damage + a - 1) // a
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    from operator import itemgetter
    from collections import deque
    buf = sys.stdin.buffer
    
    n, d, a = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))
    
    bomb_area = deque([])
    bomb_power = deque([])
    total_damage = 0
    ans = 0
    for pos, hp in monsters:
        while bomb_area:
            area = bomb_area[0]
            if area < pos:
                bomb_area.popleft()
                power = bomb_power.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp - total_damage + a - 1) // a
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

N, D, A = map(int, input().split())
E = []
for _ in range(N):
    x, h = map(int, input().split())
    E.append((x, h))
    E.append((x+2*D, 0))

E = sorted(E, key=lambda x: (x[0], -x[1]))

for i in range(len(E)-1, -1, -1):
    x, h = E[i]
    if h != 0:
        xmax = x
        break

bomb = defaultdict(int)
damage = 0
ans = 0
for i in range(len(E)):
    x, h = E[i]

    if x > xmax:
        break

    
    if h == 0:
        damage -= bomb[x]
        continue

    h -= damage

    if h <= 0:
        continue

    x = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    bomb[x] = cnt * A
    ans += cnt

print(ans)

Solution (Python):
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)


left = 0 
right = n 
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = [0 for i in range(n)]
left = 0
already = 0
for i in range(n):
    while x[makikomi[left]] < x[i]:
        already -= cnt[left]
        left += 1
    cnt[i] = max(h[i] - already, 0)
    already += cnt[i]

print(sum(cnt))

Solution (Python):
N,D,A=map(int,input().split())
P=sorted([list(map(int,input().split())) for i in range(N)])
l=r=a=d=0
m=[0]*(N+1)
while l<N:
    while r<N and P[r][0]<=P[l][0]+2*D:
        r+=1
    d+=m[l]
    x=-(-max(0,P[l][1]-d)//A)
    a+=x
    d+=x*A
    m[r]-=x*A
    l+=1
print(a)

Solution (Python):
from collections import deque
def main():
    n, d, a = map(int, input().split())
    m = [list(map(int, input().split())) for _ in range(n)]
    m.sort()
    r = 1
    d *= 2
    q=deque([])
    for i in range(n):
        while r < n and m[i][0] + d >= m[r][0]:
            r += 1
        m[i].append(r)
        m[i][1] = (m[i][1] + a - 1) // a
    res = 0
    tdamage = 0
    for i in range(n):
        while q and q[0][0] <= i:
            minus = q.popleft()
            tdamage -= minus[1]
        m[i][1] -= tdamage
        if m[i][1] > 0:
            res += m[i][1]
            tdamage += m[i][1]
            q.append([m[i][2],m[i][1]])
    print(res)
main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort()
x=[];h=[]
for xi,hi in XH:
    x.append(xi); h.append(hi)
x.append(inf); h.append(0)
data=[0]*(n+1)
for  i in range(n):
    xi=x[i]; hi=h[i]
    hi-=data[i]
    K=max(0,(A+hi-1)//A); count += K
    data[i]+=K*A
    data[bisect.bisect_left(x,xi+2*D+1)]-=K*A
    data[i+1]+=data[i]
print(count)

Solution (Python):
from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)

Solution (Python):
import sys
from bisect import bisect
from operator import itemgetter
def main():
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Solution (Python):
import queue
import math
n, d, a = map(int, input().split())
xh = list(list(map(int, input().split())) for _ in range(n))

xh.sort(key=lambda x: x[0])
d = d * 2
total = 0
q = queue.Queue()
ans = 0
for i in range(n):
    while(not q.empty() and q.queue[0][0] < xh[i][0]):
        total -= q.queue[0][1]
        q.get()
    h = xh[i][1] - total
    if h > 0:
        c = math.ceil(h/a)
        ans += c
        damage = c * a
        total += damage
        q.put((xh[i][0]+d, damage))

print(ans)

Solution (Python):
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    d*=2
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d)]+=t*a
        s-=t
    print(s)
main()

Solution (Python):
import bisect

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

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])


xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]


bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]

for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,d,a = LI()
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,h in xh]
que = deque()
for i,[x,h] in enumerate(xh):
    r = br(X,x+2*d)
    que.append((h,i,r))

ans = 0
lst = [0]*(n+1)
while que:
    h,l,r = que.popleft()
    tmp = max(0,math.ceil((h - lst[l])/a))
    ans += tmp
    lst[l] += tmp*a
    lst[r] -= tmp*a
    lst[l+1] += lst[l]
print(ans)

Solution (Python):
def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):c[i]+=c[i-1];h-=c[i];t=min(-h//a,0);c[i]-=t*a;c[bisect(z,(x+d+d,9e9))]+=t*a;s-=t
print(s)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bomb_area = deque([])
bomb_power = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bomb_area:
        area = bomb_area[0]
        if area < pos:
            bomb_area.popleft()
            power = bomb_power.popleft()
            total_damage -= power
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        power = a * count
        total_damage += power
        bomb_area.append(pos+2*d)
        bomb_power.append(power)

print(ans)

Solution (Python):
from collections import deque


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bomb_area = deque([])
bomb_power = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bomb_area:
        area = bomb_area[0]
        if area < pos:
            bomb_area.popleft()
            power = bomb_power.popleft()
            total_damage -= power
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        power = a * count
        total_damage += power
        bomb_area.append(pos+2*d)
        bomb_power.append(power)

print(ans)

Solution (Python):
from collections import deque


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bombs = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bombs:
        area, count = bombs[0]
        if area < pos:
            bombs.popleft()
            total_damage -= a * count
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        total_damage += a * count
        bombs.append([pos + 2*d, count])

print(ans)

Solution (Python):
import sys
from bisect import bisect_right
from operator import itemgetter

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
XH = sorted(zip(*[iter(XH)] * 2), key=itemgetter(0))
D *= 2
X = [i for i, _ in XH]

damages = [0] * (N + 2)
answer = 0

for i, (x, h) in enumerate(XH, 1):
    damages[i] += damages[i - 1]
    if damages[i] >= h:
        continue

    h -= damages[i]
    cnt = (h + A - 1) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D) + 1] -= damage

print(answer)

Solution (Python):
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    M=10**9
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,(x+d+d,M))]+=t*a
        s-=t
    print(s)
main()

Solution (Python):
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,9e9))]+=t*a
    s-=t
print(s)

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,10e9))]+=t*a
    s-=t
print(s)

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=-min(-h//a,0)
    c[i]+=t*a
    c[bisect(z,(x+d+d,10e9))]-=t*a
    s+=t
print(s)

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=0--max(0,h)//a
    c[i]+=t*a
    c[bisect(z,(x+d+d,10e9))]-=t*a
    s+=t
print(s)

Solution (Python):
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=0--max(0,h)//a
    c[i]+=t*a
    c[bisect(y,x+d+d)]-=t*a
    s+=t
print(s)

Solution (Python):
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, D, A = map(int, input().split())
    M = [tuple(int(m) for m in input().split()) for _ in range(N)]
    M.sort()
    
    HP = [0] * (N + 2)
    count = 0
    for i, m in enumerate(M):
        HP[i + 1] += HP[i]
        
        x, h = m
        right = x + 2 * D
        if HP[i + 1] < h:
            add = (h - HP[i + 1]) // A
            if (h - HP[i + 1]) % A > 0: add += 1
            small, large = i, N
            while large - small > 1:
                mid = (small + large) // 2
                if M[mid][0] > right: large = mid
                else: small = mid
            HP[i + 1] += add * A
            HP[small + 2] -= add * A
            count += add
    
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, D, A = map(int, input().split())
    M = [tuple(int(m) for m in input().split()) for _ in range(N)]
    M.sort()
    
    HP = [0] * (N + 2)
    count = 0
    for i, m in enumerate(M):
        HP[i + 1] += HP[i]
        
        x, h = m
        right = x + 2 * D
        if HP[i + 1] < h:
            add = (h - HP[i + 1]) // A
            if (h - HP[i + 1]) % A > 0: add += 1
            small, large = i, N
            while large - small > 1:
                mid = (small + large) // 2
                if M[mid][0] > right: large = mid
                else: small = mid
            HP[i + 1] += add * A
            HP[small + 2] -= add * A
            count += add
    
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import math
import bisect
import sys
input = sys.stdin.readline

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

XH=[[0,0] for _ in range(N)]
for i in range(N):
    x,h=map(int,input().split())
    XH[i][0]=x
    XH[i][1]=h
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]



ans=0
S=[0]*(N+1)


for i in range(N):
    if S[i]<XH[i][1]:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        num=(XH[i][1]-S[i])//A
        if (XH[i][1]-S[i])%A!=0:
            num+=1
        ans+=num
        dam=num*A
        
        S[Lb]+=dam
        S[Rb]-=dam
    S[i+1]+=S[i]
        
print(ans)

Solution (Python):
N,D,A=map(int,input().split())
D*=2 
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] 
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
        if X[i][1]<=0:
          break
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)

Solution (Python):
N,D,A=map(int,input().split())
D*=2 
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] 
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
        if X[i][1]<=0:
          break
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)