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 bisect import bisect_right, bisect_left

class BITbisect():
    def __init__(self, InputProbNumbers):
        
        self.ind_to_co = [-10**18]
        self.co_to_ind = {}
        for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind+1
        self.max = len(self.co_to_ind)
        self.data = [0]*(self.max+1)
    
    def __str__(self):
        retList = []
        for i in range(1, self.max+1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return "[" + ", ".join([str(a) for a in retList]) + "]"
    
    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < key:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max or key < 0:
            raise IndexError("BIT index out of range")
        return self.ind_to_co[ind+1]
    
    def __len__(self):
        return self._query_sum(self.max)
    
    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0
    
    
    
    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    
    
    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i
    
    def add(self, co, x):
        i = self.co_to_ind[co]
        while i > 0:
            self.data[i] += x
            i -= i & -i
    
    def now(self, x):
        i = self.co_to_ind[x]
        ret = 0
        while i <= self.max:
            ret += self.data[i]
            i += i & -i
        return ret
    
    
    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The pushing number didnt initialized")
        self._add(self.co_to_ind[x], 1)
            
    
    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The deleting number didnt initialized")
        if self.count(x) <= 0:
            raise ValueError("The deleting number doesnt exist")
        self._add(self.co_to_ind[x], -1)

    
    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)
    
    
    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    
    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i-1)

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
if D == 0:
    ans = 0
    for x, h in XH:
        ans += (h+A-1)//A
else:
    XH.sort()
    Input = []
    for x, h in XH:
        Input.append(x)

    Input.sort()

    bit = BITbisect(Input)
    ans = 0
    for x, h in XH:
        now = bit.now(x)
        if now >= h: continue
        count = (h-now+A-1)//A
        ans += count
        nx = Input[bisect_right(Input, x+2*D)-1]
        bit.add(nx, A*count)

print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import bisect

INF = float("inf")
con = 10 ** 9 + 7

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


def main():
	N, D, A = getlist()
	XH = []
	for i in range(N):
		X, H = getlist()
		XH.append([X, H])
	XH = sorted(XH)
	X = []
	H = []
	for i in range(N):
		X.append(XH[i][0])
		H.append(XH[i][1])

	X.append(INF)

	
	for i in range(N):
		h = H[i]
		if h % A == 0:
			H[i] = int(h // A)
		else:
			H[i] = int(h // A) + 1

	imos = [0] * (N + 1)
	ans = 0
	x = bisect.bisect_right(X, X[0] + 2 * D)
	imos[0] -= H[0]
	imos[x] += H[0]
	ans += H[0]
	for i in range(N - 1):
		imos[i + 1] += imos[i]
		if H[i + 1] + imos[i + 1] > 0:
			x = bisect.bisect_right(X, X[i + 1] + 2 * D)
			ans += H[i + 1] + imos[i + 1]
			imos[x] += H[i + 1] + imos[i + 1]
			imos[i + 1] = -H[i + 1]
	
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
import sys
input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Solution (Python):
n, d, a = map(int, input().split())
d *= 2
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
x = [0] * n
h = [0] * n
for i in range(n):
    x[i], h[i] = l[i]
    h[i] = (h[i] - 1) // a + 1
t = 0
r = 0
ans = 0
for l in range(n):
    tmp = 0
    while r < n and x[r] - x[l] <= d:
        h[r] -= t
        t += max(h[r], 0)
        tmp += max(h[r], 0)
        r += 1
    t -= max(h[l], 0)
    ans += tmp
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_right
def main():
    N, D, A = map( int, input().split())
    XH = []
    X = []
    for _ in range(N):
        x, h = map( int, input().split())
        XH.append( (x, (h+(A-1))//A))
        X.append(x)
    XH.sort()
    X.sort()
    T = [0]*(N+1)
    j = 0
    now = 0
    ans = 0
    for i in range(N):
        x, h = XH[i]
        now -= T[i]
        if now >= h:
            continue
        else:
            T[ bisect_right(X,x+D*2)] += h-now
            ans += h - now
            now = h
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


from collections import deque


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

    order = sorted(range(n), key=lambda idx: x[idx])
    res = 0
    sub = 0
    bounds = deque()
    for idx in order:
        while bounds and x[idx] > bounds[0][0]:
            bound, count = bounds.popleft()
            sub -= count
        h[idx] -= sub
        if h[idx] > 0:
            bound = x[idx] + 2 * d
            count = (h[idx] + a - 1) // a
            sub += count * a
            bounds.append((bound, a * count))
            res += count

    print(res)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    from bisect import bisect_left
    from operator import itemgetter

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

    xh = []
    xs = set()
    for _ in range(N):
        x, h = map(int, input().split())
        xh.append((x, h))
        xs.add(x)
        xs.add(x + D)
        xs.add(x + D * 2)

    xh.sort(key=itemgetter(0), reverse=True)

    *xs, = sorted(xs)

    imos = [0] * (len(xs) + 10)
    mons = [0] * (len(xs) + 10)
    for x, h in xh:
        i = bisect_left(xs, x)
        mons[i] += h

    ret = 0
    for i in range(len(xs) + 1):
        d = (mons[i] - imos[i] + A - 1) // A
        if d > 0:
            ret += d
            imos[i] += d * A
            imos[bisect_left(xs, xs[i] + D * 2) + 1] -= d * A
        imos[i + 1] += imos[i]

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
N,D,A=map(int,input().split())
XH=sorted([list(map(int,input().split())) for i in range(N)])
l,r=0,0
a=0
dp=0
dm=[0]*(N+1)
while l<N:
    while r<N and XH[r][0]<=XH[l][0]+2*D:
        r+=1
    dp+=dm[l]
    x=-(-max(0,XH[l][1]-dp)//A)
    a+=x
    dp+=x*A
    dm[r]-=x*A
    l+=1
print(a)

Solution (Python):
import sys
input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Solution (Python):

import sys
from bisect import bisect_left
INF = float("inf")


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


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):

    bit = Bit(N+1)

    XH = [(x, h) for x, h in zip(X, H)]
    XH.sort()
    for i in range(N):
        if i == 0:
            bit.add(i+1, XH[i][1])
        else:
            bit.add(i+1, XH[i][1]-XH[i-1][1])
    

    tot = 0
    curr = 0
    while True:
        
        

        flag = False
        for i in range(curr, N):
            if bit.sum(i+1) > 0:
                flag = True
                break
        if flag:
            curr = i+1
        else:
            break
        
        x, h = XH[i]
        h = bit.sum(i+1)
        kaisu = -(-h//A)
        damage = A*kaisu
        tot += kaisu

        
        j = bisect_left(XH, (x+2*D+1, 0))
        bit.add(i+1, -damage)
        bit.add(j+1, +damage)
        
        
        
    print(tot)
    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):
n, d, a = [int(s) for s in input().strip().split()]
X, H = [0] * n, [0] * n
for i in range(n):
    X[i], H[i] = [int(s) for s in input().strip().split()]

result = 0
monsters = sorted(zip(X, H))
q = []
ptr = 0
delta = 0
for x, h in monsters:
    while ptr < len(q) and q[ptr][0] < x:
        delta += q[ptr][1]
        ptr += 1
    h += delta
    if h <= 0:
        continue
    result += (h + a - 1) // a
    delta -= (h + a - 1) // a * a
    q.append((x + 2 * d, (h + a - 1) // a * a))
print(result)

Solution (Python):

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(X, x+D*2+1)
    cnt[j]+=n*A
    res += n*A
    ans+=n
print(ans)

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

XH.sort()

B=0
Bt=[0]*N
Bx=[0]*N
l=0
r=-1

ans=0
for i in range(N):
    x,h = XH[i]
    if h<=0: continue
    
    while l<=r:
        if Bx[l]<x: 
            B-=Bt[l]*A
            l+=1
        else: 
            break
    h-=B
    if h>0:
        t=(h+A-1)//A 
        ans+=t
        r+=1
        Bt[r]=t
        Bx[r]=x+(2*D)
        B+=A*t

print(ans)

Solution (Python):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, D, A = map(int, input().split())
a = []
b = []
res = 0
for _ in range(N):
  x, h = map(int, input().split())
  a.append([x, h])
  b.append(x)
a.sort(key = lambda x: x[0])
b.sort()
imos = [0] * (N + 2)
for i in range(N):
  a[i][1] += imos[i]
  imos[i + 1] += imos[i]
  if a[i][1] <= 0: continue
  l = a[i][0]
  r = a[i][0] + 2 * D
  t = bl(b, r)
  if t < N:
    if b[t] > r: t -= 1
  x = -(-a[i][1] // A)
  imos[i + 1] -= A * x
  imos[t + 1] += A * x
  a[i][1] = 0
  res += x
  
  


print(res)

"""
AtCoderレートで全ての優劣が決定される異世界ベラルーシ。
ここでは他世界からの転生者は「旅行者 - tourist -」と呼ばれる。

不幸な交通事故から、社長 高橋直小はベラルーシに異世界転生してしまった。
"""

Solution (Python):
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
monster=[]
for i in range(n):
    x,h=map(int,input().split())
    monster.append((x,h))
monster.sort()
x_list=[]
h_list=[]
for i in monster:
    x_list.append(i[0])
    h_list.append(i[1])
ans=0
import bisect
damage=[0]
for i in range(n):
    p=bisect.bisect_left(x_list,x_list[i]-2*d)
    D=damage[i]-damage[p]
    if h_list[i]<=D:
        damage.append(damage[-1])
        continue
    r=h_list[i]-D
    c=(r+a-1)//a
    ans+=c
    damage.append(damage[-1]+a*c)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res

def solve():

    n,d,a = LI()
    p = LIR(n)
    ans = 0
    p.sort()
    X = [p[i][0] for i in range(n)]
    s = SegmentTree(n,0)
    for i in range(n):
        x,h = p[i]
        j = bisect.bisect_left(X,x-2*d)
        if i != j:
            su = s.get(j,i)
            h -=  s.get(j,i)
        if h > 0:
            l = x
            k = math.ceil(h/a)
            ans += k
            s.update(i,k*a)
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

Solution (Python):
import math
from heapq import heappop, heappush
N, D, A = map(int, input().split())
D *= 2
enemies = []
for _ in range(N):
    x, h = map(int, input().split())
    enemies.append((x, math.ceil(h / A)))
enemies.sort()

t = 0
ans = 0
attacks = []
attacksum = 0
for f in range(N):
    x, h = enemies[f]
    while attacks:
        if x > attacks[0][0]:
            ax, ad = heappop(attacks)
            attacksum -= ad
        else:
            break
    if h <= attacksum:
        continue
    damage = h - attacksum
    attacksum += damage
    ans += damage
    heappush(attacks, (x + D, damage))

print(ans)

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

bombloc = [-1]
bombdam = [ 0]
nbomb = 1
ibomb = 0 
damage = 0
ans = 0
for x, h in XH:
    while ibomb<nbomb and bombloc[ibomb]+D<x:
        damage -= bombdam[ibomb]
        ibomb+=1
        
    h_remain = h-damage
    if h_remain<=0: continue

    n = (h_remain+A-1)//A
    bombloc.append(x+D)
    bombdam.append(n*A)
    nbomb += 1
    damage += n*A
    ans += n
    
print(ans)

Solution (Python):
import sys,bisect
input = sys.stdin.readline
n,d,a = map(int,input().split())

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

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


ide_ele = 0


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


xh = []
dg = 10**10

for i in range(n):
    x,h = map(int,input().split())
    xh.append(x*dg+h)

xh.sort()

res = 0

for i in range(n):
    x,h = xh[i]//dg,xh[i]%dg
    k1 = bisect.bisect_left(xh,(x-2*d)*dg)
    
    r = query(k1,i)

    h -= r*a
    if h <= 0:
        continue

    if h%a == 0:
        res += h//a
        update(i,h//a)
    else:
        res += h//a+1
        update(i,h//a+1)
    
print(res)

Solution (Python):
n, d, a = [int(i) for i in input().split()]
xh = [[int(i) for i in input().split()] for _ in range(n)]
xh.sort()
da = [0] * n
r = [0] * n
ru=0

ans = 0
j=0
for i in range(n):
    da[i]+=ru
    if xh[i][1] > da[i]:
        up = (xh[i][1] - da[i]) // a
        if (xh[i][1] - da[i]) % a != 0:
            up += 1
        ans += up
        up *= a
        da[i] += up
        ru+=up
        
        while j!=n-1 and xh[j+1][0] <= xh[i][0] + 2 * d:
            j += 1
        r[j]+=up
    
    ru-=r[i]
print(ans)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n, d, a = MI()
    hp = []
    for _ in range(n):
        x, h = MI()
        heappush(hp, (x, 1, h))
    p = 0
    ans = 0
    while hp:
        x, op, h = heappop(hp)
        if op:
            h -= p
            if h > 0:
                ad = (h + a - 1) // a
                ans += ad
                p += ad * a
                heappush(hp, (x + 2 * d + 1, 0, ad * a))
        else:
            p -= h

    print(ans)

main()

Solution (Python):
import math
from heapq import heappop, heappush
N, D, A = map(int, input().split())
D *= 2
enemies = []
for _ in range(N):
    x, h = map(int, input().split())
    enemies.append((x, math.ceil(h / A)))
enemies.sort()

t = 0
ans = 0
attacks = []
attacksum = 0
for f in range(N):
    x, h = enemies[f]
    while attacks:
        if x > attacks[0][0]:
            ax, ad = heappop(attacks)
            attacksum -= ad
        else:
            break
    if h <= attacksum:
        continue
    damage = h - attacksum
    attacksum += damage
    ans += damage
    attacks.append((x + D, damage))

print(ans)

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x << 30) + h)
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1] >> 30 <= Q[0][0]:
        xh = X.pop()
        x, h = xh >> 30, xh % (1<<30)
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
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()

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

cnt_sum = 0
cnt = [0] * n
l = 0
for i in range(n):
    while monsters[l][0] + 2*d < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
        
    already = cnt_sum * a
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

print(sum(cnt))

Solution (Python):
class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() 
        self.N0 = 1<<self.height 
        self.laz = [self.ID_M]*(2*self.N0) 
        self.val = None 

    
    def build(self,initial):
        self.val = initial[:]

    
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        self.thrust(L)
        self.thrust(R-1)
        
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,d,a = [int(i) for i in readline().split()]
xh = [tuple(int(i) for i in readline().split()) for _ in range(n)]
xh.sort()

from operator import add
ID_M = 0


seg = segment_tree_dual(n, add, add, ID_M)
X = [i[0] for i in xh]
H = [i[1] for i in xh]
seg.build(H)


from bisect import bisect_right

d *= 2
ans = 0
for i in range(n):
    h = seg.point_get(i)
    if h < 0: continue
    ans += (h+a-1)//a
    dam = (h+a-1)//a*a 
    
    
    idx = bisect_right(X,X[i]+d)-1
    
    seg.update(i,idx,-dam)



print(ans)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

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

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

n,d,a = map(int, input().split())
d *= 2
data = []
s = set()
for i in range(n):
    x,h = map(int, input().split())
    s.add(x)
    s.add(x+d)
    data.append([x,h])
data.sort()
dd = sorted(s)
ddd = {j:i for i,j in enumerate(dd)}
m = len(dd)

BIT = Binary_Indexed_Tree(m+1)
ans = 0
for x,h in data:
    i = ddd[x]
    rem = BIT.sum_range(i+1 , m+1)
    h = max(h-rem, 0)
    cnt = -(-h//a)
    ans += cnt
    BIT.add(ddd[x+d]+1, cnt*a)
print(ans)

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

N,D,A=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]
M.sort()

PLACE=[M[i][0] for i in range(N)]
HP=[M[i][1] for i in range(N)]

seg_el=1<<(N.bit_length()) 
SEG=[0]*(2*seg_el) 
LAZY=[0]*(2*seg_el) 

for i in range(N):
    SEG[i+seg_el]=HP[i]
    

def indexes(L,R): 
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def adds(l,r,x): 
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: 
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
    
    while L!=R:
        if L > R:
            SEG[L]+=x
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]+=x
            LAZY[R]+=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=min(SEG[ind<<1],SEG[1+(ind<<1)])  
        
def getvalues(l,r): 

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: 
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

plind=0
ANS=0
import bisect

while plind<N:
    RHP=getvalues(plind,plind+1)
    if RHP>0:
        MAX=PLACE[plind]+2*D
        x=bisect.bisect_right(PLACE,MAX)
        adds(0,x,(-RHP//A)*A)
        ANS+=-(-RHP//A)

    else:
        plind+=1

print(ANS)

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)