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_left,bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)
imos=[0]*(n+1)
mi=0
ans=0
for i in range(n):
  mi-=imos[i]
  h[i]=max(h[i]-mi*a,0)
  atk=0--h[i]//a
  ans+=atk
  mi+=atk
  point=x[i]+d*2
  index=bisect_right(x,point)
  imos[index]+=atk
print(ans)

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

    N, D, A = map(int, input().split())
    info = []
    for _ in range(N):
        x, h = map(int, input().split())
        info.append((x, h))
    info.sort(key=itemgetter(0))

    imos = [0] * N
    X = [info[i][0] for i in range(N)]
    H = [info[i][1] for i in range(N)]
    ans = 0
    i = 0
    dam = 0
    while True:
        dam += imos[i] * A
        assert dam >= 0
        bomb = (max(H[i] - dam, 0) - 1) // A + 1
        ans += bomb
        
        if H[i] > dam:
            j = bisect_right(X, X[i] + 2*D)
        else:
            j = 0
        if j == i:
            i += 1
        else:
            if i == N-1:
                break
            imos[i+1] += bomb
            if j != N:
                imos[j] -= bomb
            i += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import operator
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





class LazySegmentTree:
    
    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

        
        self._size = 1 << (size - 1).bit_length()
        self._fn = fn

        self._lazy = [0] * (self._size * 2 - 1)
        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 add(self, from_i, to_i, value, k=0, L=None, r=None):
        """
        [from_i, to_i) を、それぞれの値と value に fn を適用した値で更新する
        :param int from_i:
        :param int to_i:
        :param int value:
        :param int k: self._tree のインデックス
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        self._eval(k, L, r)

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

        if from_i <= L and r <= to_i:
            
            self._lazy[k] += (r - L) * value
            self._eval(k, L, r)
        else:
            
            self.add(from_i, to_i, value, k * 2 + 1, L, (L + r) // 2)
            self.add(from_i, to_i, value, k * 2 + 2, (L + r) // 2, r)
            self._tree[k] = self._fn(self._tree[k * 2 + 1], self._tree[k * 2 + 2])

    def _eval(self, k, L, r):
        """
        遅延配列の値を評価する
        :param k:
        :param L:
        :param r:
        """
        if self._lazy[k] != 0:
            
            self._tree[k] += self._lazy[k]
            
            if r - L > 1:
                self._lazy[k * 2 + 1] += self._lazy[k] >> 1
                self._lazy[k * 2 + 2] += self._lazy[k] >> 1
            self._lazy[k] = 0

    def get(self, from_i, to_i, 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:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        self._eval(k, L, 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


N, D, A = list(map(int, sys.stdin.buffer.readline().split()))
XH = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

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

lr = []
r = 0
for l in range(N):
    while r < N and X[r] <= X[l] + D * 2:
        r += 1
    lr.append((l, r))

imos = [0] * (N + 1)
cum = 0
ans = 0
for l, r in lr:
    cum += imos[l]
    h = H[l] - cum
    if h > 0:
        cnt = (h + A - 1) // A
        cum += cnt * A
        imos[r] -= cnt * A
        ans += cnt
print(ans)

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

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,d,a = nm()
l = [tuple(nm()) for _ in range(n)]
l.sort()
l += [(10**20,10**20)]
r = [0]*(n+3)
rind = 0
ans = 0
for i in range(n):
    x,h = l[i]
    r[i] += r[i-1]
    h -= r[i]
    
    if h <= 0: continue
    curd = x + 2*d
    while l[rind+1][0] <= curd:
        rind += 1
    
    cnt = (h-1)//a + 1
    dam = cnt*a
    r[i] += dam
    r[rind+1] -= dam
    ans += cnt
print(ans)

Solution (Python):
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from operator import itemgetter
n, d, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

info = sorted(info, key = itemgetter(0))
bit = BIT(n)

for i in range(n):
    bit.add(i, i+1, info[i][1])

info.append([10**18, 0])
ans = 0 
r = 0
for i in range(n):
    num = bit.get_val(i)
    if num <= 0:
        continue
    while True:
        if info[r][0] - info[i][0] > 2*d:
            break
        else:
            r += 1
    ans += -((-num) // a)
    bit.add(i, r, -(-((-num) // a)) * a)
print(ans)

Solution (Python):
from bisect import bisect_right

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

X = [x for x, _ in XH]

ans = 0
ims = [0] * (N + 1)
cnt = 0

for now, (x, h) in enumerate(XH):
    cnt += ims[now]
    if cnt * A >= h:
        continue
    ness = -(-(h - cnt * A) // A)
    cnt += ness

    i = bisect_right(X, x + D * 2)
    ims[now] += ness
    ims[i] -= ness
    ans += ness

print(ans)

Solution (Python):
import sys
from bisect import bisect
def input():
	return sys.stdin.buffer.readline()[:-1]

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

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

	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

	def SegAdd(self, l, r, x):
		self.PointAdd(l, x)
		self.PointAdd(r+1, -x)
		return


n, d, a = map(int, input().split())
d *= 2
mo = sorted([list(map(int, input().split())) for _ in range(n)])
for i in range(n):
	mo[i][1] = (mo[i][1]-1)//a + 1
reach = []
moo = [x[0] for x in mo]
mooo = [x[1] for x in mo]
for x in moo:
	reach.append(bisect(moo, x+d)-1)


bit = BIT(n)

ans = 0
for i, h in enumerate(mooo):
	gap = max(0, h - bit.Get(i+1))
	bit.SegAdd(i+1, reach[i]+1, gap)
	ans += gap

print(ans)

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

n, d, a = list(map(int, input().split()))
xh = []
for line in sys.stdin:
    x, h = map(int, line.split())
    xh.append((x, 0, h))
heapify(xh)
atk_cnt = 0
ans = 0
while xh:
    x, t, h = heappop(xh)
    if t == 0:
        if atk_cnt * a >= h:
            continue
        remain = h - atk_cnt * a
        new_atk = (remain - 1) // a + 1
        heappush(xh, (x + 2 * d, 1, new_atk))
        ans += new_atk
        atk_cnt += new_atk
    else:
        atk_cnt -= h
print(ans)

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

N,D,A = map(int,readline().split())
m = map(int,read().split())
X, H = zip(*sorted(zip(m,m)))

Xs = sorted(set(X) | set(x + D + D for x in X))
x_to_i = {x:i for i,x in enumerate(Xs)}

L = len(Xs)
d_atk = [0] * L

HP = [0] * L
for x,h in zip(X,H):
    i = x_to_i[x]
    HP[i] = h

d_atk = [0] * L

atk = 0 
answer = 0
for i in range(L):
    x = Xs[i]
    h = HP[i]
    if h > atk:
        rest = h - atk
        n = (rest + A - 1) // A
        atk += n * A
        answer += n
        d_atk[x_to_i[x+D+D]] = -n * A
    atk += d_atk[i]

print(answer)

Solution (Python):
import sys
from operator import itemgetter
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, d, a = na()
ms = []
for i in range(n):
    ms.append(na())

ms.sort(key=itemgetter(0))
pq = deque()
dmg = 0
ans = 0
for i in range(n):
    while len(pq) > 0 and pq[0][0] <= ms[i][0]:
        dmg -= pq[0][1]
        pq.popleft()

    h = ms[i][1]
    x = ms[i][0]
    h -= dmg
    if h > 0:
        nu = (h+a-1)//a
        ans += nu
        dmg += a*nu
        pq.append((x+2*d+1, a*nu))

print(ans)