Problem:
 Score : 600 points    Problem Statement Silver Fox is fighting with N monsters.  The monsters are standing in a row, and we can assume them to be standing on a number line. The i -th monster, standing at the coordinate X_i , has the health of H_i .  Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A .
There is no way other than bombs to decrease the monster's health.  Silver Fox wins when all the monsters' healths become 0 or below.  Find the minimum number of bombs needed to win.      Constraints  1 \leq N \leq 2 \times 10^5  0 \leq D \leq 10^9  1 \leq A \leq 10^9  0 \leq X_i \leq 10^9  1 \leq H_i \leq 10^9  X_i are distinct.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  D  A  X_1  H_1  :  X_N  H_N       Output Print the minimum number of bombs needed to win.        Sample Input 1 3 3 2
1 2
5 4
9 2      Sample Output 1 2  First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2 .  Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2 .  Now, all the monsters' healths are 0 .
We cannot make all the monsters' health drop to 0 or below with just one bomb.       Sample Input 2 9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5      Sample Output 2 5  We should use five bombs at the coordinate 5 .       Sample Input 3 3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000      Sample Output 3 3000000000  Watch out for overflow.

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

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

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

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

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda t: t[0])
Xs = [X for X, _ in XH]
bit = BIT(N+1)
ans = 0

for i in range(N):
    X = XH[i][0]
    H = max(0, XH[i][1]-A*bit.acc(i+1))
    cnt = (H+A-1)//A
    ans += cnt
    j = bisect_right(Xs, X+2*D)
    bit.add(i, cnt)
    bit.add(j, -cnt)

print(ans)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
memo = deque()
cnt = 0
for x, h in XH:
    while memo and memo[0][0] < x:
        _, i = memo.popleft()
        cnt -= i
    h -= cnt * A
    h = max(h, 0)
    bomb = (h + A - 1) // A
    ans += bomb
    cnt += bomb
    memo.append((x + 2 * D, bomb))

print(ans)

Solution (Python):
n,d,a=map(int,input().split())
d*=2
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[i for i,j in xh]+[10**20]
h=[j for i,j in xh]
notimos=[0]*(n+1)
c=0
ans=0
from bisect import bisect_right
for i in range(n):
  c+=notimos[i]
  xx,hh=xh[i]
  hh=max(0,hh-c*a)
  m=0--hh//a
  ans+=m
  c+=m
  notimos[bisect_right(x,xx+d)]-=m
print(ans)

Solution (Python):
n,d,a=map(int,input().split())
d*=2
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[i for i,j in xh]+[10**20]
h=[j for i,j in xh]
notimos=[0]*(n+1)
c=0
ans=0
from bisect import bisect_right
for i in range(n):
  c+=notimos[i]
  xx,hh=xh[i]
  hh=max(0,hh-c*a)
  m=0--hh//a
  ans+=m
  c+=m
  notimos[bisect_right(x,xx+d)]-=m
print(ans)

Solution (Python):
from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    if i != 0:
        damage[i] += damage[i-1]
    bi = bisect.bisect(x,2*d+x[i])
    count = max(math.ceil((h[i]-damage[i])/a),0)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count
    
print(point)

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

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

cnt=0

import heapq  




bomb=0
he=[]
heapq.heapify(he)
dic={}

for i in range(n):
    
    (x,h)=xh[i]

    if bomb==0:
        secchi=x+d
        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        dic[secchi]=damage
        bomb+=damage
        heapq.heappush(he, secchi)
    else:
        while a:
            tmp=heapq.heappop(he)  
            if tmp+d<x:
                bomb-=dic[tmp]
            else:
                heapq.heappush(he, tmp)
                break
            if bomb==0:
                break

        if bomb<h:
            h-=bomb
            secchi=x+d
            count=((-1*h)//a)*(-1)
            damage=count*a
            cnt+=count
            dic[secchi]=damage
            bomb+=damage
            heapq.heappush(he, secchi)



print(cnt)

Solution (Python):
from bisect import bisect_right
import sys
input=sys.stdin.readline
 
 
class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
 
        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    
    def propagates(self, ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0
 
    
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)
 
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
 
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(N)]

    l.sort()
    lh = [h for x,h in l]
    lx = [x for x,h in l]
    tree = LazySegTree(N)
    tree.set_list(lh, N)
    ans = 0

    for i in range(N):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            pos = bisect_right(lx, lx[i]+2*D)
            tree.update(i, pos, -c*A)
            ans += c

    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
n,d,a=map(int,input().split())
d=d*2
M=sorted([list(map(int,input().split())) for i in range(n)])
l=0
A=[0]*n
B=[0]
ans=0
for i in range(n):
  while M[l][0]+d<M[i][0]:
    l=l+1
  ans=ans+max(0,(M[i][1]-B[i]+B[l]+a-1)//a)
  A[i]=max(0,(M[i][1]-B[i]+B[l]+a-1)//a)*a
  B.append(B[-1]+A[i])
print(ans)

Solution (Python):
"""
Given N, D, A, N means no. of monsters, D means distances of bombs, A attack of the bombs

Find the minimum of bombs required to win.

Each monster out of N pairs - pair[0] = position, pair[1] = health

hashmap[i] = H

pref

"""
from collections import deque

mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    INF = 1e9 + 7
    N, D, A = [int(x) for x in raw_input().split()]
    D *= 2
    monsters = []
    
    change = [0 for _ in range(N)]
    for _ in range(N):
        pos, health = [int(x) for x in raw_input().split()]
        
        
        
        health = (health + A - 1) // A
        
        
        monsters.append([pos, health])    
    """
    remain_attack = 0
    ans = 0
    for cur in range(smallest_x, biggest_x+1):
        if cur in m and m[cur] > remain_attack:
            remained_health = m[cur] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            attack = times * A
            pref_sum[cur + D] = pref_sum.get(cur + D, 0) - attack
            remain_attack += attack
            ans += times
        remain_attack += pref_sum.get(cur, 0)
            
    """   
            
    monsters.sort(key = lambda x : x[0])
    
    
    
    
    running_sum = 0
    
    ans = 0
    
    for i in range(N):
        pos, health = monsters[i]
        running_sum += change[i]
        
        my_health = health - running_sum
        if my_health <= 0:
            continue 
        
        
        lo = i+1
        hi = N-1
        ok = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            
            if monsters[mid][0] <= pos + D:
                ok = mid
                lo = mid + 1
            else:
                hi = mid - 1
        
        if ok != -1:
            running_sum += my_health
        if ok + 1 < N:
            change[ok+1] -= my_health
            
            
        ans += my_health
        
                
        """
        while len(remain_attacks_queue) and monster[0] - D > remain_attacks_queue[0][0]:
            remain_attack -= remain_attacks_queue.popleft()[1]
        if remain_attack < monster[1]:
            remained_health = monster[1] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            
            attack = times * A
            remain_attacks_queue.append([monster[0], attack])
            ans += times
            remain_attack += attack
        """
    
        
    print(ans)
    

main()

Solution (Python):
"""
Given N, D, A, N means no. of monsters, D means distances of bombs, A attack of the bombs

Find the minimum of bombs required to win.

Each monster out of N pairs - pair[0] = position, pair[1] = health
"""
from collections import deque

mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    N, D, A = [int(x) for x in raw_input().split()]
    D *= 2
    monsters = []
    
    for _ in range(N):
        pos, health = [int(x) for x in raw_input().split()]
        monsters.append([pos, health])    
    
    
    monsters.sort(key = lambda x : x[0])
    
    remain_attacks_queue = deque([])
    
    remain_attack = 0
    
    ans = 0
    
    for monster in monsters:
        
        
        while len(remain_attacks_queue) and monster[0] - D > remain_attacks_queue[0][0]:
            remain_attack -= remain_attacks_queue.popleft()[1]
        if remain_attack < monster[1]:
            remained_health = monster[1] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            
            attack = times * A
            remain_attacks_queue.append([monster[0], attack])
            ans += times
            remain_attack += attack
        
    print(ans)
    

main()

Solution (Python):
import math
from bisect import bisect_right

n, d, a = map(int, input().split())
x_list = []
max_x = 0
for _ in range(n):
    x, h = map(int, input().split())
    x -= 1
    x_list.append([x, h])
    max_x = max(max_x, x)
x_list.sort()
xx = [x[0] for x in x_list]
hh = [x[1] for x in x_list]
ans = 0
accum = [0 for _ in range(n)]
for index, [x, h] in enumerate(x_list):
    if index != 0:
        accum[index] += accum[index - 1]
    cnt = max(math.ceil((hh[index] - accum[index]) / a),  0)
    ans += cnt
    index_right = bisect_right(xx, xx[index] + (2 * d))
    accum[index] += cnt * a
    if index_right < n:
        accum[index_right] -= cnt * a
print(ans)

Solution (Python):
import bisect
n, d, a = map(int, input().split())
fox = [None]*n
for i in range(n):
  x, h = map(int, input().split())
  fox[i] = (x, h)

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

ans = 0
bit = [0]*n
for i in range(n):
  if i != 0:
    bit[i] += bit[i-1]
  if bit[i] >= h[i]:
    continue
  sub = (h[i]-bit[i]-1)//a+1
  ans += sub
  bit[i] += sub*a
  index = bisect.bisect_right(x, x[i]+2*d)
  if index == n:
    continue
  bit[index] -= sub*a
print(ans)

Solution (Python):
import bisect
import sys

def main():
  input = sys.stdin.readline
  n, d, a = map(int, input().split())
  fox = [None]*n
  for i in range(n):
    x, h = map(int, input().split())
    fox[i] = (x, h)

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

  ans = 0
  bit = [0]*n
  for i in range(n):
    if i != 0:
      bit[i] += bit[i-1]
    sub = max([(h[i]-bit[i]-1)//a+1, 0])
    ans += sub
    bit[i] += sub*a
    index = bisect.bisect_right(x, x[i]+2*d)
    if index != n:
      bit[index] -= sub*a
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
import bisect
import sys

def main():
  input = sys.stdin.readline
  n, d, a = map(int, input().split())
  fox = [None]*n
  for i in range(n):
    x, h = map(int, input().split())
    fox[i] = (x, h)

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

  ans = 0
  bit = [0]*n
  for i in range(n):
    if i != 0:
      bit[i] += bit[i-1]
    sub = max([(h[i]-bit[i]-1)//a+1, 0])
    ans += sub
    bit[i] += sub*a
    index = bisect.bisect_right(x, x[i]+2*d)
    if index != n:
      bit[index] -= sub*a
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
import bisect
n, d, a = map(int, input().split())
fox = [None]*n
for i in range(n):
  x, h = map(int, input().split())
  fox[i] = (x, h)

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

ans = 0
bit = [0]*n
for i in range(n):
  if i != 0:
    bit[i] += bit[i-1]
  if bit[i] >= h[i]:
    continue
  sub = (h[i]-bit[i]-1)//a+1
  ans += sub
  bit[i] += sub*a
  index = bisect.bisect_right(x, x[i]+2*d)
  if index == n:
    continue
  bit[index] -= sub*a
print(ans)

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    n,d,a=map(int,readline().split())
    xh=[list(map(int,readline().split())) for _ in range(n)]
    xh.sort()
    x=[0]*n
    h=[0]*n
    for i in range(n):
        x[i],h[i]=xh[i][0],xh[i][1]

    dq=deque()
    now=0
    cnt=0
    for i in range(n):
        if i==0:
            cnt+=(h[i]+a-1)//a
            now+=(h[i]+a-1)//a*a
            dq.append([x[i]+2*d,now])
        else:
            while len(dq)!=0 and dq[0][0]<x[i]:
                tmp=dq.popleft()
                now-=tmp[1]
            if h[i]<=now:
                pass
            else:
                dq.append([x[i]+2*d,(h[i]-now+a-1)//a*a])
                cnt+=(h[i]-now+a-1)//a
                now+=(h[i]-now+a-1)//a*a

    print(cnt)

if __name__=="__main__":
    main()

Solution (Python):
from collections import deque
n, d, a = map(int, input().split())

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    while dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
        else:
            break
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)

Solution (Python):
N,D,A=map(int, input().split())
B=[list(map(int, input().split())) for _ in range(N)]
C=sorted(B)
d,E=zip(*C)
import bisect
Damage=[0]*N
for i in range(N):
  e=bisect.bisect_right(d,d[i]+2*D)
  Damage[i]=e
dd=[0]*(N+1)
cnt=0
for i in range(N):
  if i!=0:
    dd[i]+=dd[i-1]
  h=E[i]
  h-=dd[i]
  if h>0:
    bomb=-(-h//A)
    cnt+=bomb
    dd[i]+=A*bomb
    dd[Damage[i]]-=A*bomb
print(cnt)

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

n, d, a = map(int, input().split())
m = sorted([list(map(int, input().split())) for _ in range(n)])
m = [[x, ceil(h / a)] for x, h in m]

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    rest_h = max(0, h - acc_damage)
    ans += rest_h
    acc_damage += rest_h

    if rest_h:
        que.append([x + 2 * d, rest_h])

print(ans)

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

n, d, a = map(int, input().split())
m = sorted([list(map(int, input().split())) for _ in range(n)])
m = [[x, ceil(h / a)] for x, h in m]

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * d, need])

print(ans)

Solution (Python):
from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect
def main():
    n,d,a=map(int,input().split())
    XH=[list(map(int,input().split())) for i in range(n)]
    XH.sort()
    X,H=zip(*XH)
    right=[0]*n
    for i,x in enumerate(X):
        right[i]=bisect(X,x+2*d)
    damage=[0]*(n+1)
    ans=0
    for i,(x,h) in enumerate(XH):
        if i!=0:
            damage[i]+=damage[i-1]
        h-=damage[i]
        if h>0:
            cunt=-(-h//a)
            ans+=cunt
            damage[i]+=a*cunt
            damage[right[i]]-=a*cunt
    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect
def main():
    n,d,a=map(int,input().split())
    XH=[list(map(int,input().split())) for i in range(n)]
    XH.sort()
    X,H=zip(*XH)
    right=[0]*n
    for i,x in enumerate(X):
        right[i]=bisect(X,x+2*d)
    damage=[0]*(n+1)
    ans=0
    for i,(x,h) in enumerate(XH):
        if i!=0:
            damage[i]+=damage[i-1]
        h-=damage[i]
        if h>0:
            cunt=-(-h//a)
            ans+=cunt
            damage[i]+=a*cunt
            damage[right[i]]-=a*cunt
    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
from collections import deque
damage = deque()
dmg = 0
for x,h in enemies:
    if len(damage) == 0:
        bomb = -(-h//A)
        damage.append([x+2*D,bomb])
        dmg += bomb*A
        ans += bomb
    else:
        while len(damage) > 0:
            d,bomb = damage.popleft()
            if x > d:
                dmg -= bomb*A
            else:
                damage.appendleft([d,bomb])
                break
        if h > dmg:
            bomb = -(-(h-dmg)//A)
            dmg += bomb*A
            damage.append([x+2*D,bomb])
            ans += bomb

print(ans)

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

N, D, A = MAP()
XH = [LIST() for _ in range(N)]
XH.sort(key=lambda x:x[0])
X, H = zip(*XH)
right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

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

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

def main():
    
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            
            self.ide_ele = ele
            self.segfun = segfun
            
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)
 
        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2
 
        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2
 
        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret
 
    N, D, A = map(int,readline().split())
    X = [list(map(int,readline().split())) for _ in range(N)]
    X.sort()
    L = [0]*N
    for i in range(N):
        L[i] = X[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i,[x,h] in enumerate(X):
        H = h - S.query(i)
        if H<=0:
            continue
        ind = bisect.bisect(L,x+2*D)
        need = (H-1)//A + 1
        S.update(i,ind,need*A)
        ans += need
    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
from queue import deque

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    bom = deque()
    cur = 0
    for i, mi in enumerate(mon):

        while len(bom) != 0 and bom[0][0] < mi[0]:
            b = bom.popleft()
            cur -= b[1]

        if mi[1] <= cur:
            continue
        else:
            b1 = mi[1] - cur
            bom.append((mi[0] + 2 * d, b1))
            cur += b1
            ans += b1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
from queue import deque

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    bom = deque()
    cur = 0
    for i, mi in enumerate(mon):

        while len(bom) != 0 and bom[0][0] < mi[0]:
            b = bom.popleft()
            cur -= b[1]

        if mi[1] <= cur:
            continue
        else:
            b1 = mi[1] - cur
            bom.append((mi[0] + 2 * d, b1))
            cur += b1
            ans += b1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil
from collections import deque
def main():
    N,D,A = map(int, input().split())
    
    
    
    
    
    
    
    

    Monsters = sorted([list(map(int, input().split())) for i in range(N)])
    Monsters = [[x-1, ceil(h / A)] for x, h in Monsters]

    acc_damage = 0
    que = deque([])

    ans = 0
    for x, h in Monsters:
        
        while que and x > que[0][0]:
            limit, damage = que.popleft()
            acc_damage -= damage

        need = max(0, h - acc_damage)
        ans += need
        acc_damage += need

        if need:
            que.append([x + 2 * D, need])

    print(ans)


main()

Solution (Python):
from heapq import heappush, heappop

n, d, a = map(int, input().split())
actions = []
for _ in range(n):
    x, h = map(int, input().split())
    heappush(actions, (x, 0, (h + a - 1) // a))
cnt = 0
bomb = 0
current_bomb = 0
while cnt < n:
    a, c, b = heappop(actions)
    if c:
        current_bomb -= b
        continue
    else:
        HP = b
        if HP <= current_bomb:
            cnt += 1
            continue
        else:
            HP -= current_bomb
            cnt += 1
            current_bomb += HP
            bomb += HP
            heappush(actions, (a + 2 * d, 1, HP))
print(bomb)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, d, a = list(map(int, readline().split()))
    xh = [list(map(int, readline().split())) for _ in range(n)]

    from operator import itemgetter, add
    import bisect

    xh.sort(key=itemgetter(0))
    coordinate = [xh[i][0] for i in range(n)]
    hp = [xh[i][1] for i in range(n)]

    ans = 0
    dmg_cur = 0
    dmg_cum = [0] * (n + 1)

    for i in range(n):
        x = coordinate[i]
        h = hp[i]

        dmg_cur += dmg_cum[i]
        h -= dmg_cur

        if h > 0:
            num = (h + a - 1) // a
            ans += num
            dmg = a * num
            dmg_cur += dmg
            range_left = x
            range_right = x + 2 * d
            index_right = bisect.bisect_right(coordinate, range_right)
            dmg_cum[index_right] -= dmg
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

dic={}

ans=0
atk_cnt=0
while B:
    x,h=heappop(B)
    if h==-1:
        atk_cnt-=dic[x-1]
        continue
    if h<=A*atk_cnt:
        continue
    h-=A*atk_cnt
    sup=x+2*D
    bomb=(h-1)//A+1
    ans+=bomb
    dic[sup]=bomb
    atk_cnt+=bomb
    heappush(B,(sup+1,-1))
    
    
print(ans)

Solution (Python):
from collections import deque
N, D, A = list(map(int, input().split()))
pair_xh = [[-1, -1] for _ in range(N)] 
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))
pair_xh.sort(key = lambda x: x[0]) 

q_lim_d = deque() 
total = 0 
count = 0 
for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    while len(q_lim_d) and q_lim_d[-1][0] < x: 
        total -= q_lim_d[-1][1]
        q_lim_d.pop()
    h -= total
    if h > 0: 
        times = (h + A - 1) // A 
        count += times
        damage = A * times
        total += damage
        q_lim_d.appendleft([x + 2 * D, damage])
print(count)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    down = [0] * (N+1)


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] += b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

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

ans = 0
att = [0]*n
cnt = 0
f = []
f1 = [0]*n

for x,h in xh:
    f.append(h)

for i in range(n):
    tmp = xh[i][0] + 2 * d
    while cnt < n:
        if xh[cnt][0] <= tmp:
            cnt += 1
        else:
            break
    att[i] = min(cnt-1, n-1)

for i in range(n):
    if f[i] > 0:
        da = -(-f[i]//a)
        ans += da
        f1[i] -= da * a
        if att[i]+1 < n:
            f1[att[i]+1] += da * a
    if i < n-1:
        f1[i+1] += f1[i]
        f[i+1] += f1[i+1]
print(ans)

Solution (Python):
import math
from collections import deque

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

xh_field = deque()

cnt = 0
now_damage = 0
while xh:
    pos, hp = xh.popleft()
    if xh_field:
        while (xh_field and xh_field[0][0] < pos) :
            now_damage -= a * xh_field[0][1]
            xh_field.popleft() 
    if hp <= now_damage:
        pass
    elif hp > now_damage:
        atk_cnt = math.ceil((hp - now_damage) / a)
        cnt += atk_cnt
        now_damage += atk_cnt * a
        xh_field.append((2*d + pos, atk_cnt))        
print(cnt)

Solution (Python):
import bisect

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

monsters = []
for i in range(N):
    X, H =map(int,input().split())
    monsters.append([X,H])

monsters = sorted(monsters)

id = 0
ans = 0

damage = [0 for i in range(N)]

while id < N:
    if id > 0: damage[id] += damage[id-1]
    nowX, nowH = monsters[id][0], monsters[id][1]
    nowH -= damage[id]

    if nowH > 0:
        damage[id] += A * ((nowH + A - 1) // A)

        right = bisect.bisect_left(monsters, [nowX+2*D+1,0])
        if right < N:
            damage[right] -= A * ((nowH + A - 1) // A)

        ans += (nowH + A -1) // A

    id += 1

print(ans)