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

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, D, A = map(int, input().split())
    XH = [None] * N
    X = [None] * N

    for i in range(N):
        XH[i] = tuple(map(int, input().split()))
        X[i] = XH[i][0]

    XH.sort()
    X.sort()
    
    ans = 0
    S = [0] * (N+1)
    for i in range(N):
        if S[i] < XH[i][1]:
            
            need = (XH[i][1]-S[i]+A-1)//A
            
            j = bisect_right(X,X[i]+2*D)
            
            S[i] += need*A
            S[j] -= need*A
            ans += need
        S[i+1] += S[i]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())

Solution (Python):
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    explosion = FIFO deque and damage, range
    """
    N, D, A = read_ints()
    XH = []
    for _ in range(N):
        XH.append(read_ints())
    XH.sort()
    explosion = deque([])
    current_damage = 0
    count = 0
    for i in range(N):
        while len(explosion) != 0 and explosion[0][1] < XH[i][0]:
            current_damage -= explosion.popleft()[0]
        if current_damage < XH[i][1]: 
            left_health = XH[i][1]-current_damage
            more_bombs = (left_health//A+(1 if left_health%A != 0 else 0))
            count += more_bombs
            more_damage = more_bombs*A
            current_damage += more_damage
            explosion.append((more_damage, XH[i][0]+2*D))
    return count


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, D, A = in_nn()
    XH = sorted(in_nl2(N))
    X = [0] * N
    H = [0] * N

    for i in range(N):
        x, h = XH[i]
        X[i] = x
        H[i] = h

    bit = Bit(N)

    ans = 0
    for i in range(N):

        x, h = X[i], H[i]
        j = bisect.bisect_right(X, x + 2 * D)
        cnt_bomb = bit.sum(i + 1)

        h -= A * cnt_bomb
        if h <= 0:
            continue

        cnt = -(-h // A)
        ans += cnt
        bit.add(i + 1, cnt)
        bit.add(j + 1, -cnt)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, D, A = in_nn()
    XH = sorted(in_nl2(N))
    X = [0] * N
    H = [0] * N

    for i in range(N):
        x, h = XH[i]
        X[i] = x
        H[i] = h

    bit = Bit(N)

    ans = 0
    for i in range(N):

        x, h = X[i], H[i]
        j = bisect.bisect_right(X, x + 2 * D)
        cnt_bomb = bit.sum(i + 1)

        h -= A * cnt_bomb
        if h <= 0:
            continue

        cnt = -(-h // A)
        ans += cnt
        bit.add(i + 1, cnt)
        bit.add(j + 1, -cnt)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

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

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res


def main():

    N, D, A = in_nn()
    XH = sorted(in_nl2(N))
    X = [0] * N
    H = [0] * N

    for i in range(N):
        x, h = XH[i]
        X[i] = x
        H[i] = h

    seg = SegTree([0] * N, segfunc=lambda a, b: a + b, ide_ele=0)

    ans = 0
    for i in range(N):

        x, h = X[i], H[i]
        j = bisect.bisect_right(X, x + 2 * D)
        cnt_bomb = seg.query(0, i + 1)

        h -= A * cnt_bomb
        if h <= 0:
            continue

        cnt = -(-h // A)
        ans += cnt
        seg.update(i, cnt)

        if j < N:
            seg.update(j, -cnt)

        
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import *

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

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

X = []
H = []
for x, h in data:
    X.append(x)
    H.append(h)

Imos = [0]*(N+1)
cnt = 0
damage = 0
res = 0
for i in range(N):
    damage -= Imos[i]*A
    h = H[i] - damage
    x = X[i]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = min(bisect_right(X, x+2*D)-1, N-1)
        Imos[p+1] += cnt
        damage = damage + cnt * A
        res += cnt
print(res)

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

hit = []

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

que = []
ans = 0
bomb = 0
for i in range(n):
  while True:
    if len(que) == 0:
      break
    if hit[i][0] <= que[0][0]:
      break
    bomb -= que[0][1]
    que.pop(0)
  r = hit[i][1] - bomb
  if r < 0:
    continue
  c = (r + a - 1)//a
  ans += c
  bomb += c*a
  que.append((hit[i][0]+2*d,c*a))
print (ans)

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

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

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

N,d,a=LI()


INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    arr=[]
    for i in range(LV):
        if rc <= i:
            arr.append(R)
        if L < R and lc <= i:
            arr.append(L)
        L >>= 1; R >>= 1
    return arr


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])


def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
    

show_flg=False
show_flg=True

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

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

print(ans)

Solution (Python):
import bisect


def main():
    N, D, A = list(map(int, input().split()))
    monsters = [list(map(int, input().split())) for _ in range(N)]
    monsters.sort()
    X = [m[0] for m in monsters]
    
    ans = 0
    damages = [0] * (N + 1)
    for n, monster in enumerate(monsters):
        x, h = monster
        h = max(0, h - damages[n])
        to_n = bisect.bisect_right(X, x + 2 * D)
        cnt = (h + A - 1) // A  
        ans += cnt
        damages[n] += A * cnt
        damages[to_n] -= A * cnt
        damages[n + 1] += damages[n]
    print(ans)


if __name__ == '__main__':
    main()

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


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

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])

bombs = deque()

ans = 0
valid_bomb = 0
for pos, hp in ms:
    
    while bombs and bombs[0][0] < pos:
        bomb_border, bomb_cnt = bombs.popleft()
        valid_bomb -= bomb_cnt
    
    
    bomb_cnt = max(0, hp - valid_bomb)
    valid_bomb += bomb_cnt
    ans += bomb_cnt
    
    
    if bomb_cnt > 0:
        bombs.append([pos + d * 2, bomb_cnt])
 
print(ans)

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


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

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])
 
bombs = deque()
 
ans = 0
valid_bomb = 0
for pos, hp in ms:
  
  while bombs and bombs[0][0] < pos:
    bomb_border, bomb_cnt = bombs.popleft()
    valid_bomb -= bomb_cnt
  
  
  bomb_cnt = max(0, hp - valid_bomb)
  valid_bomb += bomb_cnt
  ans += bomb_cnt
  
  
  if bomb_cnt > 0:
    bombs.append([pos + d * 2, bomb_cnt])
 
print(ans)

Solution (Python):
from collections import deque
from math import ceil
 
n,d,a = map(int,input().split())
M = [list(map(int,input().split())) for i in range(n)]
M = sorted([(x,ceil(h/a)) for x,h in M])
 
que = deque()
 
ans = 0
atack = 0
for x,h in M:
  while len(que) > 0 and que[0][0] < x:
    tx,ta = que.popleft()
    atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  if bomb_num > 0:
    que.append([x+d*2,bomb_num])
 
print(ans)

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

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

que = deque()

ans = 0
atack = 0
for x,h in M:
  while len(que) > 0 and que[0][0] < x:
    tx,ta = que.popleft()
    atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  if bomb_num > 0:
    que.append([x+d*2,bomb_num])

print(ans)

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

que = deque()
cur = 0
ans = 0
for x,h in monsters:
  while que and x > que[0][0]:
    _,n = que.popleft()
    cur -= n

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

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

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
      l, r = l >> 1, r >> 1
      
N,D,A = IL()
data = ILL(N)
data.sort()
PLACE = [d[0] for d in data]
HP = [-(-d[1]//A) for d in data]
MAKIKOMI = []
for i in range(N):
  x = PLACE[i]
  p  = bisect.bisect(PLACE,x+2*D)
  MAKIKOMI.append(p-i)

ST = SegmentTree(N,0)
ST.build(HP)
ans = 0
now = 0
while now < N:
  while ST.get(now) > 0:
    t = ST.get(now)
    ans += t
    ST.add(now,now+MAKIKOMI[now],-t)
  now += 1
print(ans)

Solution (Python):
from math import ceil
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])
ans = 0

XN = [[x, ceil(h/A)] for x, h in XH]

cnum = 0
que = deque()
ans = 0
for x, n in XN:
    while que and x > que[0][0]:
        _, num = que.popleft()
        cnum -= num
    need = max(0, n - cnum)
    ans += need
    cnum += need

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

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, D, A = NMI()
    M = [NLI() for _ in range(N)]
    M.sort()
    maxj = [0] * N
    j = 0
    for i in range(N):
        while j < N-1:
            if M[j+1][0] <= M[i][0] + D*2:
                j += 1
            else:
                break
        maxj[i] = j
    S = [0]*(N+1)
    ans = 0
    for i in range(N):
        x = M[i][0]
        hp = M[i][1] - S[i]
        need = max((hp-1) // A + 1, 0)
        ans += need
        S[i] += need * A
        S[maxj[i]+1] -= need * A
        S[i+1] += S[i]

    print(ans)





if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

n,d,a = map(int, input().split())
xhl = []
for _ in range(n):
    x,h = map(int, input().split())
    cnt = (h-1)//a + 1
    xhl.append((x,cnt))

xhl.sort()

attack_q = deque([])
attack_sum = 0
ans = 0
for x,h in xhl:
    
    
    
    while attack_q and attack_q[0][0] < x:
        poped_cnt = attack_q.popleft()[1]
        attack_sum -= poped_cnt
    
    
    rem = h-attack_sum
    if rem <= 0:
        continue
    attack_sum += rem
    ans += rem
    attack_q.append((x+2*d, rem))
    

print(ans)

Solution (Python):
from math import ceil
N,D,A = list(map(int, input().split()))
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
  

P.sort()



  

Attack = [-1 for _ in range(N)]
leftx, leftj = 0,0
for i in range(N):
  now = P[i][0]
  leftx = now + 2*D
  while leftj < N:
    if P[leftj][0] <= leftx:
      leftj += 1
    else:
      break
  Attack[i] = leftj - 1
  




wk_dam = 0
imos = [0] * (N+1)
ans = 0
for i in range(N):
  wk_dam += imos[i]
  
  if P[i][1] <= wk_dam:
    
    continue
  cnt = (P[i][1] - wk_dam + A-1) // A 
  wk_dam += cnt * A
  imos[i] += cnt * A
  imos[Attack[i]+1] -= cnt * A
  ans += cnt
  
print(ans)

Solution (Python):
from math import ceil
N,D,A = list(map(int, input().split()))
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
  

P.sort()



  

Attack = [-1 for _ in range(N)]
leftx, leftj = 0,0
for i in range(N):
  now = P[i][0]
  leftx = now + 2*D
  while leftj < N:
    if P[leftj][0] <= leftx:
      leftj += 1
    else:
      break
  Attack[i] = leftj - 1
  




wk_dam = 0
imos = [0] * (N+1)
ans = 0
for i in range(N):
  wk_dam += imos[i]
  
  if P[i][1] <= wk_dam:
    
    continue
  cnt = (P[i][1] - wk_dam + A-1) // A 
  wk_dam += cnt * A
  imos[i] += cnt * A
  imos[Attack[i]+1] -= cnt * A
  ans += cnt
  
print(ans)

Solution (Python):


class LasySegmentTree:
    def __init__(self, size: int, segfunc, lazy_ide_ele=0):
        self.lazy_ide_ele = lazy_ide_ele
        self.segfunc = segfunc
        self.N0 = 1 << (size - 1).bit_length()
        self.lazy = [self.lazy_ide_ele] * (2 * self.N0)

    def gindex(self, left, right):
        L = left + self.N0
        R = right + 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):
            idx = i - 1
            v = self.lazy[idx]
            if v == self.lazy_ide_ele:
                continue
            self.lazy[2 * idx + 1] = self.segfunc(self.lazy[2 * idx + 1], v)
            self.lazy[2 * idx + 2] = self.segfunc(self.lazy[2 * idx + 2], v)
            self.lazy[idx] = self.lazy_ide_ele

    def update(self, left: int, right: int, x):
        L = self.N0 + left
        R = self.N0 + right

        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] = self.segfunc(self.lazy[R - 1], x)
            if L & 1:
                self.lazy[L - 1] = self.segfunc(self.lazy[L - 1], x)
                L += 1
            L >>= 1
            R >>= 1

    def query(self, k: int):
        self.propagates(*self.gindex(k, k + 1))
        return self.lazy[k + self.N0 - 1]



from operator import add
from bisect import bisect_right
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    X, _ = zip(*AB)


    seg_lazy = LasySegmentTree(N+10, segfunc=add)
    ans = 0
    for i in range(N):
        d = AB[i][1] - seg_lazy.query(i)
        if d <= 0:
            continue
        cnt = -(-d//A)
        ans += cnt
        idx = bisect_right(X, (X[i] + 2*D))
        seg_lazy.update(i, idx, cnt*A)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):

import operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size



from bisect import bisect_right
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    X, _ = zip(*AB)
    D = 2*D

    seg = SegmentTree(N+10)
    ans = 0
    for i, (x, h) in enumerate(AB):
        h = -(-h // A)
        damage = seg.get(0, i+1)

        if h < damage:
            continue
        ans += h - damage
        seg.add(i, h-damage)
        seg.add(bisect_right(X, x + D), - h + damage)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):

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

    
    imos = [0] * (N+1)
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] <= 2 * D + x:
                R += 1
            d = h - imos[l]
            cnt = -(-d//A) 
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()