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):
from collections import deque

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

ans = 0
dam_sum = 0
q = deque()
for i, (x, h) in enumerate(xh):
    while q and q[0][0] < x:
        ran, dam = q.popleft()
        dam_sum -= dam
    h -= dam_sum
    if h <= 0:
        continue 
    c = -(-h//a)
    ans += c
    dam_sum += c*a
    q.append((x+d*2, c*a))
print(ans)

Solution (Python):
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [0] * (n + 1)
h = [0] * (n + 1)
s = [0] * (n + 1)

for i, (f, g) in enumerate(xh):
    x[i], h[i] = f, g
x[n] = 10 ** 10 + 1
ans = 0
for i in range(n):
    if i > 0:
        s[i] += s[i - 1]
    h[i] -= s[i]
    if h[i] > 0:
        num = 0 - - h[i] // a
        ans += num
        s[i] += num * a

        j = bisect_right(x, x[i] + d * 2)
        s[j] -= num * a
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        while len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import math

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

for _ in range(n):
    x, h = map(int, input().split())
    xh.append((x, h))
xh.sort(key=lambda x: x[0])
xs = [x[0] for x in xh]

ranges = []
for x in xs:
    ranges.append(bisect.bisect_right(xs, x + 2 * d))



N = n
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

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


for i, (x, h) in enumerate(xh):
    update(i, i + 1, h)

ans = 0
for i in range(n):
    v = query(i, i + 1)
    if v > 0:
        t = math.ceil(v / a)
        ans += t
        update(i, ranges[i], -t * a)
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
左から見る，モンスターが生きているならそいつが左端ギリギリになる位置に爆弾投下
区間減算，座圧
"""
def main():
    
    import sys
    class Lazysegtree():
        


        """RAQ
        外から使うのは，query，add,updateくらいか

        """
        def __init__(self, A, intv, initialize = True, segf = min):
            """
            Aが初期配列，intvが単位元,segfが評価関数
            """

            
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.intv = intv
            self.segf = segf
            self.lazy = [0]*(2*self.N0)
            if initialize:
                self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [intv]*(2*self.N0)

        def _ascend(self, k):
            k = k >> 1
            c = k.bit_length()
            for j in range(c):
                idx = k >> j
                self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
                + self.lazy[idx]

        def _descend(self, k):
            k = k >> 1
            idx = 1
            c = k.bit_length()
            for j in range(1, c+1):
                idx = k >> (c - j)
                ax = self.lazy[idx]
                if not ax:
                    continue
                self.lazy[idx] = 0
                self.data[2*idx] += ax
                self.data[2*idx+1] += ax
                self.lazy[2*idx] += ax
                self.lazy[2*idx+1] += ax

        def update(self, k, x):
            
            k = k + self.N0
            self.data[k] = x
            self._ascend(k)

        def query(self, l, r):
            
            L = l+self.N0
            R = r+self.N0
            Li = L//(L & -L)
            Ri = R//(R & -R)
            self._descend(Li)
            self._descend(Ri - 1)

            s = self.intv 
            t = self.intv 
            while L < R:
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        def add(self, l, r, x):
            
            L = l+self.N0
            R = r+self.N0

            Li = L//(L & -L)
            Ri = R//(R & -R)

            while L < R :
                if R & 1:
                    R -= 1
                    self.data[R] += x
                    self.lazy[R] += x
                if L & 1:
                    self.data[L] += x
                    self.lazy[L] += x
                    L += 1
                L >>= 1
                R >>= 1

            self._ascend(Li)
            self._ascend(Ri-1)

        


    




    import bisect
    
    N,D,A=MI()
    X=[0]*N
    H=[0]*N
    for i in range(N):
        X[i],H[i]=MI()
    
    X,H=zip(*sorted(zip(X,H)))
    
    from collections import defaultdict
    dd = defaultdict(int)

    for i in range(N):
        dd[X[i]]=i
        
    ans=0
    inf=10**10
    seg=Lazysegtree(list(H),inf,segf=min)
    for i in range(N):
        h=seg.query(i,i+1)
        
        if h>0:
            cnt=(h+A-1)//A
            ans+=cnt
            l=i
            t=X[l]+2*D
            r=bisect.bisect_right(X,t)
            
            seg.add(l,r,-1*cnt*A)
            
    print(ans)
        
    
        
    

main()

Solution (Python):
"""
lazyseg使う方法とかもあるが、imos法使うのが簡単そう。
座標圧縮は必須。
"""
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()

coordinates = set()
for x,h in XH:
    coordinates.add(x)
    coordinates.add(x+2*D+1)

compress = {x:i for i,x in enumerate(sorted(coordinates))}

imos = [0]*(len(compress))
damage = 0
cur = 0
ans = 0
for x,h in XH:
    compX = compress[x]
    while cur <= compX:
        damage += imos[cur]
        cur += 1
    rest = h-damage
    if rest > 0:
        add = A*ceil(rest/A)
        ans += int(ceil(rest/A))
        imos[cur] += add
        right = compress[x+2*D+1]
        imos[right] -= add
print(ans)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        
        
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        
        
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        
        
        return self.bit1._sum(i)*i + self.bit2._sum(i)

import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():
    n, d, a = map(int, input().split())
    XH = []
    for i in range(n):
        x, h = map(int, input().split())
        XH.append((x-d, h))
    XH.sort()
    X = []
    H = []
    for x, h in XH:
        X.append(x)
        H.append(h)

    bit = RangeAddBIT(n+1)
    bit.init(H)
    import bisect
    ans = 0
    for i in range(n):
        h = bit.sum(i, i+1)
        if h > 0:
            q = (h+a-1)//a
            ans += q
            j = bisect.bisect_right(X, X[i]+2*d)
            bit.add(i, j, -q*a)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        
        
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        
        
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        
        
        return self.bit1._sum(i)*i + self.bit2._sum(i)

import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x-d, h))
XH.sort()
X = []
H = []
for x, h in XH:
    X.append(x)
    H.append(h)

bit = RangeAddBIT(n+1)
bit.init(H)
import bisect
ans = 0
for i in range(n):
    h = bit.sum(i, i+1)
    if h > 0:
        q = (h+a-1)//a
        ans += q
        j = bisect.bisect_right(X, X[i]+2*d)
        bit.add(i, j, -q*a)
print(ans)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from heapq import *

def main():
	n,d,a=MI()
	Q=[]
	heapify(Q)
	for _ in range(n):
		x=LI()
		heappush(Q,x)

	ans=0
	now=0
	li=[[10**10,0]]
	heapify(li)
	while Q:
		
		if Q[0][0]<li[0][0]:
			x,h=heappop(Q)
			if h-now>0:
				k=(h-now-1)//a+1
				ans+=k
				now+=k*a
				heappush(li,[x+2*d+1,-k*a])
		else:
			x,h=heappop(li)
			now+=h
	print(ans)
















if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque

N, D, A = map(int, input().split())
Monsters = [tuple(map(int, input().split())) for _ in range(N)]
Monsters.sort()
Attack = deque()
attack = 0
ans = 0
for x, h in Monsters:
    while Attack and Attack[0][0] <= x:
        y, at = Attack.popleft()
        attack -= at
    h -= attack
    num = max((h - 1) // A + 1, 0)
    attack += num * A
    ans += num
    Attack.append((x + 2 * D + 1, num * A))
print(ans)

Solution (Python):
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
from math import ceil
times = ceil(XH[0][1]/A)
ans = times
damege = [times*A]
coor = [XH[0][0]+2*D]
start = 0
end = 1
dam = sum(damege[start:end])
for i in range(1,N):
    st = start
    while start < end and coor[start] < XH[i][0]:
        start += 1
    dam -= sum(damege[st:start])
    H = XH[i][1] - dam
    if H > 0:
        times = ceil(H/A)
        ans += times
        damege.append(times*A)
        dam += times*A
        coor.append(XH[i][0]+2*D)
        end += 1
print(ans)

Solution (Python):




from collections import deque

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

XH = sorted(XH)
que=deque()
cum = 0
ans = 0
for i in range(N):
  x,h = XH[i]
  if i == 0:
    r,n = x+2*D,(h+A-1)//A
    d = n*A
    cum += d
    que.append((r,d))
    ans += n
    continue
  while que and que[0][0]<x:
    r,d = que.popleft()
    cum -= d
  h -= cum
  if h<0:
    continue
  r,n = x+2*D,(h+A-1)//A
  d = n*A
  cum += d
  que.append((r,d))
  ans += n
  
print(ans)

Solution (Python):
"""

普通に端っこを基準にして、貪欲的に爆弾をおいていく方法を考えるのがよさそう。
座標圧縮したうえで、遅延セグ木で各座標に蓄積しているダメージを管理しておけばよい。
一番左端のやつの体力を削れるだけの爆弾を設置してみる:O(1)
次の左端になるモンスターの位置(体力が1以上あるモンスターのなかで一番左端のやつの座標)を探す。これはO(logN)かかる。
このサイクルをモンスターが全滅するまで行うので、O(N)サイクル回す。したがって全体でO(NlogN)
"""
from math import ceil
class lazySegTree:
    def __init__(self,n):
        self.end_leave = 2**(n.bit_length()+1)
        self.tree = [0]*(2*self.end_leave)
        self.lazy = [0]*(2*self.end_leave)

    def gindex(self,left,right):
        
        left = left + self.end_leave
        right = right + self.end_leave
        left >>= 1
        while left:
            yield left
            left >>= 1

        right >>= 1
        while right:
            yield right
            right >>= 1

    def add(self,left,right,x):
        L = left + self.end_leave
        R = right + self.end_leave
        while L < R:
            if L&1:
                self.lazy[L] += x
                self.tree[L] += x
                L += 1
            if R&1:
                R -= 1
                self.lazy[R] += x
                self.tree[R] += x
            L >>= 1
            R >>= 1
        for i in self.gindex(left,right):
            self.tree[i] = max(self.tree[i*2],self.tree[i*2+1])+self.lazy[i]
    
    def propagates(self,*ids):
        for i in reversed(ids):
            self.lazy[i*2] += self.lazy[i]
            self.lazy[i*2+1] += self.lazy[i]
            self.tree[i*2] += self.lazy[i]
            self.tree[i*2+1] += self.lazy[i]
            self.lazy[i] = 0

    def get(self,left,right):
        self.propagates(*self.gindex(left,right))
        L = left + self.end_leave
        R = right + self.end_leave
        res = 0
        while L < R:
            if L&1:
                res = max(res,self.tree[L])
                L += 1
            if R&1:
                R -= 1
                res = max(res,self.tree[R])
            L >>= 1
            R >>= 1
        return res
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
compSet = []
for x,h in XH:
    compSet.append(x)
    compSet.append(x+2*D)
compSet.sort()
compSet = sorted(set(compSet))
compDic = {x:i for i,x in enumerate(compSet)}

LST = lazySegTree(len(compDic))
ans = 0
for x,h in XH:
    compX = compDic[x]
    h -= LST.get(compX,compX+1)
    if h > 0:
        bomb = ceil(h/A)
        ans += bomb
        damage = bomb*A
        compRight = compDic[x+2*D]
        LST.add(compX,compRight+1,damage)
print(ans)

Solution (Python):
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

print(ans)

Solution (Python):

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    N, D, A = map(int, input().split())
    mlist = []
    for _ in range(N):
        x, h = map(int, input().split())
        mlist.append([x, (h+A-1)//A])
    mlist.sort(key=lambda x: x[0])
    db = deque()
    dnotb = deque()
    left = mlist[0][0]
    ans = 0
    for monster in mlist:
        if monster[0] <= left+2*D:
            db.append(monster)
        else:
            dnotb.append(monster)
    ans = 0
    while db or dnotb:
        if not db:
            monster = dnotb.popleft()
            monster[1] += ans
            db.append(monster)
        bmonster = db.popleft()
        while dnotb:
            if dnotb[0][0] <= bmonster[0]+2*D:
                monster = dnotb.popleft()
                monster[1] += ans
                db.append(monster)
            else:
                break
        ans = max(ans, bmonster[1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def zaatsu(nums):
    ref = list(set(copy.copy(nums)))
    ref.sort()
    dic = dict()
    for i, num in enumerate(ref):
        dic[num] = i

    return [dic[num] for num in nums]

def solve():
    n, d, a = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort()
    ichi = [x[0] for x in li]
    imos = [0] * n
    cur = 0
    ans = 0
    for i, (x, h) in enumerate(li):
        cur -= imos[i]
        hp = h - cur * a
        if hp <= 0:
            continue
        thr = hp // a
        if hp % a != 0:
            thr += 1
        ans += thr
        cur += thr
        owari = bisect_right(ichi, x + 2 * d)
        if owari != n:
            imos[owari] += thr

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())


def is_ok(arg):
    return h[arg][0] <= h[i][0] + d*2

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n, d, a = MAP()
h = [LIST() + [0] for i in range(n)]
h = sorted(h, key=itemgetter(0))
attack = 0

ans = 0
for i in range(n):
    bomb = ceil( (h[i][1] - attack) / a )
    if bomb > 0:
        j = min(meguru_bisect(n, i), n-1)
        h[j][2] -= bomb
        attack += bomb*a
        ans += bomb
    attack += h[i][2]*a

print(ans)

Solution (Python):
import sys
import math
from collections import deque


def bisect(ng, ok, x, q):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if q[mid][0] >= x:
            ok = mid
        else:
            ng = mid
    return ok


def solve_greedy(N, D, A, XH):
    ret = 0
    q = deque([(0, 0)])
    for i, (x, h) in enumerate(XH):
        if q[-1][0] < x:
            damaged = 0
        else:
            i = bisect(0, len(q) - 1, x, q)
            damaged = q[-1][1] - q[i - 1][1]
            
        if h <= damaged:
            continue
        tmp = math.ceil((h - damaged) / A)
        ret += tmp
        q.append((x + 2 * D, A * tmp + q[-1][1]))
    return ret


input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[0])
ans = solve_greedy(N, D, A, XH)
print(ans)

Solution (Python):

N,D,A = map(int,input().split())
XH = [0]*N
for i in range(N):
    X,H = map(int,input().split())
    XH[i] = (X,(H-1)//A+1)
XH = sorted(XH, key=lambda x:x[0])
X = [xh[0] for xh in XH]
M = [XH[0][1]]+[XH[i][1]-XH[i-1][1] for i in range(1,N)]
Y = [0]*N
r = 0
for l in range(N):
    r = max(r,l+1)
    while r<N and X[r]<=X[l]+2*D:
        r += 1
    Y[l] = r-1
ans = 0
tmp = 0
for i in range(N):
    tmp += M[i]
    if tmp>0:
        ans += tmp
        r = Y[i]+1
        if r<N:
            M[r] += tmp
        tmp = 0
print(ans)

Solution (Python):
from bisect import bisect
from collections import defaultdict

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

for _ in range(N):
  X, H = map(int, input().split())
  XH.append((X, -(-H//A)))

XH.sort()
Xs = [ xh[0] for xh in XH ]
HP = [ xh[1] for xh in XH ]

XR = []
for x in Xs:
  XR.append(bisect(Xs, x+2*D))

cnt = 0
temp = 0
D = defaultdict(int)

for i in range(N):
  temp -= D[i]
  HP[i] -= temp
  if HP[i] > 0:
    temp += HP[i]
    cnt += HP[i]
    D[XR[i]] += HP[i]
    HP[i] -= temp

print(cnt)

Solution (Python):
from bisect import bisect
from collections import defaultdict

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

for _ in range(N):
  X, H = map(int, input().split())
  XH.append((X, -(-H//A)))

XH.sort()
Xs = [ xh[0] for xh in XH ]
HP = [ xh[1] for xh in XH ]

XR = []
for x in Xs:
  XR.append(bisect(Xs, x+2*D))

cnt = 0
temp = 0
D = defaultdict(int)

for i in range(N):
  temp -= D[i]
  HP[i] -= temp
  if HP[i] > 0:
    temp += HP[i]
    cnt += HP[i]
    D[XR[i]] += HP[i]
    HP[i] -= temp

print(cnt)

Solution (Python):



from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)

Solution (Python):
n, d, a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(n)])
ret = 0
surface = 0
dec = []
j = 0
for i in range(n):
    x, h = xh[i]
    while j < len(dec) and dec[j][0] < x:
        surface -= dec[j][1]
        j += 1
    h = (h + a - 1) // a - surface
    if h > 0:
        dec.append((x + 2 * d, h))
        ret += h
        surface += h
print(ret)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_table(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

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

    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i = max(i, 1)
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    
    def get(self, l, r=None):
        if r is None: r = l
        return self.sum(r) - self.sum(l-1)

class ExBIT:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    
    def add(self, x, l, r=None):
        if r is None: r = l
        r += 1
        self.p.add(l, -x * l)
        self.p.add(r, x * r)
        self.q.add(l, x)
        self.q.add(r, -x)

    def sum(self, l, r):
        r += 1
        return self.p.sum(r) + self.q.sum(r) * r - self.p.sum(l) - self.q.sum(l) * l

    def get(self, l, r=None):
        if r is None: r = l
        return self.sum(l, r)

def main():
    N, D, A = LI()
    XH = sorted(LIR(N), key=lambda x: x[0])
    X = [xi for xi, _ in XH]
    bit = ExBIT(N)

    for i in range(N):
        _, hi = XH[i]
        bit.add(math.ceil(hi / A), i)

    ans = 0

    for i, (xi, hi) in enumerate(XH):
        right = bisect_right(X, xi + 2 * D) - 1
        cnt = bit.get(i)
        if cnt > 0:
            bit.add(-cnt, i, right)
            ans += cnt

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
from collections import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
ans=0
tot=0
q=deque()
for i in range(n):
  x,h=mon[i]
  while q and q[0][0]<x:
    tot-=q.popleft()[1]
  h-=tot
  if h>0:
    b=(h+a-1)//a
    tot+=b*a
    ans+=b
    q.append((x+2*d,b*a))
print(ans)

Solution (Python):
import bisect
import math
N, D, A = map(int, input().split())
cusum = [0] * (N+1)
X = []
XH =[]
for i in range(N):
    xi, hi = map(int, input().split())
    X += [xi]
    XH += [(xi, hi)]
X = sorted(X)
XH = sorted(XH)
cusumD = 0
ans = 0
for i, (xi, hi) in enumerate(XH):
    cusumD -= cusum[i]
    hi = max(0, hi-cusumD)
    r = bisect.bisect_right(X, xi+2*D)
    b = int(math.ceil(hi/A))
    d = b * A
    ans += b
    cusumD += d
    cusum[r] += d
    
print(ans)

Solution (Python):

def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
from collections import deque
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for i in range(n)]
xh.sort()
queue = deque()
ans = 0
cur = 0
for i in range(n):
    x, h = xh[i]
    while queue != deque() and queue[0][0] < x:
        cur -= queue.popleft()[1]
    h -= cur
    if h > 0:
        cur += a * ((h - 1) // a + 1)
        ans += (h - 1) // a + 1
        queue.append([x + 2 * d, a * ((h - 1) // a + 1)])
print(ans)