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 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)

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]

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 = bisect_right(xx, xi + 2 * d)
        imos[i] += c * a
        imos[idx] -= c * a

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

print(ans)

Solution (Python):
from operator import itemgetter
from bisect import bisect_right
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]

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 = bisect_right(xx, xi + 2 * d)
        imos[i] += c * a
        imos[idx] -= c * a

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

print(ans)

Solution (Python):
import bisect

n, d, a = map(int, input().split())
XB = []
X = []
for _ in range(n):
    x, h = map(int, input().split())
    bomb = int(-(-h//a))
    XB.append([x, bomb])
    X.append(x)

XB = sorted(XB, key=lambda x:x[0])
X = sorted(X)




X_range = [[-1]]

for i in range(1,n):
    now = X[i]
    
    x_ind = bisect.bisect_left(X, X[i]-2*d)
    if x_ind == i:
        X_range.append([-1])
    else:
        X_range.append([x_ind, i-1])







Bomb = [XB[0][1]]
Bomb_rui = [0, XB[0][1]]

for i in range(1,n):
    need_bomb = XB[i][1]
    if X_range[i][0] == -1:
        Bomb.append(need_bomb)
        Bomb_rui.append(Bomb_rui[-1]+need_bomb)
    else:
        before_bomb = Bomb_rui[X_range[i][1]+1] - Bomb_rui[X_range[i][0]]
        if before_bomb >= need_bomb:
            Bomb.append(0)
            Bomb_rui.append(Bomb_rui[-1])
        else:
            need_bomb -= before_bomb
            Bomb.append(need_bomb)
            Bomb_rui.append(Bomb_rui[-1]+need_bomb)

ans = Bomb_rui[-1]



print(ans)

Solution (Python):
import sys
from collections import deque
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

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

"""
どうせ左端のモンスターはいつか倒さないといけない（かつ爆弾投下順は不問）ので、
左端のモンスターから順に、なるべく爆弾を右に寄せて落としていけば良い。

別解としてBITでも殴ってみた
"""
class BIT:
    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    """
    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)

"""
BITで区間に対する加算をする場合はimos法を利用することに注意する
"""

Damage = BIT(N)
ans = 0
for i in range(1, N + 1):
    x, h = monsters[i]
    d = Damage.sum(i) 
    if d < h:
        times = ceil((h - d) / A)
        ans += times
        new_damage = times * A
        

        idx = bisect_right(monsters, (monsters[i][0] + 2 * D, 10**10))
        Damage.add(i, new_damage)
        if idx != N + 1:
            Damage.add(idx, -new_damage)

print(ans)

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

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

"""
どうせ左端のモンスターはいつか倒さないといけない（かつ爆弾投下順は不問）ので、
左端のモンスターから順に、なるべく爆弾を右に寄せて落としていけば良い。

BITを使って区間に爆弾のダメージを追加して考えても良いが、
ここではimos法チックな回答を与える。

仮に全ての爆弾が前モンスターに攻撃を与えるとしよう。
すると各モンスターにどれだけ流れダメージが飛んできたかは累積和で求まる。->totalで累積ダメージを管理。
しかし今回は爆弾に有効範囲があるため、有効期限切れの爆弾ダメージはtotalから除く必要がある。
そこでキューに（爆弾のダメージが入る限界線、爆弾のダメージ）を追加していき、各モンスターを見たとき
爆弾の期限が切れていたらpopleftで期限切れ爆弾を捨てていく。
（それ以降のモンスターに対してもその爆弾は期限切れなので、永久に捨て去って問題ない）。

以下のサイトの解説が参考になりました↓
https://at274.hatenablog.com/entry/2020/02/01/060000
"""

total = 0
ans = 0
q = deque([])

for i in range(N):
    x, h = monsters[i]

    
    while q and q[0][0] < x:
        total -= q[0][1]
        q.popleft()
    h -= total

    
    if h > 0:
        
        times = ceil(h / A)
        ans += times
        

        
        damage = times * A
        total += damage
        q.append((x + 2 * D, damage))

print(ans)

Solution (Python):
def binary_search(v, is_ok):
    """
    ソートしてから使え！！！
    v : list
        ある場所から左が条件を満たさず、右が条件を満たすように並んだ配列
    is_ok(x) : bool
        vの要素xが条件を満たすかどうかを返す関数
    """
    ng = -1             
    ok = len(v)         
    

    
    
    
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if is_ok(v[mid]):   
            ok = mid        
        else:               
            ng = mid        

    return ok



N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
X = [x for x, h in XH]
H = [(h + A - 1) // A for x, h in XH]

yuukou = 0
mou_mukou = [0] * N + [0]
ans = 0


def bomb(l, n):
    global ans, yuukou
    ans += n
    yuukou += n
    r = l + 2 * D
    mou_mukou[binary_search(X, lambda x: r < x)] += n

for i in range(N):
    yuukou -= mou_mukou[i]
    H[i] -= yuukou
    if H[i] > 0:
        bomb(X[i], H[i])

print(ans)

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


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える"""
    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)


def compress(array):
    """座標圧縮したリストを返す"""
    array2 = sorted(set(array))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

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

info = sorted(info)
b = [info[i][0] for i in range(n)]
memo = compress([info[i][0] for i in range(n)])
bit = BIT(n)

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

ans = 0
for i in range(n):
    tmp = bit.get_val(i)
    if tmp <= 0:
        continue
    ans += -((-tmp) // a)
    nxt_ind = b[i] + 2 * d
    ii = bisect.bisect_right(b, nxt_ind)
    bit.add(i, ii, ((-tmp) // a) * a)
print(ans)

Solution (Python):
N, D, A = map(int, input().split())
H = [list(map(int, input().split())) for i in range(N)]
H.sort(key = lambda x:x[0])
INF = int(1e18)
H.append((INF, INF))

ans = 0
S = [0] * (N + 1)
l, r = 0, 0
while l < N:
    while H[r][0] - H[l][0] <= D * 2: r += 1
    h = H[l][1] - S[l]
    num = (h - 1) // A + 1 if h > 0 else 0
    ans += num
    S[l] += A * num
    S[r] -= A * num
    l += 1
    S[l] += S[l - 1]
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,D,A=map(int,input().split())
s=[tuple(map(int, input().split())) for i in range(N)]
s.sort()
d=2*D+1
t=0
p=0
l=[0]*N
a=0
for n,i in enumerate(s):
    while 1:
        if t<N and s[t][0]<i[0]+d:
            t+=1
        else:
            break
    h=i[1]-p*A
    if h>0:
        k=-(-h//A)
        a+=k
        p+=k
        l[t-1]+=k
    p-=l[n]
print(a)

Solution (Python):
import sys
from bisect import bisect_right

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, D, A = MI()
monsters = list()
for i in range(N):
    x, h = MI()
    monsters.append((x, (h + A - 1) // A))
monsters.sort()

X = [x for x, h in monsters]
ub = [0] * N
for i, x in enumerate(X):
    ub[i] = bisect_right(X, x + 2 * D)

dmg = [0] * N
accum = 0
ans = 0
for i, (x, h) in enumerate(monsters):
    h = h - max(0, accum + dmg[i])
    if h > 0:
        ans += h
        dmg[i] += h
        if ub[i] < N:
            dmg[ub[i]] -= h
    accum += dmg[i]
print(ans)

Solution (Python):




def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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


import operator


class LazySegmentTree:  
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num)  
        self.lazy = [self.lide] * (2 * self.num)  
        for i, l in enumerate(ls):  
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  
            v = self.lazy[i]
            if v == self.lide:
                continue
            
            
            self.tree[2 * i + 1] += v >> 1  
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            

            self.lazy[i] = self.lide  

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        
        ids = tuple(_gidx(l, r, self.num))
        
        
        
        
        
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            
            
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            
            x <<= 1  
            l >>= 1
            r >>= 1
        
        for i in ids:
            i -= 1  
            
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        
        self._lazyprop(*_gidx(l, r, self.num))
        
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret



from bisect import bisect_left, bisect_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()

X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)

ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  
    if atk <= 0:
        continue
    ans += atk
    
    seg.update(i+1, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Solution (Python):




def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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


import operator


class LazySegmentTree:  
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num)  
        self.lazy = [self.lide] * (2 * self.num)  
        for i, l in enumerate(ls):  
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  
            v = self.lazy[i]
            if v == self.lide:
                continue
            
            
            self.tree[2 * i + 1] += v >> 1  
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            

            self.lazy[i] = self.lide  

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        
        ids = tuple(_gidx(l, r, self.num))
        
        
        
        
        
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            
            
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            
            x <<= 1  
            l >>= 1
            r >>= 1
        
        for i in ids:
            i -= 1  
            
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        
        self._lazyprop(*_gidx(l, r, self.num))
        
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret



from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from fractions import gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()

X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)

ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  
    if atk <= 0:
        continue
    ans += atk
    
    seg.update(i, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Solution (Python):




def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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


import operator


class LazySegmentTree:  
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  
        self.tree = [self.ide] * (2 * self.num)  
        self.lazy = [self.lide] * (2 * self.num)  
        for i, l in enumerate(ls):  
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  
            v = self.lazy[i]
            if v == self.lide:
                continue
            
            
            self.tree[2 * i + 1] += v  
            self.tree[2 * i + 2] += v
            self.lazy[2 * i + 1] += v
            self.lazy[2 * i + 2] += v
            

            self.lazy[i] = self.lide  

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        
        ids = tuple(_gidx(l, r, self.num))
        
        
        self._lazyprop(*ids)
        
        
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            
            
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            
            l >>= 1
            r >>= 1
        
        for i in ids:
            i -= 1  
            
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2])
            

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        
        self._lazyprop(*_gidx(l, r, self.num))
        
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret



from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from fractions import gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right


N, D, A = read_ints()
XH = read_tuple(N)

XH.sort()

X = []
H_cnt = []
for x, h in XH:
    H_cnt.append((h - 1) // A + 1)
    X.append(x)

seg = LazySegmentTree(H_cnt)

ans = 0
for i in range(N):
    atk = seg.query(i, i + 1)  
    if atk <= 0:
        continue
    ans += atk
    
    seg.update(i, bisect_left(X, X[i] + 2 * D + 1, lo=i), -atk)

print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
n,d,a=map(int,input().split())
l=[]
ans=0
for i in range(n):
    x,h=map(int,input().split())
    l.append((x,-(-h//a)))
l.sort()
back=[-1]
rui=[0]
for x,h in l:
    i=bisect_left(back,x)
    h-=rui[-1]-rui[i-1]
    if h<=0:
        continue
    ans+=h
    back.append(x+d*2)
    rui.append(rui[-1]+h)
print(ans)

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left


def main():
    N, D, A = read_ints()
    XH = read_tuple(N)
    XH.sort()  

    n_atk = []  
    X = []  
    for x, h in XH:
        n_atk.append((h - 1) // A + 1)
        X.append(x)

    damege = [0] * (N + 10)  
    ans = 0
    
    for i, (x, n) in enumerate(zip(X, n_atk)):
        damege[i] += damege[i - 1]  
        atk = max(0, n - damege[i])  
        ans += atk
        
        damege[i] += atk
        
        
        
        
        damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  

n_atk = []  
X = []  
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  
ans = 0

for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  
    atk = max(0, n - damege[i])  
    if atk == 0:
        continue
    ans += atk
    
    damege[i] += atk
    
    
    
    
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  


print(ans)

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  

n_atk = []  
X = []  
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  
ans = 0
j = 0  
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  
    atk = max(0, n - damege[i])  
    ans += atk
    
    damege[i] += atk
    
    while j < len(X) and X[j] < x + 2 * D + 1:
        j += 1
    damege[j] -= atk  

print(ans)

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  

n_atk = []  
X = []  
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  
ans = 0
j = 0  
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  
    atk = max(0, n - damege[i])  
    ans += atk
    
    damege[i] += atk
    
    while j < len(X) and X[j] < x + 2 * D + 1:
        j += 1
    damege[j] -= atk  

print(ans)

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  

n_atk = []  
X = []  
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  
ans = 0

for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  
    atk = max(0, n - damege[i])  
    ans += atk
    
    damege[i] += atk
    
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  

print(ans)

Solution (Python):




import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret








from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  

n_atk = []  
X = []  
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  
ans = 0

for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  
    atk = max(0, n - damege[i])  
    ans += atk
    
    damege[i] += atk
    
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  

print(ans)

Solution (Python):
import bisect
from math import ceil
n,d,a=map(int,input().split())
XH=[list(map(int,input().split())) for i in range(n)]
X=[XH[i][0] for i in range(n)]
XH.sort(key=lambda y:y[0])
X.sort()
damage=[0]*(n+1)
ans=0
for i,(x,h) in enumerate(XH):
  damage[i]+=damage[i-1]
  h-=damage[i]
  if h<=0:
    continue
  cnt=ceil(h/a)
  ans+=cnt
  damage[i]+=a*cnt
  br=bisect.bisect_right(X,x+d*2)
  damage[br]-=a*cnt
print(ans)

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

xh.sort()
xs = [x for x, h in xh]

memo = [0 for _ in range(n)]

ans = 0

for j, (x, h) in enumerate(xh):
    memo[j] +=  memo[j-1]
    b = h - memo[j]
    if b > 0:
        c = (b + a - 1) // a
        memo[j] += c * a
        ans += c
        i = bisect.bisect_right(xs, x + 2 * d)
        if i < n:
            memo[i] -= c * a

print(ans)