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
input = sys.stdin.readline


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

fox.sort()

sub = [0]*(n+1)

def bisect(x):
    l, r = 0, n
    while r-l > 1:
        k = (r+l)//2
        if fox[k][0] <= x:
            l = k
        else:
            r = k
    if fox[l][0] <= x:
        return l
    return r


def main():
    ans = 0
    
    for i in range(n):
        if i != 0:
            sub[i] += sub[i-1]
        if fox[i][1]-a*sub[i] <= 0:
            continue
        count = (fox[i][1]-sub[i]*a-1)//a+1
        ans += count
        sub[i] += count
        sub[bisect(fox[i][0]+2*d)+1] -= count

    print(ans)

    
if __name__ == "__main__":
    main()

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


def resolve(in_):
    N, D, A = map(int, next(in_).split())
    def f(line):
        x, h = map(int, line.split())
        return x, (h + A - 1) // A
    XH = list(map(f, islice(in_, N)))
    XH.sort(key=itemgetter(0))
    assert N == len(XH)

    bomb_attack = deque()
    bomb = 0
    ans = 0
    for x, h in XH:
        while bomb_attack and bomb_attack[0][0] < x:
            e = bomb_attack.popleft()
            bomb -= e[1]

        h_real = h - bomb
        if h_real <= 0:
            continue
        ans += h_real
        bomb_attack.append((x + D * 2, h_real))
        bomb += h_real

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()

q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)

Solution (Python):
from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)

Solution (Python):
from collections import deque
import math

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





ans = 0

total_damage = 0

dq = deque()


for x, h in XH:
    
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    
    if total_damage < h:
        
        h -= total_damage
        
        cnt = math.ceil(h / A)
        ans += cnt
        
        dmg = cnt * A
        total_damage += dmg
        
        dq.append((dmg, x + D * 2))

print(ans)

Solution (Python):
from collections import deque
import math

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





ans = 0

total_damage = 0

dq = deque()


for x, h in XH:
    
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    
    if total_damage < h:
        
        h -= total_damage
        
        cnt = math.ceil(h / A)
        ans += cnt
        
        dmg = cnt * A
        total_damage += dmg
        
        dq.append((dmg, x + D * 2))

print(ans)

Solution (Python):
from collections import deque
import math

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





ans = 0

total_damage = 0

dq = deque()


for x, h in XH:
    
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    
    if total_damage < h:
        
        h -= total_damage
        
        
        cnt = (h + A - 1) // A
        ans += cnt
        
        dmg = cnt * A
        total_damage += dmg
        
        dq.append((dmg, x + D * 2))

print(ans)

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

Solution (Python):
from collections import deque
import math
n,d,a = map(int,input().split())
F = []
for _ in range(n):
    x,h = map(int,input().split())
    F.append((x,h))
F.sort()
total = 0
d *=2
ans = 0
q = deque([])
for x,h in F:
    while q and q[0][0]<x:
        total -= q.popleft()[1]
    h-=total
    if h >0:
        tmp = math.ceil(h/a)
        ans += tmp
        damage = tmp*a
        total += damage
        q.append((x+d,damage))
print(ans)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np

def solve(N, D, A, XH):
    q = []
    idx_q = 0
    I = XH[:, 0].argsort()
    XH = XH[I]
    XH[:, 1] = -(-XH[:, 1]//A)
    d = 0
    ans = 0
    for i in range(N):
        x, h = XH[i]
        while idx_q < len(q) and q[idx_q][0] <= x:
            d -= q[idx_q][1]
            idx_q += 1
        if d < h:
            q.append((x + D*2+1, h-d))
            ans += h-d
            d = h
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8[:,:])"],
])

import sys
def main():
    N, D, A = map(int, input().split())
    XH = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N, 2)
    ans = solve(N, D, A, XH)
    print(ans)

main()

Solution (Python):
from random import random
class Node:
        def __init__(self, key, value:int=-1):
            self.left = None
            self.right = None
            self.key = key
            self.value = value
            self.priority = int(random()*10**7)
            
            self.sum_partial = value

 

class Treap:
    
    
    def __init__(self):
        self.root = None

    def update(self, node) -> Node:
        if node.left is None:
            
            left_sum = 0
        else:
            
            left_sum = node.left.sum_partial
        if node.right is None:
            
            right_sum = 0
        else:
            
            right_sum = node.right.sum_partial

        
        node.sum_partial = left_sum  + node.value + right_sum
        return node

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            return self.update(left)
        else:
            right.left = self.merge(left,right.left)
            return self.update(right)


    
    
    
    def node_key(self, node: Node) -> int:
        return -1 if node is None or node.key is None else node.key
    
    def node_sum(self, node: Node) -> int:
        return 0 if node is None else node.sum_partial

    
    def split(self, node:None, key:int) -> (Node, Node):
        if node is None:
            return None,None
        if key <= self.node_key(node):
            left,right = self.split(node.left, key)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, key)
            node.right = left
            return self.update(node),right

    
    def insert(self, key:int, value:int =-1):
        value = value if value > 0 else key
        left, right = self.split(self.root, key)
        new_node = Node(key,value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, key:int):
        
        middle,right = self.split(self.root, key+1)
        
        left,middle = self.split(middle, key)
        
        self.root = self.merge(left,right)


    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'k=',node.key,'v=',node.value, 'p=',node.priority)
        if node.left is not None:
            print('left')
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            print('right')
            self.printTree(node.right,level+1)
        
    

    def find(self, key):
        
        v = self.root
        while v:
            v_key = self.node_key(v)
            if key == v_key:
                return v.value
            elif key < v_key:
                v = v.left
            else:
                v = v.right
        return -1
    def interval_sum(self, left_key, right_key):
        lt_left, ge_left = self.split(self.root,left_key)
        left_to_right, gt_right = self.split(ge_left, right_key + 1)
        res = self.node_sum(left_to_right)
        self.root = self.merge(lt_left, self.merge(left_to_right, gt_right))
        return res



def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,D,A = LMIIS()
    enemies = []
    for i in range(N):
        x, h = LMIIS()
        enemies.append((x, ceil(h/A)))
    enemies.sort()
    bomb = Treap()
    ans = 0
    for i, (x, h) in enumerate(enemies):
        left = x - D
        right = x + D
        remain_h = h - bomb.interval_sum(left, right)
        if remain_h <= 0:
            continue

        ans += remain_h
        bomb.insert(x + D, remain_h)
    print(ans)
        





    
main()

Solution (Python):
from collections import deque

dq = deque()

(n,d,a),*xh = [list(map(int, s.split())) for s in open(0)]
xh.sort()

total_bomb = 0
eff_bomb = 0

for x,h in xh:
    while dq and dq[0][0] < x:
        end, cnt = dq.popleft()
        eff_bomb -= cnt
    resid = h - eff_bomb * a
    if resid > 0:
        cnt = 0--resid//a
        end = x + 2 * d
        dq.append((end,cnt))
        eff_bomb += cnt
        total_bomb += cnt

print(total_bomb)

Solution (Python):
import bisect
from math import ceil
class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i += i & -i
 
    def find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1

n,d,a = map(int,input().split())
monster = sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])
x_list = [0]+[monster[i][0] for i in range(n)]+[float("inf")]
h_list = [0]+[monster[i][1] for i in range(n)]+[float("inf")]

bit = BinaryIndexedTree(n+2)
ans = 0
for i in range(1,n+1):
    hp = h_list[i] - bit.get_sum(i)
    if hp < 0:
        continue
    atk_time = ceil(hp/a)
    ans += atk_time
    top = bisect.bisect_right(x_list, x_list[i]+2*d)
    bit.add(i, atk_time*a)
    bit.add(top, -atk_time*a)

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, D, A = MAP()
XH = [LIST() for _ in range(N)]

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

X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

ans = 0
imos = [0]*(N+1)
tmp = 0
for i in range(N):
	x, h = XH[i]
	tmp += imos[i]
	left = h-tmp
	if 0 < left:
		cnt = -(-left//A)
		damage = A*cnt
		idx = bisect(X, x+2*D)
		tmp += damage
		imos[idx] -= damage
		ans += cnt

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, D, A = MAP()
XH = [LIST() for _ in range(N)]

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

X, H = zip(*XH)
right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

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

for i, (X, H) in enumerate(XH):
	if i != 0:
		damage[i] += damage[i-1]
	H -= damage[i]
	if 0 < H:
		n = -(-H//A)
		ans += n
		d = A*n
		damage[i] += d
		damage[right[i]] -= d
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, D, A = MAP()
XH = [LIST() for _ in range(N)]

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

X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

ans = 0
imos = [0]*(N+1)
tmp = 0
for i in range(N):
	x, h = XH[i]
	tmp += imos[i]
	left = h-tmp
	if 0 < left:
		cnt = -(-left//A)
		damage = A*cnt
		idx = bisect(X, x+2*D)
		tmp += damage
		imos[idx] -= damage
		ans += cnt

print(ans)

Solution (Python):
from collections import deque 
import math
n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key = lambda x:x[0])
cnt = 0
queue = deque()
sum_bomb = 0
for i in range(n):
    while len(queue) != 0 and queue[0][0]<l[i][0]:
        sum_bomb -= queue[0][1] * a
        queue.popleft()
    l[i][1] -= sum_bomb
    if l[i][1] <= 0 :
        continue
    num = math.ceil(l[i][1]/a)
    right = l[i][0] + 2 * d
    queue.append([right, num])
    cnt += num
    sum_bomb += num * a
print(cnt)

Solution (Python):

from bisect import bisect_right

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

X.sort()
place = []
hps = []
for x, h in X:
    place.append(x)
    hps.append(h)

buf = [0] * (N + 2)
ans = 0
for i in range(N):
    
    buf[i + 1] += buf[i]

    
    tmp = -(-max(0, hps[i] - buf[i + 1] * A) // A)
    ans += tmp

    
    j = bisect_right(place, place[i] + D * 2)
    buf[i + 1] += tmp
    buf[min(j + 1, N + 1)] -= tmp

print(ans)

Solution (Python):
N, D, A = map(int, input().split())
X = [0] * N
for i in range(N):
    x, h = map(int, input().split())
    X[i] = (x, h)
X = sorted(X)

from collections import deque

q = deque()

ans = 0
total = 0
for i in range(N):
    x, h = X[i]
    while (len(q) > 0 and q[0][0] < x):
        total -= q[0][1] 
        q.popleft()
    h -= total
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        total += damage
        q.append((x + 2 * D, damage))
print(ans)

Solution (Python):
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)

Solution (Python):
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind

cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
        monstershp[i]=monstershp[i]-A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    
print(cnt)

Solution (Python):
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind

cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    
print(cnt)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






def segfunc(x, y):
    return min(x, y)



ide_ele = 2**31 - 1


class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    add(l, r, x): 区間[l, r)にxを加算 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if not v:
                continue
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.data[2 * i] += v
            self.data[2 * i + 1] += v
            self.lazy[i] = 0

    def add(self, l, r, x):
        """
        区間[l, r)の値にxを加算
        l, r: index(0-index)
        x: additional value
        """
        *ids, = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.data[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.data[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

def or_less(array, x):
    
    
    index = bisect_right(array, x)
    if index == 0:
        or_less_int = -float('inf')
    else:
        or_less_int = array[index - 1]
    return index - 1

N, D, A = getNM()
que = [getList() for i in range(N)]
que.sort()

HP = [i[1] for i in que]
dis = [i[0] for i in que]

seg = LazySegmentTree([0] * (N + 1), segfunc, ide_ele)

now = 0

now_dis = dis[now]

ans = 0
while now < N:
    
    range = or_less(dis, now_dis + 2 * D)
    left_hp = HP[now] - seg.query(now, now + 1)
    
    explo = (left_hp + A - 1) // A
    seg.add(now, range + 1, explo * A)
    ans += explo

    while True:
        if now >= N or seg.query(now, now + 1) < HP[now]:
            break
        now += 1
    if now < N:
        now_dis = dis[now]

print(ans)

Solution (Python):
from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
monster = deque(monster)
final = monster[-1][0]
ruiseki = 0
minuslist = deque()

while len(monster) > 0:
  while len(minuslist) > 0:
    if monster[0][0] >= minuslist[0][0]:
      ruiseki -= minuslist[0][1]
      minuslist.popleft()
    else:
      break
  if ruiseki < monster[0][1]:
    ans += monster[0][1] - ruiseki
    if monster[0][0] + 2*D +1 <= final:
      minuslist.append([monster[0][0]+2*D+1, monster[0][1] - ruiseki])
    ruiseki = monster[0][1]
  monster.popleft()

print(ans)

Solution (Python):
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0

final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


print(ans)

Solution (Python):
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
"""
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = monster[k][1]
    ans += monster[k][1]
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk
"""
final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)])

    res = 0
    tt_dmg = 0
    que = deque()
    for x, h in XH:
        while que and que[0][1] < x:
            dmg, rng = que.popleft()
            tt_dmg -= dmg

        if tt_dmg < h:
            h -= tt_dmg
            cnt = (h + a - 1) // a
            res += cnt
            dmg = cnt * a
            tt_dmg += dmg
            que.append((dmg, x + d * 2))

    print(res)


if __name__ == '__main__':
    resolve()

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