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 = [list(map(int, input().split())) for i in range(n)]
xh.sort()
que = deque()
ans = 0
atk = 0
for x, h in xh:
    while que and que[0][0] <= x:
        atk -= que.popleft()[1]
    h -= a*atk
    if h <= 0:
        continue
    count = -(-h//a)
    ans += count
    atk += count
    que.append((x+2*d+1, count))
print(ans)

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            pl()
            b-=ql()
        h-=b
        t=0--h//a
        if t>0:
            s+=t
            b+=t*a
            pa(x+d+d)
            qa(t*a)
    print(s)
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    f,g=p.popleft,q.popleft
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            f()
            b-=g()
        h-=b
        t=0--h//a
        if t>0:
            s+=t
            b+=t*a
            p+=x+d+d,
            q+=t*a,
    print(s)
main()

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

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

Solution (Python):
import math
from operator import itemgetter
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=tuple(map(int,input().split()))
  l.append(k)
l.sort(key=itemgetter(0))
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Solution (Python):
import math
from operator import itemgetter
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=tuple(map(int,input().split()))
  l.append(k)
l.sort(key=itemgetter(0))
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a
 
show_flg=False
show_flg=True
 
ans=0
m=[]

n,d,a=LI()
for i in range(n):
    x,h=LI()
    m.append((x,h))

m.sort(key=lambda x:x[0])
dm=0
q=deque()

for i in range(n):
    x,h=m[i]
    while q:
        if x>q[0][0]:
            y,c=q.popleft()
            dm-=c*a
        else:
            break

    if h>dm:
        c=(h-dm+a-1)//a
        dm+=c*a
        ans+=c
        q.append((x+2*d,c))

print(ans)

Solution (Python):

n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break
    ms[i][1]-=tmp
    ms[i][1] = max(ms[i][1],0)

    if ms[i][1]>0:
        
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

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


N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 

import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N+1, int)
answer = 0
power = 0
for i in range(N):
    power -= damage[i]
    J = (H[i]-1+A)//A
    if J <= power:
        continue
    else:
        a = bi.bisect_right(X, X[i]+2*D)
        damage[a] += J - power
        answer += J-power
        power = J
 
print(answer)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
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())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)

Solution (Python):
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
imos=[0]*(n+1)
x=[]
for i in range(n):
  x.append(xh[i][0])
ans,cnt=0,0
for i in range(n):
  cnt+=imos[i]
  hp=xh[i][1]-cnt*a
  if hp>0:
    cnt+=ceil(hp/a)
    ans+=ceil(hp/a)
    imos[bisect_right(x,x[i]+2*d)]-=ceil(hp/a)
print(ans)

Solution (Python):


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


def bit_add(i,w):
    x = i+1
    while x <= n:
        bit[x-1] += w
        x += x & -x
    return

def bit_sum(i):
    res = 0
    x = i+1
    while x > 0:
        res += bit[x-1]
        x -= x & -x
    return res

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

ans = 0
for i,h,r in lst:
    tmp = max(0,math.ceil((h - bit_sum(i))/a))
    ans += tmp
    bit_add(r,-tmp*a)
    bit_add(i,tmp*a)
print(ans)

Solution (Python):


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

def bit_add(i,w):
    x = i+1
    while x <= n:
        bit[x-1] += w
        x += x & -x
    return

def bit_sum(i):
    res = 0
    x = i+1
    while x > 0:
        res += bit[x-1]
        x -= x & -x
    return res

n,d,a = LI()
bit = [0]*(n+1)
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,_ in xh]
lst = []
for x,h in xh:
    r = br(X,x+2*d)
    lst.append((x,h,r))

ans = 0
for i in range(n):
    x,h,r = lst[i]
    tmp = max(0,math.ceil((h - bit_sum(i))/a))
    ans += tmp
    bit_add(r,-tmp*a)
    bit_add(i,tmp*a)
print(ans)

Solution (Python):
import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)

Solution (Python):
from collections import deque

N, D, A, *XH = map(int, open(0).read().split())

ans = 0
Q = deque()
damage = 0
for x, h in sorted(zip(*[iter(XH)] * 2)):

    while Q and Q[0][0] < x:
        v, d = Q.popleft()
        damage -= d

    h -= damage
    if h <= 0:
        continue

    n = -(-h // A)

    damage += A * n
    ans += n

    Q.append((x + 2 * D, A * n))

print(ans)

Solution (Python):

from heapq import heappush, heappop

N, D, A, *XH = map(int, open(0).read().split())

XH = sorted(zip(*[iter(XH)] * 2))

ans = 0
Q = []
damage = 0
for x, h in XH:

    while Q:
        v, d = Q[0]
        if v >= x:
            break
        v, d = heappop(Q)
        damage -= d

    h -= damage
    if h <= 0:
        continue

    n = -(-h // A)

    damage += A * n
    ans += n

    heappush(Q, (x + 2 * D, A * n))

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.sort()


ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:

        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))

    

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])

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

def bisect(x):
    i_min=0
    i_max=n
    while i_min<i_max:
        i = (i_min+i_max)//2
        if xh[i][0]<=x:
            i_min = i+1
        else:
            i_max = i
    return i_min

ans = 0
accu = 0
out = [0]*(n+1)
for i, (x, h) in enumerate(xh):
    accu -= out[i]
    hp = h-accu
    if hp<=0:
        continue
    accu += hp
    ans += hp
    out[bisect(x+2*d)] += hp 
print(ans)

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

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    R = [0] * (N * 2)
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append((x, h))
        XH.append((x + 2 * D + 1, -float("inf")))
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 1))

    ans = 0
    ruiseki = 0

    for i in range(N * 2):
        x, h = XH[i]
        if h != -float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == -float("inf"):
                    R[nx] -= tmpruiseki
                else:
                    R[nx + 1] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += R[i]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,d,a = map(int,input().split())
monsters = [tuple(map(int,input().split())) for _ in range(n)]
monsters.sort()



atk_count = [0]*n
atk_count_sum = 0
l = 0 
for i in range(n):
    x = monsters[i][0]
    h = monsters[i][1]
    
    while monsters[l][0] + 2*d < x:
        atk_count_sum -= atk_count[l]
        l += 1
    
    al = atk_count_sum * a
    h = h - al
    if h > 0:
        atk_count[i] = -(-h//a)
    atk_count_sum += atk_count[i]
print(sum(atk_count))

Solution (Python):



from collections import deque

def main():
  n, d, a = map(int, input().strip().split())
  XsHs = [list(map(int, input().strip().split())) for _ in range(n)]
  XsHs.sort(key = lambda x:x[0])

  queue = deque()
  total = 0
  ans = 0
  for x, h in XsHs:
    while queue:
      if queue[0][0] < x:
        total -= queue[0][1]
        queue.popleft()
      else:
        break
    h -= total
    if h > 0:
      num = (h+a-1)//a
      ans += num
      total += (num*a)
      queue.append((x+(2*d), num*a))
  print(ans)

if __name__=='__main__':
  main()

Solution (Python):
from operator import itemgetter
import bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
x = []
for X,h in xh:
  x.append(X)
ans = 0
attack_start = [i for i in range(N)]
now = 0
cumsum = [0] * (N+1)
for L,(X,H) in enumerate(xh):
  R = bisect.bisect_right(x,X+2*d)
  for i in range(now,R):
    attack_start[i] = L
  now = R
  damage = (cumsum[L] - cumsum[attack_start[L]]) * a
  attack_time = max(0,math.ceil((H - damage) / a))
  ans += attack_time
  cumsum[L+1] = ans
print(ans)

Solution (Python):
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def update(self,left,right,f):
        left += self.n
        right += self.n
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],f)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],f)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

import sys
input = sys.stdin.readline

import bisect

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

monster.sort()
ans = 0
X = []
H = []
for i in range(N):
    X.append(monster[i][0])
    H.append(monster[i][1])

r = [0 for _ in range(N)]
for i in range(N):
    r[i] = bisect.bisect_left(X,X[i]+2*D+1)

sg = SegmentTreeDual(H,lambda x,y:x+y,0)

for i in range(N):
    hp = sg.get(i)
    if hp <= 0:
        continue
    cnt = -(-hp//A)
    sg.update(i,r[i],-A*cnt)
    ans += cnt

print(ans)

Solution (Python):
import sys
from heapq import heapify, heappop, heappush

n, d, a = list(map(int, input().split()))
xh = []
for line in sys.stdin:
    x, h = map(int, line.split())
    xh.append((x, 0, h))
heapify(xh)
atk_cnt = 0
ans = 0
while xh:
    x, t, h = heappop(xh)
    if t == 0:
        if atk_cnt * a >= h:
            continue
        remain = h - atk_cnt * a
        new_atk = (remain - 1) // a + 1
        heappush(xh, (x + 2 * d, 1, new_atk))
        ans += new_atk
        atk_cnt += new_atk
    else:
        atk_cnt -= h
print(ans)

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

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

damage=0 
from collections import deque
bombs=deque() 

ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1] 
  
  while bombs:
    b=bombs.popleft()
    if b[0]<x:
      damage-=b[1]
    else:
      bombs.appendleft(b)
      break
  h-=damage
  if h>0:
    turn=((h+A-1)//A)
    damage+=turn*A
    ans+=turn
    bombs.append([x+D,turn*A])
print(ans)

Solution (Python):
class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r: s.down(r)
    ans = s.inf
    k, kl, kr = 0, 0, s.N - 1
    S = [[k, kl, kr]]
    while S:
      k, kl, kr = S.pop()
      if l <= kl and r >= kr: ans = s.do(ans, s.T[k])
      else:
        t = (kl + kr) // 2
        if l > t: S.append([2 * k + 2, t + 1,kr])
        elif r < t + 1: S.append([2 * k + 1, kl, t])
        else: 
          S.append([2 * k + 2, t + 1,kr])
          S.append([2 * k + 1, kl, t])
    return ans
  def add(s, l, r, v):
    k, kl, kr = 0, 0, s.N - 1
    S = [[k, kl, kr]]
    while S:
      k, kl, kr = S.pop()
      if l <= kl and kr <= r:
        s.D[k] += v
        continue
      if k >= s.N: continue
      if kl <= r and l <= kr:
        t = (kl + kr) // 2
        S.append([2 * k + 1, kl, t])
        S.append([2 * k + 2, t + 1, kr])

  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Solution (Python):
import math,bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,d,a = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()


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

def init(init_val): 
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): 
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): 
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num



x = []
for i in lst1:
    x.append(i[0])


ans = 0

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

    r = query(k,i) 

    if lst1[i][1] > r:
        if (lst1[i][1]-r)/a%1==0:
            need = (lst1[i][1]-r)//a
        else:
            need = (lst1[i][1]-r)//a+1
        ans += need
        update(i,need*a)

print(ans)

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

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        c = -(-dam//A)
        count += c
        aldam += c*A
        q.append((now+2*D,c*A))

    print(count)

if __name__ == "__main__":
    main()

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

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        c = -(-dam//A)
        count += c
        aldam += c*A
        q.append((now+2*D,c*A))

    print(count)

if __name__ == "__main__":
    main()

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

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

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele = 0

data = []
n, d, a = map(int, input().split())
x_point = []
for i in range(n):
    x, h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
x_point.sort()
data.sort()

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
ans = 0
for i in range(n):
    x, h = data[i]
    index = bisect.bisect_left(x_point, x - 2*d)
    sum_damage = query(index, i)
    h -= sum_damage
    count = max(((h+a-1)//a), 0)
    ans += count
    update(i, count * a)
print(ans)

Solution (Python):
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

N,d,a=LI()


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()
    arr=[]
    for i in range(LV):
        if rc <= i:
            arr.append(R)
        if L < R and lc <= i:
            arr.append(L)
        L >>= 1; R >>= 1
    return arr


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
    

show_flg=False
show_flg=True

ans=0
n=N
m=[]
for i in range(n):
    x,h=LI()
    m.append((x,h))
m.append((inf,0))
m.sort(key=lambda x:x[0])
X=[x for x,h in m]
H=[h for x,h in m]

for j in range(n):
    i=j+1
    dm=query(i,i+1)
    if H[j]>dm:
        c=(H[j]-dm+a-1)//a
        r=bisect.bisect(X,X[j]+2*d)
        update(i,r+1,c*a)
        ans+=c



    
print(ans)