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
fastinput = sys.stdin.readline
N,D,A = [int(i) for i in fastinput().split()]
preXH = [[int(i) for i in fastinput().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
X = [x for x,h in XH]+[100000000000000000]
Diff = [X[m+1]-X[m] for m in range(N)]
reach = []
count = 0
l = X[0]
r = X[0]+2*D
for m in range(1,N+1):
    while r<X[m]:
        reach.append(m-1)
        r += Diff[count]
        count += 1

damage = 0
ans = 0
DIFF = [0]*N
for n,d in enumerate(DIFF):
    damage += d
    if damage<XH[n][1]:
        bonu = XH[n][1]-damage
        damage += bonu
        ans += bonu
        if reach[n]<N-1:DIFF[reach[n]+1] -= bonu
print(ans)

Solution (Python):
import sys
from bisect import bisect
 
class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size
 
	def Get(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s
 
	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return
 
	def SegAdd(self, l, r, x):
		self.PointAdd(l, x)
		self.PointAdd(r+1, -x)
		return
 
 
n, d, a = map(int, input().split())
d *= 2
mo = sorted([list(map(int, input().split())) for _ in range(n)])
for i in range(n):
	mo[i][1] = (mo[i][1]-1)//a + 1
reach = []
moo = [x[0] for x in mo]
mooo = [x[1] for x in mo]
for x in moo:
	reach.append(bisect(moo, x+d)-1)

 
bit = BIT(n)
 
ans = 0
for i, h in enumerate(mooo):
	gap = max(0, h - bit.Get(i+1))
	bit.SegAdd(i+1, reach[i]+1, gap)
	ans += gap
 
print(ans)

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

from bisect import bisect_right

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

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)

Solution (Python):
N,D,A=map(int,input().split())
XH=[]
inf=float("inf")
for i in range(N):
    X,H=map(int,input().split())
    if H%A==0:
        H//=A
    else:
        H=H//A+1
    XH.append([X,H])
XH.sort()
XH=[[-inf,0]]+XH

L=0
lst=[0]*(N+1)
S=[0]*(N+1)
lst[1]=XH[1][1]
S[1]=lst[1]

for R in range(2,N+1):
    r=XH[R][0]
    l=r-2*D
    while XH[L][0]<l:
        L+=1
    lst[R]=max(0,XH[R][1]-(S[R-1]-S[L-1]))
    S[R]=lst[R]+S[R-1]
    
print(S[-1])

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

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

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)
index = 0
minus = 0
answer = 0

while 1:
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  bi = bisect_right(X, pt)
  minus += ht
  answer += -(-XH[index][1] // A)
  check[bi] += ht

  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
                 
print(answer)

Solution (Python):
import math
import sys
input = sys.stdin.readline
N, D, A = [int(i) for i in input().split()]
Mons = []
for _ in range(N):
    x, h = map(int, input().split())
    Mons.append([x, h, 0])


Mons.sort(key=lambda x: x[0])
ans = 0
idx = 0
d = 0

for i, M in enumerate(Mons):
    x = M[0]+D*2+1
    d -= M[2]
    ac = math.ceil(max(M[1]-d, 0)/A)
    ans += ac
    d += ac*A
    l = i
    r = N
    while l < r-1:
        m = (l+r)//2
        if m >= N:
            break
        elif Mons[m][0] < x:
            l = m
        else:
            r = m
    else:
        if r < N and Mons[r][0] >= x:
            Mons[r][2] += ac*A
print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,d,a = get_nums_l()
lines = sys.stdin.readlines()
monsters = [ tuple(map(int, s.split(" "))) for s in lines ]
monsters.sort(key=lambda m: m[0])

ans = (monsters[0][1] + a - 1)//a
areas = [(monsters[0][0] + 2*d, ans*a)]
sum_ = ans*a
area_cursol = 0
for i in range(1, len(monsters)):
    m = monsters[i]
    x = m[0]
    h = m[1]


    while area_cursol < len(areas) and x > areas[area_cursol][0]:
        sum_ -= areas[area_cursol][1]
        area_cursol += 1

    if sum_ < h:
        
        nokori = h-sum_
        kaisuu = (nokori+a-1)//a
        sum_ += kaisuu*a
        areas.append((x+2*d, kaisuu*a))
        ans += kaisuu

print(ans)

Solution (Python):
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
cum = [0]*N
dam = 0
for i in range(N):
    dam += cum[i]
    H[i] -= dam
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_right(X,x+2*D)
    if i+1 < N:
        cum[i+1] += damage 
    if ind < N:
        cum[ind] -=damage 

print(ans)

Solution (Python):
n,d,a = map(int,input().split())
XH = []
for _ in range(n):
    x,h = map(int,input().split())
    h = (h+a-1)//a
    XH.append([x,h])
ans = 0
XH.sort()
p = 0
j = 0
data = []
for i in range(n):
    while XH[i][0] > XH[j][0] + 2*d:
        p -= data[j]
        j += 1
    p_i = max(XH[i][1]-p,0)
    data.append(p_i)
    ans += p_i
    p += p_i

print(ans)

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

input = sys.stdin.readline

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
q = deque()
ans = 0
dam = 0
for i in range(n):
    
    while len(q) > 0:
        if q[0][0] < xh[i][0]:
            dam -= q[0][1]
            q.popleft()
        else:
            break
    xh[i][1] -= dam
    if xh[i][1] > 0:
        a_num = ceil(xh[i][1] / a)
        xh[i][1] -= a_num * a
        ans += a_num
        dam += a_num * a
        q.append((xh[i][0] + 2*d, a_num * a))
print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (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):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N, D, A = map(int, input().split())

ys = []
for _ in range(N):
    X, H = map(int, input().split())
    ys.append((2*X, -(-H//A)))
    ys.append((2*X+4*D+1, -(-H//A)))

ys = sorted(ys, key=lambda x : x[0])
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, h) in enumerate(ys):
    if y%2:
        d1[y-1-4*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)

Solution (Python):
N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (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):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
L.sort()
X = []
for i in range(N):
    X.append(L[i][0])

import bisect
ans = 0
for i in range(N):
    L[i][1] -= bit.sum(N)-bit.sum(i)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    if j > i:
        bit.add(j, num*A)
    
print(ans)

Solution (Python):
import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

N, D, A = map(int, readline().split())
m = map(int,read().split())
XH = list(zip(m,m))
heapq.heapify(XH)
width = 2*D

ans = 0
while len(XH) != 0:
  xh_min = heapq.heappop(XH)
  
  left = xh_min[0]
  right = left + width
  nAttack = (xh_min[1] + A - 1) // A
  damage = nAttack * A
    
  target = []
  while len(XH) != 0:
    xh = heapq.heappop(XH)
    if xh[0] <= right:
      if xh[1] > damage:
        target.append(xh)
    else:
      heapq.heappush(XH, xh)
      break
  if len(XH) == 0:
    maxH = xh_min[1]
    if len(target):
      maxH = max(xh_min[1], max([t[1] for t in target]))
    nAttack = (maxH + A - 1) // A
    ans += nAttack
  else:
    ans += nAttack
    for t in target:
      heapq.heappush(XH, (t[0], t[1] - damage))
  
print(ans)

Solution (Python):
from collections import deque
N,D,A = map(int,input().split())
enemy = []
for i in range(N):
    C,B = map(int,input().split())
    enemy.append([C,B])
enemy.sort()
count = 0
chk_deque = deque()
total = 0
for i in range(N):
    if enemy[i][0] < D*2:
        demand =  (enemy[i][1]-1)//A + 1
        if demand > count :
            chk_deque.append([enemy[i][0],demand-count])
            total += demand - count
            count = demand
    else:
        for j in range(len(chk_deque)):
            a = chk_deque.popleft()
            if a[0] +2*D < enemy[i][0] :
                count -= a[1]
            else:
                chk_deque.appendleft(a)
                break
        demand =  (enemy[i][1]-1)//A + 1
        if demand > count :
            chk_deque.append([enemy[i][0],demand-count])
            total += demand - count
            count = demand
print(total)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
import bisect

n, d, a = [int(item) for item in input().split()]
places = []
xh = []
for i in range(n):
    x, h = [int(item) for item in input().split()]
    xh.append((x, h))
    places.append(x)
xh.sort()
places.sort()

N = 2**((n - 1).bit_length())
data0 = [0]*(N+1)
data1 = [0]*(N+1)

def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)


def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0
for i, (x, h) in enumerate(xh):
    init_damage = (query(1, i+2) - query(1, i+1)) * a
    if init_damage >= h:
        continue
    bomb = (h - init_damage + a - 1) // a
    ans += bomb
    r_lim = bisect.bisect_right(places, x+2*d)
    add(1, r_lim+1, bomb)
print(ans)

Solution (Python):

 
import sys, math, bisect
sys.setrecursionlimit(300000)
 
 
def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    p = []
    for i in range(N):
        p.append([X[i], H[i]])
    p.sort()
    ret = 0
    idx = []
    val = []
    cur = 0
    nex = 0
    cum = 0
    minus = 0
    l = 0
    for i in range(N):
        v = cum
        while l < i and idx[l] < i:
            minus = val[l]
            l += 1
        v -= minus
        p[i][1] = max(0, p[i][1] - v * A)
        tmp = math.ceil(p[i][1] / A)
        ret += tmp
        x = p[i][0] + D
        while nex < N and p[nex][0] <= x + D:
            
            
            nex += 1
        cum += tmp
        idx.append(nex - 1)
        val.append(cum)
        
        
        
        
        
        
        
    print(ret)
    return
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    D = int(next(tokens))  
    A = int(next(tokens))  
    X = [int()] * (N)  
    H = [int()] * (N)  
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n,d,a = map(int,input().split())
H = [list(map(int,input().split())) for i in range(n)]
H.sort()

ans = 0
m = 0
M = []
t = 0
for i in range(n):
    while t < len(M) and M[t][1] < H[i][0]:
        m -= M[t][0]
        t += 1
    H[i][1] -= m
    if H[i][1] > 0:
        dn = -(-H[i][1]//a)
        dd = dn * a
        M.append([dd, H[i][0]+d*2])
        ans += dn
        m += dd
    
print(ans)

Solution (Python):
import sys
import bisect
import math
from operator import itemgetter
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, D, A = IL()
X = []
xx = []
H = []
for i in range(N):
  x, h = IL()
  xx.append(x)
  X.append([x, i])
  H.append(h)
else:
  xx.append(MAX_INT)
xx.sort()
X.sort(key=itemgetter(0))
data = [0]*(N+1)

D = D*2
damage = 0
ans = 0
for i in range(N):
  x,j = X[i]
  hp = H[j]
  damage += data[i]
  num = max(0,math.ceil((hp - damage)/A))
  damage += num*A
  ans += num
  rng = x + D
  nxt = bisect.bisect_right(xx, rng)
  data[nxt] -= num*A


print(ans)

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

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

N,D,A = map(int,readline().split())
m = map(int,read().split())
X, H = zip(*sorted(zip(m,m)))

Xs = sorted(set(X) | set(x + D + D for x in X))
x_to_i = {x:i for i,x in enumerate(Xs)}

L = len(Xs)
d_atk = [0] * L

HP = [0] * L
for x,h in zip(X,H):
    i = x_to_i[x]
    HP[i] = h

d_atk = [0] * L

atk = 0 
answer = 0
for i in range(L):
    x = Xs[i]
    h = HP[i]
    if h > atk:
        rest = h - atk
        n = (rest + A - 1) // A
        atk += n * A
        answer += n
        d_atk[x_to_i[x+D+D]] = -n * A
    atk += d_atk[i]

print(answer)

Solution (Python):


import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    p = []
    for i in range(N):
        p.append([X[i], H[i]])
    p.sort()
    ret = 0
    idx = []
    val = []
    nex = 0
    minus = 0
    l = 0
    for i in range(N):
        
        
        v = ret
        while l < i and idx[l] < i:
            minus = val[l]
            l += 1
        v -= minus
        p[i][1] = max(0, p[i][1] - v * A)
        tmp = math.ceil(p[i][1] / A)
        ret += tmp
        x = p[i][0] + D
        while nex < N and p[nex][0] <= x + D:
            nex += 1
        nex -= 1
        idx.append(nex)
        val.append(ret)
        
        
        
        
        
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    D = int(next(tokens))  
    A = int(next(tokens))  
    X = [int()] * (N)  
    H = [int()] * (N)  
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)

if __name__ == '__main__':
    main()

Solution (Python):
import math
n,d,a=map(int,input().split())
XH=[]
for _ in range(n):
    x,h=map(int,input().split())
    h=math.ceil(h/a)
    XH.append([x,h])
XH.sort()
if n==1:
    print(XH[0][1])
    exit()
l=0
r=0
ans=XH[0][1]
c=XH[0][1]
L=[c]
while l<=n-1:
    left=XH[l][0]
    right=left+2*d
    if XH[r+1][0]<=right:
        cc=max(0,XH[r+1][1]-c)
        L.append(cc)
        c+=cc
        ans+=cc
        r+=1
        if r>=n-1:
            r-=1
            l+=1
    else:
        c-=L[l]
        l+=1
print(ans)

Solution (Python):


import math

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

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q*A))
        s += q*A
        t += q

print(t)

Solution (Python):
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N; V = [[]for _ in range(N)]
    for i in range(N):
        A[i],B[i] = LI()
        V[i] = [A[i],B[i],A[i]/B[i]]
    V.sort(key=lambda x:x[2],reverse=True)
    dp = [[inf]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            if j <= H - V[i][0]:
                dp[i + 1][j + V[i][0]] = min(dp[i + 1][j + V[i][0]], dp[i][j] + V[i][1])
            else:
                dp[i + 1][H] = min(dp[i + 1][H], dp[i][j] + V[i][1])
    loop = (H-1) // V[0][0] + 1
    ans = [0]*loop
    for i in range(loop):
        curH = H - V[0][0]*i
        ans[i] = i * V[0][1] + min(dp[N][curH:])
    print(ans)

    print(min(ans))
    return

def examF():
    class segment_():
        def __init__(self, A, n, segfunc):
            
            self.ide_ele = 0
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        
        def update_add(self, k,u):
            k += self.num
            self.seg[k] += u
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    B = [0] * (N + 1)
    S = segment_(B,(N+1),lambda a, b: a+b)
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        left = bisect.bisect_left(X,X[i]-D*2)

        cur -= min(S.query(left,i),cur)
        ans +=cur
        S.update_add(i,cur)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

Solution (Python):
import sys
n,d,a=map(int,input().split())
xh=[]
xx=[]
for i in range(n):
    x,h=map(int,input().split())
    xx.append(x)
    xh.append((x,h//a+(h%a>0)))
xh.sort()
xx.sort()
dp=[0]*n
import bisect
buf=0
count=0
if d==0:
    for i in range(n):
        count+=xh[i][1]
    print(count)
    sys.exit()
for i in range(n):
    
    buf+=dp[i]
    y=max(xh[i][1]-buf,0)
    count+=y
    buf+=y
    idx=bisect.bisect_left(xx,xx[i]+2*d+1)
    if idx>=n:
        continue
    dp[idx]-=y
    
print(count)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect

import collections

dms = collections.deque()
mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []
for i in range(N):
    xh.append(LI())
xh.sort()


ans = 0
sum_dm = 0
for i in range(N):
    X, H = xh[i]
    while len(dms) > 0:
        if dms[0][0] + 2 * D < X:
            x, dm = dms.popleft()
            sum_dm -= dm
        else:
            break
    H -= sum_dm
    if H > 0:
        ans += math.ceil(H / A)
        dms.append([X, math.ceil(H/A) * A])
        sum_dm += math.ceil(H/A) * A
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret




def main():
    N,D,A = list(map(int,input().split()))

    enemy = []
    for i in range(N):
        x,h = list(map(int,input().split()))
        if h%A==0:
            enemy.append([x,h//A])
        else:
            enemy.append([x,h//A+1])

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l

    bit = BIT([0]*N)

    count1 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v=0
        if enemy[i][1] - v>0:
            count1 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)

    enemy = enemy[::-1]
    for i in range(N):
        enemy[i][0] = -enemy[i][0]

    bit = BIT([0]*N)

    count2 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v = 0
        if enemy[i][1] - v>0:
            count2 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)


    print(min(count1,count2))

if __name__ == '__main__':
    main()

Solution (Python):
N,D,A = map(int,input().split())
XH = [tuple(map(int,input().split())) for i in range(N)]
XH.sort()
from collections import deque
q = deque()

ans = dmg = 0
for x,h in XH:
    while q and q[0][0] < x:
        _,d = q.popleft()
        dmg -= d
    rem = h - dmg
    if rem <= 0: continue
    a = -(-rem // A)
    ans += a
    dmg += a*A
    q.append((x + 2*D, a*A))
print(ans)

Solution (Python):

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

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

import math
i, ans = 0, 0
powers = []
damage = 0
while i < N:
    x, h = X_H_pairs[i]
    if powers:
        while powers and x - powers[0][0] > 2*D:
            damage -= powers[0][1]
            powers.pop(0)

    h -= damage
    if h <= 0:
        i += 1
        continue
    else:
        times = int(math.ceil(h / A))
        ans += times

        dh = times * A
        damage += dh
        powers.append((x, dh))
        i += 1

print(ans)

Solution (Python):
from bisect import*
def _add(data,k,x):
    while k<=N:
        data[k]+=x
        k+=k&-k
def add(l,r,x):
    _add(data0,l,-x*(l-1))
    _add(data0,r,x*(r-1))
    _add(data1,l,x)
    _add(data1,r,-x)
def _get(data,k):
    s=0
    while k:
        s+=data[k]
        k-=k&-k
    return s
def query(l,r):
    return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)
N,d,a,*t=map(int,open(0).read().split())
data0=[0]*(N+1)
data1=[0]*(N+1)
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, d, a = LI()
X = []
H = []
xh = LIR(n)
xh.sort()
for x, h in xh:
    X += [x]
    H += [h]

X2 = [0] * n
ret = 0
ans = 0
for i in range(n):
    x = X[i]
    ret -= X2[i]
    remain = H[i] - ret
    if remain > 0:
        j = remain // a + bool(remain % a)
        ans += j
        ret += j * a
        if x + d * 2 < X[-1]:
            l = i
            r = n
            while l + 1 < r:
                mid = (l + r) // 2
                if X[mid] <= x + d * 2:
                    l = mid
                else:
                    r = mid
            X2[r] += j * a


print(ans)

Solution (Python):
import math
import sys
input = sys.stdin.readline
import heapq
def main():
    N,D,A=map(int,input().split())
    xh = [tuple(map(int,input().split())) for _ in range(N)]
    xh = sorted(xh, key = lambda x:x[0])
    x = [elem[0] for elem in xh]
    h = [elem[1] for elem in xh]
    res = 0
    buff = 0
    q = []
    heapq.heapify(q)
    
    for i in range(N):
        while len(q)!=0:
            p = heapq.heappop(q)
            if p[0] < x[i]:
                
                buff -= p[1]
            else:
                heapq.heappush(q,p)
                break
        nowhp = h[i] - buff*A
        if nowhp <= 0:
            continue
        cnt = math.ceil(nowhp/A)
        res += cnt
        buff += cnt
        
        ins = (x[i]+2*D, cnt)
        heapq.heappush(q,ins)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
''' Hey stalker :) '''
INF = 10**10
def main():
    
    ''' Cook your dish here! '''
    n, d, a = get_list()
    monsters = [get_list() for _ in range(n)]
    monsters.sort()
    sm = 0
    updates = []
    ptr = 0
    res = 0
    for x, helth in monsters:
        while ptr<len(updates) and updates[ptr][0]<=x:
            sm += updates[ptr][1]
            ptr += 1
        if helth>sm:
            times = (helth-sm+a-1)//a
            k = times*a
            res += times
            sm += k
            updates.append([x+2*d+1, -k])
    print(res)

''' Pythonista fLite 1.1 '''
import sys




input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()

print(*out, sep='\n')

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

tekis.sort()

haba = 2 * D


ruisekiwa = [(0, float("-inf"))]

left = 0

ans = 0
for i in range(N):
    x, h = tekis[i]

    while left < len(ruisekiwa) and ruisekiwa[left][1] < x:
        left += 1
    left -= 1
    
    
    

    imamadeiryoku = 0
    if left < len(ruisekiwa):
        imamadeiryoku = ruisekiwa[-1][0] - ruisekiwa[left][0]
    

    h -= imamadeiryoku

    bakudankaisuu = 0
    if h > 0:
        bakudankaisuu = h // A + (1 if h % A > 0 else 0)
    ans += bakudankaisuu
    
    bakudaniryoku = A * bakudankaisuu
    ruisekiwa.append((bakudaniryoku + ruisekiwa[-1][0], x + haba))

print(ans)