Problem: 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.

Submission attempts (in order):




def _gidx(l, r, treesize):
    
    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):
        
        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):
        
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            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):
        
        
        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  # to 0based
            #########################################################
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        
        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):
    
    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)






def _gidx(l, r, treesize):
    
    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):
        
        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):
        
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            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):
        
        
        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  # to 0based
            #########################################################
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        
        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):
    
    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)






def _gidx(l, r, treesize):
    
    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):
        
        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):
        
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            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):
        
        
        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  # to 0based
            #########################################################
            
            
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2])
            #########################################################

    def query(self, l, r):
        
        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):
    
    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)






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
        
        
        #     j += 1
        
        damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  

    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted