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):
def f_silver_fox_vs_monster():
    
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N, D, A = [int(i) for i in input().split()]
    Monsters = sorted([[int(i) for i in input().split()] for j in range(N)])

    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """array[1] から array[index] までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """array[index] に value を加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    position = [row[0] for row in Monsters]
    hit_point = [row[1] for row in Monsters]
    
    pos_right = [bisect_right(position, pos + 2 * D) for pos in position]

    ans = 0
    bomb_damage = BIT(N + 1)  
    for i in range(N):
        hp, damage, right = hit_point[i], bomb_damage.sum(i + 1), pos_right[i]
        if hp - damage > 0:
            num_defeat = (hp - damage + A - 1) // A  
            ans += num_defeat
            bomb_damage.add(i + 1, num_defeat * A)
            
            bomb_damage.add(right + 1, -num_defeat * A)
    return ans

print(f_silver_fox_vs_monster())

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

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

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

    B.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = B[i]
    ans = 0
    ok = [False] * N
    S = [0] * (N + 1)
    for i in range(N):
        if S[i] < H[i]:
            cnt = (H[i] - S[i]) // A if (H[i] - S[i]) % A == 0 else (H[i] - S[i]) // A + 1
            ans += cnt
            search_max = bisect_right(X, X[i] + 2 * D)
            S[i] += cnt * A
            S[search_max] -= cnt * A
        
        S[i+1] += S[i]

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import bisect
n,d,a = map(int,input().split())
l = []
for i in range(n):
    x,h = map(int,input().split())
    l.append([x,h])
l.sort(key=lambda x:x[0])
x = [l[0][0]]
c = 1
ans = l[0][1]//a
if l[0][1] % a > 0:
    ans += 1
count = [ans]
y = 0
for i in range(1,n):
    y = bisect.bisect_left(x,l[i][0]-2*d)
    
    if y > 0 and y < c:
        if (ans-count[y-1])*a < l[i][1]:
            b = (l[i][1] - (ans-count[y-1])*a)//a
            if (l[i][1]-(ans-count[y-1])*a) % a > 0:
                b += 1
            x.append(l[i][0])
            count.append(ans+b)
            ans += b
            c += 1
    else:
        if y == 0:
            if ans*a < l[i][1]:
                    b = (l[i][1] - ans*a)//a
                    if (l[i][1] - ans*a)%a > 0:
                        b += 1
                    x.append(l[i][0])
                    count.append(ans+b)
                    ans += b
                    c += 1
        else:
            b = l[i][1]//a
            if l[i][1]%a > 0:
                b += 1
            x.append(l[i][0])
            ans += b
            count.append(ans)
            c += 1
print(ans)

Solution (Python):


import sys
from bisect import bisect_right
from operator import itemgetter

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

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

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

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

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

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

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

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

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

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

N, D, K = MAP()

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

XH.sort(key=itemgetter(0))
X, _ = zip(*XH)
D = D * 2

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

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

xh.sort()

ends = [None] * n
start = 0

d2 = 2 * d
for base in range(n):
    while True:
        if start >= n:
            break

        x = xh[start][0]
        
        if x > xh[base][0] + d2:
            
            break
        start += 1
    
    
    
    
    
    
    
    ends[base] = start




cnt = [0] * (n + 1)

hist = 0
ans = 0
for i, end in enumerate(ends):
    hist += cnt[i]
    atk = (max(0, xh[i][1] - hist * a) + a - 1) // a
    
    ans += atk
    hist += atk

    cnt[i] += atk
    cnt[end] -= atk
    

print(ans)

Solution (Python):
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def update(self,left,right,f):
        left += self.n
        right += self.n
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],f)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],f)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

import sys
input = sys.stdin.readline

import bisect

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

monster.sort()
ans = 0
X = []
H = []
for i in range(N):
    X.append(monster[i][0])
    H.append(monster[i][1])

r = [0 for _ in range(N)]
for i in range(N):
    r[i] = bisect.bisect_left(X,X[i]+2*D+1)

sg = SegmentTreeDual(H,lambda x,y:x+y,0)

for i in range(N):
    hp = sg.get(i)
    if hp <= 0:
        continue
    cnt = -(-hp//A)
    sg.update(i,r[i],-A*cnt)
    ans += cnt

print(ans)

Solution (Python):
def main():
    import sys
    from collections import deque
    read=sys.stdin.read
    readline=sys.stdin.readline
    
    n, d, a = map(int, readline().split())
    m = map(int, read().split())
    monsters = sorted(zip(m, m), key=lambda x:x[0])
    
    bomb_area = deque([])
    bomb_power = deque([])
    total_damage = 0
    ans = 0
    for pos, hp in monsters:
        while bomb_area:
            area = bomb_area[0]
            if area < pos:
                bomb_area.popleft()
                power = bomb_power.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            rest = hp - total_damage
            count = rest // a + (rest % a != 0)
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
    print(ans)


if __name__ == '__main__':
    main()