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 bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

data0=[0]*(n+1)
data1=[0]*(n+1)

def _add(data,k,x):
  while k<=n:
    data[k]+=x
    k+=k&-k

def add(l,r,x):
  _add(data0,l,-x*(l-1))
  _add(data0,r,x*(r-1))
  _add(data1,l,x)
  _add(data1,r,-x)

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

def query(l,r):
  return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)

x=[]
for i in range(n):
  x.append(l[i][0])
  add(i+1,i+2,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p+1,p+2)
  add(p+1,Right[p]+1,-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p+1,p+2)<=0:
    p+=1
    if p==n:
      break
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline().strip()

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

x = []
h = {} 
for _ in range(n):
    i, j = map(int, input().split())
    x.append(i)
    h[i] = j
x.sort()
x.append(x[-1] + 2*d + 1)


ans = 0
attack = [0 for _ in range(n+1)]
for i in range(n):
    attack[i] += attack[i-1]
    if attack[i] >= h[x[i]]:
        continue

    if (h[x[i]] - attack[i]) % a == 0:
        j = (h[x[i]] - attack[i]) // a
    else:
        j = (h[x[i]] - attack[i]) // a + 1
    attack[i] += a * j
    ans += j

    
    
    start = i + 1
    stop = n
    k = stop - start + 1
    while k > 1:
        if x[start + k//2 - 1] <= x[i] + 2*d:
            start += k//2
        else:
            stop = start + k//2 - 1
        k = stop - start + 1
    attack[start] -= a * j

print(ans)

Solution (Python):





'''
3 3 2
1 2
5 4
9 2
'''

from collections import deque

N, D, A = map(int, input().split())
a = sorted(list(map(int, input().split())) for _ in range(N))
D *= 2

bomb_queue = deque()
bomb_dmg = 0
ans = 0

for x, h in a:
    
    while bomb_queue and bomb_queue[0][0] < x:
        
        bomb_dmg -= bomb_queue.popleft()[1]

    
    h -= bomb_dmg
    if h > 0:
        
        cnt = (h + A - 1) // A
        ans += cnt
        
        
        bomb_queue.append((x + D, cnt * A))
        bomb_dmg += cnt * A

print(ans)

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]

atack = np.zeros(N+1, np.int64)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

Solution (Python):
from collections import deque
N, D, A = map(int, input().split())
XH = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort(key=lambda x: x[0])
D = 2 * D
tot = 0
q = deque()
ans = 0
for i in range(N):
    x, h = XH[i]
    while 0 < len(q) and q[0][0] < x:
        tot -= q[0][1]
        q.popleft()
    h -= tot
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        tot += damage
        q.append((x + D, damage))
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
    

def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 0
    rdi = 0
    bit = BinaryIndexedTree(n+1)
    for i in range(n):
        x, h = xh[i]
        h -= bit.sum(i)
        if h > 0:
            t = (h - 1) // a + 1
            for rdi in range(rdi, n):
                if x + 2 * d < xh[rdi][0]:
                    rdi -= 1
                    break
            ans += t
            bit.add(rdi + 1, -t * a)
            bit.add(i, t * a)

    print(ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

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

ans = 0
q = deque([])
tot = 0
for x, h in mons:
    while q:
        x0, h0 = next(iter(q))
        if x - 2 * D <= x0:
            break
        tot -= h0
        q.popleft()
    h = max(0, h - tot)
    ans += h
    tot += h
    q.append((x, h))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
from collections import deque
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0
q=deque()
q_sum = 0

for x,h in xh:
    while len(q) > 0:
        bx, bh = q[0]
        if bx < x:
            q.popleft()
            q_sum -= bh
        else:
            break
    h -= q_sum
    if h > 0:
        q.append((x+2*d, h))
        q_sum += h
        res += h

print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil
from bisect import bisect_right

n, d, a = map(int, readline().split())
xh = [list(map(int, readline().split())) for i in range(n)]
xh.sort()
imos = [0] * (n + 1)
cnt = 0
ans = 0
x = []
for i in range(n):
    xh[i][1] = ceil(xh[i][1] / a)
    x.append(xh[i][0])
for i in range(n):
    cnt += imos[i]
    n_h = xh[i][1] - cnt
    if n_h > 0:
        cnt += n_h
        ans += n_h
        imos[bisect_right(x, x[i] + 2 * d)] -= n_h
print(ans)

Solution (Python):
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

print(ans)

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    
    N, D, A = lr()
    monsters = []
    for _ in range(N):
        x, h = lr()
        monsters.append((x, h))

    monsters.sort()
    bomb = deque()
    answer = 0
    attack = 0
    for x, h in monsters:
        while bomb:
            if bomb[0][0] + D < x:
                attack -= bomb[0][1]
                bomb.popleft()
            else:
                break
        h -= attack
        if h > 0:
            t = -(-h//A)
            answer += t
            bomb.append((x + D, A * t))
            attack += A * t

    print(answer)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque

readline = sys.stdin.readline
sr = lambda: readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
attack = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            attack -= bomb[0][1]
            bomb.popleft()
        else:
            break
    h -= attack
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, A * t))
        attack += A * t

print(answer)

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
attack = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            attack -= bomb[0][1]
            bomb.popleft()
        else:
            break
    h -= attack
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, A * t))
        attack += A * t

print(answer)

Solution (Python):
import bisect
from collections import deque
import math
n, d, A = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
xh.sort(key=lambda x: x[0])

monster_x = []
monster_hp = []
for i in range(n):
    monster_x.append(xh[i][0])
    monster_hp.append(xh[i][1])

dist = 2 * d
ans = 0
damage = 0
cum_damage = [0] * (n + 1)
for i in range(n):
    cum_damage[i + 1] += cum_damage[i]
    damage = cum_damage[i + 1] * A
    if damage < monster_hp[i]:
        min_attack_num = math.ceil((monster_hp[i] - damage) / A) 
        index = bisect.bisect_right(monster_x, monster_x[i] + dist)
        cum_damage[i + 1] += min_attack_num
        if index < n:
            t = min(index + 1, n)
            cum_damage[t] -= min_attack_num
        ans += min_attack_num

print(ans)

Solution (Python):
import math
from collections import deque

N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, math.ceil(h/A)))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 
for i in range(N):
    x, h = data[i]

    
    while damage_que and x > damage_que[0][0]:
        _, a = damage_que.popleft()
        attack -= a
    
    
    remain = max(h - attack, 0)
    
    attack += remain
    c += remain

    
    damage_que.append([x+2*D, remain])

print(c)

Solution (Python):
from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])

POS = [v[0] for v in L]
ES = [0]*(N+1)
ans, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > c:
        t = L[i][1]-c
        ans += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(ans)

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

def main():
    def isok(z,val):
        return (z-val<=2*d)
    def bisect(ls,val): 
        ok = -1
        ng = len(ls)
        idx = (ok+ng)//2
        while ng-ok>1:
            num = ls[idx]
            if isok(num,val):
                ok = idx
            else:
                ng = idx
            idx = (ok+ng)//2
        return ok 

    n,d,a = map(int,input().split())
    mon = []
    for i in range(n):
        x,h = map(int,input().split())
        mon.append((x,h))
    mon.sort()
    keys = [ls[0] for ls in mon] 

    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        x,h = mon[i]
        res = h-damage[i]
        if res>0:
            c = ceil(res/a)
            ans+=c
            idx = bisect(keys,x) 
            if idx==-1:continue
            damage[i] +=a*c
            damage[idx+1] -=a*c
        damage[i+1] += damage[i]
    print(ans)
if __name__=="__main__":
    main()

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

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

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

monsters.sort()

attack = 0
que = deque([])
attack_num = 0

for monster in monsters:
    xx, hh = monster
    while que and que[0][0] < xx - d:
        attack -= que[0][1]
        que.popleft()

    

    if hh - attack <= 0:
        continue

    a_times = (hh - attack - 1) // a + 1
    attack_num += a_times
    attack += a_times * a
    que.append((xx + d, a_times * a))

    

print(attack_num)

Solution (Python):
import bisect

def main():
  N,D,A=map(int,input().split())
  m=sorted([int(j) for j in input().split()] for i in range(N))

  x=[m[i][0] for i in range(N)]
  es=[0]*(N+1)
  a,c=0,0
  for i in range(N):
    c-=es[i]
    if m[i][1]>A*c:
      t=(m[i][1]-A*c+A-1)//A
      a+=t
      c+=t
      es[bisect.bisect_right(x,x[i]+2*D)]+=t
  print(a)

main()

Solution (Python):
from math import ceil
from collections import deque
count = 0
ans = 0

N, D, A = map(int, input().split())
Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))
Monster = [[x, ceil(h/A)] for x, h in Monster]
Monster.sort()
que = deque([])

for x,h in Monster:
    
    while que and x > que[0][0]:
        a, b = que.popleft()
        count -= b
    
    need = max(0, h-count)
    ans += need
    count += need
    
    que.append([x + 2*D, need])
print(ans)

Solution (Python):
import bisect
n,d,a = map(int,input().split())
lst = []
x = []
for i in range(n):
    xi,hi = map(int,input().split())
    lst.append([xi,hi,0])
    x.append(xi)
lst.sort()
x.sort()
count = 0
cur = 0
for i in range(n):
    if lst[i][1]-cur > 0:
        num = -(-(lst[i][1]-cur)//a)
        count += num
        damage = a * num
        cur += damage
        index = bisect.bisect(x,x[i]+2*d)
        if index != n:
            lst[index-1][2] += damage
    cur -= lst[i][2]
print(count)

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())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

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())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):

import sys
import math
from collections import deque


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    revert = deque()
    currentDamage = 0
    for m in M:
        while len(revert) > 0 and revert[0][0] < m[0]:
            currentDamage -= revert[0][1]
            revert.popleft()
        nextDamage = max(0, m[1] - currentDamage)
        needAttack = math.ceil(nextDamage/A)
        currentDamage += needAttack * A
        result += needAttack
        if needAttack > 0:
            revert.append((m[0]+2*D, needAttack*A))
    print(result)
    return



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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
from collections import deque


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    revert = deque()
    currentDamage = 0
    for m in M:
        while len(revert) > 0 and revert[0][0] < m[0]:
            currentDamage -= revert[0][1]
            revert.popleft()
        nextDamage = max(0, m[1] - currentDamage)
        needAttack = math.ceil(nextDamage/A)
        currentDamage += needAttack * A
        result += needAttack
        if needAttack > 0:
            revert.append((m[0]+2*D, needAttack*A))
    print(result)
    return



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


if __name__ == '__main__':
    main()

Solution (Python):
import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)

Solution (Python):
import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)

Solution (Python):
from math import ceil
from collections import deque
n,d,a = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(n)]
m.sort()
l = [(x, ceil(h/a)) for x,h in m]

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

for x,h in l:
    while que and que[0][0] < x:
            s,t = que.popleft()
            damage -= t
    need = max(0, h - damage)
    ans += need
    damage += need
    if need:
        que.append((x+2*d, need))
print(ans)

Solution (Python):
import sys
from bisect import bisect_right

sys.setrecursionlimit(500000)


class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)
 
    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = 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 = ret + self.data[i]
        return ret

def main():
    N, D, A = map(int, input().split())
    monsters = []

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

    seg = DualSegmentTree(N)
    monsters.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = monsters[i]
    ans = 0
    for i in range(N):
        tmp_dist = monsters[i][0] + 2 * D
        tmp_hp = int(monsters[i][1] - seg.query(i))
        if tmp_hp <= 0:
            continue
        idx = bisect_right(X, tmp_dist)
        cnt = tmp_hp // A if tmp_hp % A == 0 else tmp_hp // A + 1
        ans += cnt
        seg.update(i,idx,cnt*A)

    print(ans)
    


    


if __name__ == "__main__":
    main()

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

monster.sort()

H=[monster[i][1] for i in range(0,N)]

right_2d=[0 for i in range(0,N)]
for i in range(0,N):
    start=i
    end=N-1
    while end-start>1:
        test=(end+start)//2
        if 2*D+monster[i][0]>=monster[test][0]:
            start=test
        else:
            end=test
    if 2*D+monster[i][0]>=monster[end][0]:
        right_2d[i]=end
    else:
        right_2d[i]=start

imos=[0 for i in range(0,N+1)]
ans=0
for i in range(0,N):
    H[i]-=imos[i]
    if H[i]>0:
        count=(H[i]+A-1)//A
        ans+=count
        imos[i]+=A*count
        imos[right_2d[i]+1]-=A*count

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

print(ans)

Solution (Python):

from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)

Solution (Python):


import bisect

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

log=[]
loc=[]
ene=[]

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

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

for X,H in log:
    loc.append(X)
    ene.append(H)

syokan=[0]*N

power=0
for i in range(N):
    temp=max(-((-ene[i]+power)//A),0)*A
    power+=temp
    
    rng=bisect.bisect_right(loc,loc[i]+2*D)
    syokan[min(rng-1,N-1)]+=temp
    
    power-=syokan[i]
    

print(sum(syokan)//A)

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

xh.sort()
j = 0
cnt = [0] * n
taken = 0








for i in range(n):
    [x,h] = xh[i]
    while xh[j][0] + 2*d < x:
        taken -= cnt[j]
        j += 1
    if taken * a >= h:
        continue
    if h % a == 0:
        cnt[i] = h//a - taken
    else:
        cnt[i] = h//a - taken + 1
    
    taken += cnt[i]
print(sum(cnt))

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

xh.sort()
j = 0
cnt = [0] * n
taken = 0

def problem(h):
    if h <= 0:return 0
    ans = h//a
    if h%a :
        ans += 1
    return ans

for i in range(n):
    [x,h] = xh[i]
    while xh[j][0] + 2*d < x:
        taken -= cnt[j]
        j += 1
    
    
    
    
    
    
    cnt[i] = problem(h - taken * a)
    taken += cnt[i]
print(sum(cnt))

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

m.sort()

x = [s[0] for s in m]
h = [s[1] for s in m]

dh = [0] * (n+1)
dh[0] = h[0]
for i in range(n-1):
    dh[i+1] = h[i+1] - h[i]

import bisect
ans = 0
health = 0
for i in range(n):
    health += dh[i]
    if health > 0:
        count = (health + a - 1) // a
        damage = count * a
        ans += count
        health -= damage
        r = bisect.bisect_right(x, x[i] + 2 * d)
        dh[r] += damage
print(ans)

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

n, d, a = map(int, input().split())
monster = [tuple(map(int, input().split())) for _ in range(n)]
monster.sort(key=itemgetter(0))
xx = [xi for xi, hi in monster]


d_range = [-1] * n
idx = 0
for i, (xi, hi) in enumerate(monster):
    while idx < n and xx[idx] - xi <= 2 * d:
        idx += 1
    d_range[i] = idx

ans = 0
imos = [0] * (n + 1)
for i, (xi, hi) in enumerate(monster):
    hi -= imos[i]
    if hi > 0:
        c = (hi + a - 1) // a
        ans += c
        idx = d_range[i]
        imos[i] += c * a
        imos[idx] -= c * a

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

print(ans)