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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = zip(*sorted(zip(m,m)))
    
    over = [-1]*N
    tmp=0
    for i in range(N):
      while(tmp<N and X[i]+D*2>=X[tmp]):
        tmp += 1
      over[i] = tmp
    reset = [0]*N
    
    ans = 0
    dam = 0
    for i in range(N):
      if i>0:
        reset[i] += reset[i-1]
      hp = H[i]-dam+reset[i]
      if hp > 0:
        bomb = (hp+A-1)//A
        ans += bomb
        dam += bomb * A
        if(over[i]<N):
          reset[over[i]] += bomb * A

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq as hq

N, D, A = map(int,input().split())
m = []
for i in range(N):
    hq.heappush(m, tuple(map(int,input().split())))
ans = 0
dmg = 0; d = []
while m:
    X, H = m[0]
    if not d or (X <= d[0][0]):
        if dmg < H:
            k = (H - dmg + A - 1) // A
            ans += k
            dmg += k * A
            hq.heappush(d, (X + 2 * D, - k * A))
        hq.heappop(m)
    else:
        dmg += d[0][1]
        hq.heappop(d)
    

print(ans)

Solution (Python):
import heapq as hq

N, D, A = map(int,input().split())
m = []
for i in range(N):
    hq.heappush(m, tuple(map(int,input().split())))
ans = 0
dmg = 0; d = []
while m:
    X, H = m[0] 
    if not d or (X <= d[0][0]):
        if dmg >= H:
            hq.heappop(m)
        else:
            k = (H - dmg + A - 1) // A
            ans += k
            dmg += k * A
            hq.heappush(d, (X + 2 * D, - k * A))
    else:
        dmg += d[0][1]
        hq.heappop(d)
    

print(ans)

Solution (Python):
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
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 sys import stdin
from collections import deque

n, d, a = (int(v) for v in stdin.readline().split())
monsters = [(int(v) for v in line.split()) for line in stdin.readlines()]

monsters = [[x, (h // a + 1) if h % a > 0 else (h // a)] for x, h in monsters]
monsters = sorted(monsters)
bomb_size = 2 * d + 1
num_bombs = 0

current_bombs = 0
bomb_endpoints = deque()
bomb_endnumbers = deque()

for i in range(len(monsters)):
    while len(bomb_endpoints) > 0 and bomb_endpoints[0] <= monsters[i][0]:
        current_bombs -= bomb_endnumbers[0]
        bomb_endpoints.popleft()
        bomb_endnumbers.popleft()
    monsters[i][1] -= current_bombs
    if monsters[i][1] > 0:        
        bombs_now = monsters[i][1]
        monsters[i][1] = 0
        num_bombs += bombs_now
        current_bombs += bombs_now
        bomb_endpoints.append(monsters[i][0] + bomb_size)
        bomb_endnumbers.append(bombs_now)

print(num_bombs)

Solution (Python):
import sys
import math

def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]
    xh = [[]] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    
    
    
    
    xh.sort()

    cur = 0
    right_indices = [0] * n
    for i in range(n):
        cur = max(cur, i)
        x, h = xh[i]
        right_val = x + d * 2
        while cur < n-1 and xh[cur+1][0] <= right_val:
            cur += 1
        right_indices[i] = cur

    imos = [0] * (n+1)
    ans = 0
    for i in range(n):
        if imos[i] < xh[i][1]:
            need = math.ceil((xh[i][1] - imos[i]) / a)
            ans += need
            imos[i] += need * a
            right_idx = right_indices[i]
            imos[right_idx+1] -= need * a
        imos[i+1] += imos[i]
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

N, D, A = map(int, input().split())
M = []
for i in range(N):
  x, h = map(int, input().split())
  M.append((x, -(-h//A)))
M.sort(key=lambda x: x[0])
X = list(map(lambda x: x[0], M))
H = list(map(lambda x: x[1], M))

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

for i in range(N):
  x, h = M[i]
  h = max(0, h - dmg[i])
  dmg[bisect_right(X, x + 2*D)] -= h
  dmg[i+1] += dmg[i] + h
  ans += h
print(ans)

Solution (Python):
import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  if h <= 0:
    continue
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)

Solution (Python):
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
d = [0]*(N+1)
for l in range(N):
  if d[l]<xh[l][1]:
    la = (xh[l][1]-d[l]+A-1)//A
    for _ in range(N):
      if l<N and r<N and 2*D>=xh[r][0]-xh[l][0]:
        r+=1
      else:
        break
    ans += la
    d[l]+=la*A
    d[r]-=la*A
  d[l+1]+=d[l]
print(ans)

Solution (Python):
def resolve():
    N, D, A = map(int, input().split())
    lXH = []
    while True:
        try:
            x, h = map(int, input().split())
            lXH.append([x, h])
        except:
            break
    lXHs = sorted(lXH, key=lambda k: k[0])
    from collections import deque
    q = deque()
    tot = 0
    ans = 0
    for i in range(N):
        x, h = lXHs[i]
        while len(q) > 0 and q[0][0] < x:
            qx, qh = q.popleft()
            tot -= qh
        h -= tot
        if h > 0:
            num = (h+A-1)//A
            ans += num
            dam = num*A
            tot += dam
            q.append([x+2*D, dam])
    print(ans)
resolve()

Solution (Python):


import bisect

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 = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
X_right = [bisect.bisect_right(X, XH[i][0] + 2*D) for i in range(N)]

ans = 0
bomb_damage = Bit(N+1)
for i in range(N):
    damage = bomb_damage.sum(i+1)
    if XH[i][1] - damage > 0:
        n_bomb = -(-(XH[i][1] - damage)//A)
        ans += n_bomb
        bomb_damage.add(i+1, n_bomb * A)
        bomb_damage.add(X_right[i]+1, -n_bomb * A)

print(ans)

Solution (Python):
def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()

Solution (Python):
def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()

Solution (Python):


import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT2:
    """ 区間加算BIT(区間加算・区間合計取得) """

    def __init__(self, N):
        
        N += 1
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N

    def _add(self, data, k, x):
        k += 1
        while k < self.N:
            data[k] += x
            k += k & -k

    def _get(self, data, k):
        k += 1
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """

        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def query(self, l, r):
        """ 区間[l,r)の和を取得 """

        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
             - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

N, D, K = MAP()

XH = []
for i in range(N):
    x, h = MAP()
    XH.append((x, h))

XH.sort()
X, H = zip(*XH)
D = D * 2

bit = BIT2(N)
ans = 0
for i, (x, h) in enumerate(XH):
    h -= bit.query(i, i+1) * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D) - 1
    bit.add(i, idx+1, cnt)
    ans += cnt
print(ans)

Solution (Python):


import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    
    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):
        """ 区間[l,r)の値にxを加算 """

        
        
        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 self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

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

N, D, K = MAP()

XH = []
for i in range(N):
    x, h = MAP()
    XH.append((x, h))

XH.sort()
X, H = zip(*XH)
D = D * 2

sst = StarrySkyTree(N, max, 0)
ans = 0
for i, (x, h) in enumerate(XH):
    h -= sst.query(i, i+1) * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D) - 1
    sst.update(i, idx+1, cnt)
    ans += cnt
print(ans)

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

def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]
    
    
    
    

    xh = [[]] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    xh.sort()

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n-1 and xh[cur+1][0] <= attack_rightmost:
            cur += 1
        attack_rightmost_idx[i] = cur

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = remaining_life // a
        if remaining_life % a:
            needed += 1
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = XH[::2] + [-1]
H = XH[1::2] + [-1]
D *= 2
X, H = zip(*sorted(zip(X, H)))

damages = [0] * (N + 2)
answer = 0

for i in range(1, N + 1):
    damages[i] += damages[i - 1]
    h = H[i]
    if damages[i] >= h:
        continue
    else:
        h -= damages[i]

    x = X[i]
    cnt = (h + A - 1) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D)] -= damage

print(answer)

Solution (Python):
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = XH[::2]
H = XH[1::2]
D *= 2
X, H = zip(*sorted(zip(X, H)))

damage = [0] * (N + 1)
answer = H[0] // A + min(1, H[0] % A)
damage[0] += A * answer
damage[bisect_right(X, X[0] + D)] -= A * answer

for i in range(1, N):
    damage[i] += damage[i - 1]
    h = H[i]
    x = X[i]
    if damage[i] >= h:
        continue
    else:
        h -= damage[i]

    cnt = h // A + min(1, h % A)
    answer += cnt
    damage[i] += A * cnt
    damage[bisect_right(X, x + D)] -= A * cnt

print(answer)

Solution (Python):
import sys
from collections import deque
 
input = sys.stdin.readline
 
N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])
 
XH.sort(key=lambda xh: xh[0])
que = deque()
D = 2*D
 
H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
que.append([XH[0][0]+D,a*A])
tot = a * A
ans = a
for i in range(1,N):
	while XH[i][0] > que[0][0] :
		tot -= que[0][1]
		que.popleft()
		if(len(que)==0): break
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)

Solution (Python):
import sys
from collections import deque
 
input = sys.stdin.readline
 
N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])
 
XH.sort(key=lambda xh: xh[0])
que = deque()
D = 2*D
 
H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
que.append([XH[0][0]+D,a*A])
tot = a * A
ans = a
for i in range(1,N):
	while XH[i][0] > que[0][0] :
		tot -= que[0][1]
		que.popleft()
		if(len(que)==0): break
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)

Solution (Python):
from collections import deque

N,D,A = map(int,input().split())
mons = [list(map(int,input().split())) for i in range(N)]
for i in range(N):
    mons[i][1] = (mons[i][1]+A-1)//A

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

damages = deque()
nowdmg = 0
ans = 0
for i in range(N):
    while len(damages) != 0:
        if mons[i][0] >= damages[0][0]+1:
            rec = damages.popleft()
            nowdmg += rec[1]
        else:
            break
    if mons[i][1]+nowdmg > 0:
        c = mons[i][1]+nowdmg
        ans += c
        damages.append([mons[i][0]+2*D,c])
        nowdmg -= c


print(ans)

Solution (Python):
import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
count = 0
min_x = 0
acm = [0] * (n + 1)
dif = [0] * (n + 1)
while min_x < n:
    place = x[min_x] + d
    num = (h[min_x] - acm[min_x + 1] - 1) // a + 1
    count += num
    dif[min_x] += num
    dif[bisect.bisect(x, place + d)] -= num
    for i in range(min_x, bisect.bisect(x, place + d)):
        acm[i + 1] = acm[i] + dif[i] * a
        if acm[i + 1] >= h[i]:
            min_x += 1
            continue
        else:
            break
print(count)

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

data = []
for _ in range(N):
	data.append(tuple(map(int, input().split())))

data.sort()

queue = []
i = 0
j = 0
total = 0
height = 0
while i < N:
	if j >= len(queue) or data[i][0] <= queue[j][0]:
		x, h = data[i]
		i += 1
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			queue.append((x + D * 2, count * A))
	else:
		height -= queue[j][1]
		j += 1

print(total)

Solution (Python):

from bisect import *
from collections import *
from heapq import *



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

lst=[]
bomb=[]
count=0
nowbomb=0
idx=0

for x,h in XH:
    
    if lst:
        while idx<len(lst) and lst[idx]<x-D:
            nowbomb-=bomb[idx]
            idx+=1
    
    a=h-nowbomb
    if a>0:

        b=a//A+(a%A>0)*1
        
        nowbomb+=b*A
        count+=b
        lst.append(x+D)
        bomb.append(b*A)

print(count)

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

que = deque([])
ans = 0
total = 0

for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue
    while que and XH[i][0] > que[0][0]:
        _, tmp = que.popleft()
        total -= tmp

    h -= total
    if h > 0:
        atk = (h + A - 1) // A
        damage = atk * A
        ans += atk
        total += damage
        que.append((x+2*D, damage))

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]
class StarrySkyTree:
    
    def __init__(self, N):
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.INF = 2**31 - 1
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    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):
        
        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 self.gindex(l, r):
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    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 = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


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
    ST = StarrySkyTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i,i+1)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
import bisect

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

XH = []
for i in range(N):
  x, h = map(int, input().split())
  XH.append([x, h])

XH.sort()



X = [-1]
H = [0]
for x, h in XH:
  X.append(x)
  H.append(h)




J = [0]
for x in X[1:]:
  J.append(bisect.bisect_left(X, x+W+1))


damage = [0]*(N+1)
ans = 0
for i in range(1, N+1):
  damage[i] += damage[i-1]
  H[i] -= damage[i]
  x, h = X[i], H[i]
  if h <= 0:
    continue
  
  count = -(-h//A)
  ans += count
  dmg = count*A
  damage[i] += dmg
  if J[i] <= N:
    damage[J[i]] -= dmg 

print(ans)

Solution (Python):
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=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)

not_imos=[0]*(n+1)
atk_n=0
ans=0
for i in range(n):
  atk_n-=not_imos[i]
  h[i]-=atk_n*a
  if h[i]<0:h[i]=0
  atk_i=0--h[i]//a
  ans+=atk_i
  atk_n+=atk_i
  not_imos[bisect_right(x,x[i]+d*2)]+=atk_i
print(ans)

Solution (Python):
def main():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    readline = sys.stdin.readline

    mon = namedtuple('mon', 'x h')

    N, D, A = map(int, readline().split())
    mons = []
    for _ in range(N):
        x, h = map(int, readline().split())
        mons.append(mon(x=x, h=h))
    mons.sort(key=attrgetter('x'))

    imos = [0] * (N + 1)

    bomb = 0
    j = 0
    for i, mon in enumerate(mons):
        while (j + 1 < N) and (mons[j + 1].x - mon.x) <= D * 2:
            j += 1
        count = max(0, (mon.h - imos[i] * A + A - 1) // A)
        bomb += count

        imos[i] += count
        imos[j + 1] -= count

        imos[i + 1] += imos[i]

    print(bomb)


if __name__ == '__main__':
    main()

Solution (Python):
N, D, A = map(int, input().split())
ys = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,-(-H//A)))
ys.sort(key=lambda x : x[0])
li = dmg = r = 0
hs = [0]*N
for i, (y, h) in enumerate(ys):
    while ys[li][0]+2*D < y:
        dmg -= hs[li]
        li += 1
    hs[i] = max(0, h-dmg)
    dmg += hs[i]
    r += hs[i]
print(r)

Solution (Python):
from subprocess import*
call(("pypy3","-c","""
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):
def main():
    from bisect import bisect_right as br
    n, d, a = map(int, input().split())
    xh = [list(map(int, input().split())) for _ in [0]*n]
    xh.sort()
    x_list = [x for x, h in xh]
    ac = [0]*(n+1)
    ans = 0
    temp = 0
    for i in range(n):
        j = xh[i][1]-temp
        if j > 0:
            atk_cnt = (j-1)//a+1
            k = br(x_list, x_list[i]+2*d)-1
            ac[i] += a*atk_cnt
            ac[k] -= a*atk_cnt
            ans += atk_cnt
        temp += ac[i]
    print(ans)


main()

Solution (Python):
import bisect

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

XH.sort()
X, H = zip(*XH)

K = [-(-h // A) for h in H]
L = [0] * (N + 2)

ans = 0
for i in range(N):
    L[i + 1] += L[i]
    s = max(K[i] - L[i + 1], 0)
    ans += s
    L[i + 1] += s
    L[bisect.bisect_right(X, X[i] + 2 * D) + 1] -= s

print(ans)

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

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,-(-H//A)))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = dmg = r = 0
hs2 = [0]*N
for i, (y, h) in enumerate(ys):
    while l < y:
        dmg -= hs2[li]
        li += 1
        l = ys[li][0] + 2*D
    hs2[i] = max(0, h-dmg)
    dmg += hs2[i]
    r += hs2[i]
print(r)

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])
lastX=X[-1][0] 
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
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])
lastX=X[-1][0] 
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)

Solution (Python):
from bisect import bisect_right
N,D,A = map(int,input().split(" "))
line = []
line_append = line.append
for i in range(N):
    x,h = map(int,input().split(" "))
    line_append((x,-(-h//A)))
line.sort()
X = list(map(lambda x: x[0],line))
dmg = [0 for _ in range(N+1)]
ans = 0
for i in range(N):
    x,h = line[i]
    h = max(0,h - dmg[i])
    dmg[i] += h
    dmg[bisect_right(X,x+2*D)] -= h
    dmg[i+1] += dmg[i]
    ans += h

print(ans)

Solution (Python):
from bisect import bisect_right
N,D,A = map(int,input().split(" "))
line = []
line_append = line.append
for i in range(N):
    x,h = map(int,input().split(" "))
    line_append((x,-(-h//A)))
line.sort()
X = list(map(lambda x: x[0],line))
dmg = [0 for _ in range(N+1)]
ans = 0
for i in range(N):
    x,h = line[i]
    h = max(0,h - dmg[i])
    dmg[i] += h
    dmg[bisect_right(X,x+2*D)] -= h
    dmg[i+1] += dmg[i]
    ans += h

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)