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

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        
        return self.bit.sum(key+1)

bit = BitImos(n)
ans = 0
att = [0]*n
cnt = 0

for i in range(n):
    tmp = xh[i][0] + 2 * d
    while cnt < n:
        if xh[cnt][0] <= tmp:
            cnt += 1
        else:
            break
    att[i] = min(cnt-1, n-1)

for i,xh1 in enumerate(xh):
    x,h = xh1
    if bit.get(i) < h:
        at = -(-(h - bit.get(i)) // a)
        ans += at
        bit.add(i, att[i]+1, at*a)

print(ans)

Solution (Python):
import bisect
def main():
    N,D,A=map(int,input().split())
    XH=[list(map(int,input().split())) for _ in range(N)]
    XH.sort()
    for i in range(N):
        XH[i][1]=-(-XH[i][1]//A)
    X=[x for x,a in XH]
    far=[0]*N
    for i in range(N):
        far[i]=bisect.bisect_right(X,X[i]+2*D)-1

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

if __name__ == '__main__':
    main()

Solution (Python):
from math import ceil
def solve():
    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(key=lambda x:x[0])

    S = [0] * (N+1)
    ans = 0
    for i in range(N):
        if S[i] < monster[i][1]:
            left = i-1
            right = N
            while right - left > 1:
                mid = (left + right) // 2
                if monster[mid][0] > monster[i][0] + 2 * D:
                    right = mid
                else:
                    left = mid
            include_end = left
            need = ceil((monster[i][1] - S[i]) / A)
            S[i] += need * A
            S[include_end+1] -= need * A
            ans += need
        S[i+1] += S[i]
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):


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

now_damage=0
from collections import deque
d=deque(d)
ans=0
d_field=deque()
while d:
    x=d.popleft()
    place,life=x
    if d_field:
        while (d_field and d_field[0][0]<place) :
            now_damage-=A*d_field[0][1]
            d_field.popleft()      
    if life<=now_damage:
        pass
    elif life>now_damage:
        K=math.ceil((life-now_damage)/A)
        ans+=K
        now_damage+=K*A
        d_field.append((2*D+place,K))        
print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A)+1
lst.sort(key=itemgetter(0))
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A)+1
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A)+1
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Solution (Python):
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A)+1
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Solution (Python):
def nibun_right(a, x, lo=0, hi=None):
 if lo < 0:
  raise ValueError('lo must be non-negative')
 if hi is None:
  hi = len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(int((lst[i][1]-1)/A)+1-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Solution (Python):
def nibun_right(a, x, lo=0, hi=None):
 if lo < 0:
  raise ValueError('lo must be non-negative')
 if hi is None:
  hi = len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
lst.sort()
DMG=[0]*N
ans=0
for i in range(N):
 if i!=0:
  DMG[i]+=DMG[i-1]
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(int((lst[i][1]-1)/A)+1-DMG[i],0)
 DMG[i]+=Z
 if renji!=N:
  DMG[renji]-=Z
 ans+=Z
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N,d,a = map(int,readline().split())

data0 = [0]*(N+1)
data1 = [0]*(N+1)

def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)


def get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
  return get(data1,r-1)*(r-1)+get(data0,r-1)-get(data1,l-1)*(l-1)-get(data0,l-1)

xh = []
for _ in range(N):
    x,h = map(int,readline().split())
    xh.append((x,h))

xh = sorted(xh)
xl = [x for x,h in xh]

for i in range(N):
    add(i+1, i+2, xh[i][1])

import bisect,math

ans = 0
for i in range(N):
    hp = query(i + 1, i + 2)
    
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect_right(xl, xl[i] + 2*d)
        add(i+1, idx+1, -damage)
print(ans)

Solution (Python):
from collections import deque
import sys 
input = sys.stdin.readline
N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh = sorted(xh)
total = 0 
D = 2*D
ans = 0
q = deque()
for i in range(N):
  x, h = xh[i]
  
  while len(q) >= 1 and q[0][0] < x:
    total -= q.popleft()[1]
  h -= total

  if h > 0:
    num = (h-1)//A+1
    ans += num
    damage = num*A
    total += damage
    q += ([[x+D, damage]])

print(ans)

Solution (Python):
from collections import deque
import sys 
input = sys.stdin.readline
N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh = sorted(xh)
total = 0 
D = 2*D
ans = 0
q = deque()
for i in range(N):
  x, h = xh[i]
  
  while len(q) >= 1 and q[0][0] < x:
    total -= q.popleft()[1]
  h -= total

  if h > 0:
    num = (h-1)//A+1
    ans += num
    damage = num*A
    total += damage
    q += ([[x+D, damage]])

print(ans)

Solution (Python):
from collections import deque
n,d,a = map(int,input().split())
c,cc = 0,0
deq = deque()
dl = [tuple(map(int,input().split())) for i in range(n)]
dl.sort()
for i in dl:
  x,h = i
  while deq:
    if deq[0][0] < x-2*d:
      cc -= deq.popleft()[1]
    else:
      break
  h -= a*cc
  if h > 0:
    c += (h-1)//a + 1
    cc += (h-1)//a + 1
    deq.append((x,(h-1)//a + 1))
print(c)

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

from math import ceil

B = []
for i in range(N):
    B.append((data[i][0],ceil(data[i][1]/A)))

B = [(0,0)] + sorted(B)

C = [0]  
for i in range(1,N+1):
    a = i
    b = N+1
    while a+1 < b:
        mid = (a+b)//2
        if B[mid][0] <= B[i][0] + 2*D:
            a = mid
        else:
            b = mid
    C.append(a)

D = [0]*(N+2)  
ans = 0
for i in range(1,N+1):
    D[i] = max(0,D[i-1]+D[i])
    if D[i] >= B[i][1]:
        continue
    else:
        k = -D[i]+B[i][1]
        D[i] += k
        D[C[i]+1] -= k
        ans += k
print(ans)

Solution (Python):
import sys, heapq
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = [[int(_) for _ in input().split()] for _ in range(N)]
He = [[2 * x, h, 0] for x, h in XH]
heapq.heapify(He)
now = 0
ans = 0
while He:
    x, h, t = heapq.heappop(He)
    if t:
        now -= h
    else:
        if h - A * now > 0:
            diff = (h - A * now - 1) // A + 1
            now += diff
            ans += diff
            heapq.heappush(He, [x + 4 * D + 1, diff, 1])
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from bisect import bisect_right
from operator import add
def resolve():
    n, d, a = map(int, input().split())
    X = [None] * n
    XH = [None] * n
    for i in range(n):
        x, h = map(int, input().split())
        X[i] = x
        XH[i] = x, (h - 1) // a + 1

    X.sort()
    XH.sort()

    tree = SegmentTree([0] * (n + 1), add, 0)
    res = 0
    for i in range(n):
        x, h = XH[i]
        damage = tree.sum(0, i + 1)
        if h < damage:
            continue
        res += h - damage
        tree.add(i, h - damage)
        tree.add(bisect_right(X, x + 2 * d), - h + damage)

    print(res)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, d, a = map(int, input().split())
    XH = [None] * n
    coordinates = set() 
    for i in range(n):
        x, h = map(int, input().split())
        XH[i] = [x, (h - 1) // a + 1] 
        coordinates.add(x)
        coordinates.add(x + 2 * d + 1) 
    XH.sort()
    compress = {v : i for i, v in enumerate(sorted(coordinates))}

    n = len(compress)
    A = [0] * n
    for i in range(len(XH)):
        A[compress[XH[i][0]]] = XH[i][1]

    res = 0
    tree = LazySegmentTree(A, max, 0, add, 0, add) 
    for x, h in XH:
        
        hp = tree.sum(compress[x], compress[x] + 1)
        if hp <= 0:
            continue
        res += hp
        tree.range_act(compress[x], compress[x + 2 * d + 1], -hp)

    print(res)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, d, a = map(int, input().split())
    XH = [None] * n
    coordinates = set() 
    for i in range(n):
        x, h = map(int, input().split())
        XH[i] = [x, (h - 1) // a + 1] 
        coordinates.add(x)
        coordinates.add(x + 2 * d + 1) 
    XH.sort()
    compress = {v : i for i, v in enumerate(sorted(coordinates))}

    n = len(compress)
    A = [0] * n
    for i in range(len(XH)):
        A[compress[XH[i][0]]] = XH[i][1]

    res = 0
    tree = LazySegmentTree(A, max, 0, add, 0, add) 
    for x, h in XH:
        
        hp = tree.sum(compress[x], compress[x] + 1)
        if hp <= 0:
            continue
        res += hp
        tree.range_act(compress[x], compress[x + 2 * d + 1], -hp)

    print(res)
resolve()

Solution (Python):
import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
tree = make_tree(n)
l = len(tree)
for i in range(n):
    tree[i + l // 2] = s[i][1]
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if s[i][0] + 2 * d >= s[j][0]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    l=lambda: list(map(int,input().split()))
    n,d,a=l()
    xh=[]
    for i in range(n):
        xi,hi=l()
        xh.append([xi,hi])
    xh.sort()
    
    
    right_index=[]
    
    
    tmp=0
    for i in range(n):
        j=tmp
        while xh[j][0]<=xh[i][0]+2*d:
            j+=1
            if j==n: break
        j-=1
        right_index.append(j)
        tmp=j

    
    ans=0
    cnt=0
    damage=[0]*(n+1)
    for i in range(n):
    	xh[i][1]-=(ans-cnt)*a
    	damage_cnt=max(0,(xh[i][1]-1)//a + 1)
    	ans+=damage_cnt
    	damage[right_index[i]]+=damage_cnt
    	cnt+=damage[i]
    print(ans)

if __name__=='__main__':
    main()

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        self.sub = [0 for i in range(size + 1)]
        self.r = 0
        self.v = 0
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        self.sub[a] += value
        self.sub[b] -= value

    def get(self, key):
        """値の取得"""
        if key < self.r - 1:
            self.r = 0
            self.v = 0
        for i in range(self.r, key):
            self.v += self.sub[i]
        self.r = key
        return self.v + self.sub[key]


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        ans += c
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        m = -1
        i += 1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import bisect
import operator
import collections


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        self.sub = [0 for i in range(size + 1)]
        self.r = 0
        self.v = 0
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        self.sub[a] += value
        self.sub[b] -= value

    def get(self, key):
        """値の取得"""
        if key < self.r - 1:
            self.r = 0
            self.v = 0
        for i in range(self.r, key):
            self.v += self.sub[i]
        self.r = key
        return self.v + self.sub[key]


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        ans += c
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        m = -1
        i += 1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import math

I = lambda: list(map(int, input().split()))
n, d, a = I()
l = []
for _ in range(n):
	x, y = I()
	l.append([x,y])
l.sort()

j = 0
limit = []
for i in range(n):
	while l[j][0] - l[i][0] <= 2*d:
		j+=1
		if j == n: break
	j-=1
	limit.append(j)

ans = 0
num=[0]*(n+1)
cnt=0
for i in range(n):
	l[i][1]-=(ans-cnt)*a
	damage_cnt=max(0,(l[i][1]-1)//a + 1)
	ans+=damage_cnt
	num[limit[i]]+=damage_cnt
	cnt+=num[i]
print(ans)

Solution (Python):
import math

I = lambda: list(map(int, input().split()))
n, d, a = I()
l = []
for _ in range(n):
	x, y = I()
	l.append([x,y])
l.sort()

j = 0
limit = []
for i in range(n):
	while l[j][0] - l[i][0] <= 2*d:
		j+=1
		if j == n: break
	j-=1
	limit.append(j)

ans = 0
num=[0]*(n+1)
cnt=0
for i in range(n):
	l[i][1]-=(ans-cnt)*a
	damage_cnt=max(0,(l[i][1]-1)//a + 1)
	ans+=damage_cnt
	num[limit[i]]+=damage_cnt
	cnt+=num[i]
print(ans)

Solution (Python):
from collections import deque
import math

N, D, A = map(int, input().split())
monster = [list(map(int, input().split())) for _ in range(N)]
monster.sort(key=lambda x:x[0])

bomb = deque()
s = 0
ans = 0
for i in range(N):
    x, h = monster[i]
    while len(bomb) > 0 and bomb[0][1] < x:
        s -= bomb.popleft()[2]
    h -= s
    if h > 0:
        cnt = math.ceil(h/A)
        damage = cnt*A
        bomb.append([x, x+2*D, damage])
        s += damage
        ans += cnt
print(ans)

Solution (Python):
from math import * 
from collections import *

N, D, A = list(map(int, input().split()))
ans = 0
t = 0
q = deque()

XH = sorted([list(map(int, input().split())) for i in range(N)])

for x, h in XH:
    if q:
        while q and q[0][0] < (x-D):
            _, c = q.popleft()
            t -= c
    
    h = h - t * A
    if h <= 0: continue
    
    x += D
    c = ceil(h/A)
    t += c
    ans += c
    q.append((x, c))
    
print(ans)

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

Monster.sort(key=lambda x:x[0])

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    while len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
            break
    Monster[i][1] -= damage
    count = -(-max(Monster[i][1],0)//A)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)

Solution (Python):
N, D, A = map(int, input().split())
XH = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans, R, S = 0, 0, [0] * (N + 2)
for L in range(N):
    while R < N and XH[R][0] - XH[L][0] <= 2 * D:
        R += 1
    S[L + 1] += S[L]
    bomb = (max(XH[L][1] - S[L + 1], 0) + A - 1) // A
    ans += bomb
    S[L + 1] += bomb * A
    S[R + 1] -= bomb * A
print(ans)

Solution (Python):


from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, -(h // a + (1 if (h % a) else 0))))
    bomb = 0
    res = 0
    while q:
        x, h = heapq.heappop(q)
        if h < 0:
            h *= -1
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):


from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, -ceil(h / a)))
    bomb = 0
    res = 0
    while q:
        x, h = heapq.heappop(q)
        if h < 0:
            h *= -1
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):


from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, 0, ceil(h / a)))
    bomb = 0
    res = 0
    while q:
        x, ty, h = heapq.heappop(q)
        if ty == 0:
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, 1, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):
xh=[]
n,d,a=map(int,input().split())
for _ in range(n):
	x,h=map(int,input().split())
	xh.append([x,h])
xh.sort()
ans=0
cnt=[0]*n
j=0
limit=[]
for i in range(n):
	while xh[j][0]-xh[i][0]<=2*d:
		j+=1
		if j==n:
			break
	j-=1
	limit.append(j)
num=[0]*(n+1)
cnt=0
for i in range(n):
	xh[i][1]-=(ans-cnt)*a
	damage_cnt=max(0,(xh[i][1]-1)//a+1)
	ans+=damage_cnt
	num[limit[i]]+=damage_cnt
	cnt+=num[i]
print(ans)