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 resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()

    
    imos = [0] * (N+1)
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] <= 2 * D + x:
                R += 1
            d = h - imos[l]
            cnt = (d+A-1) // A
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import math
import bisect
 
n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0

x.sort()
x.append(1145141919810)
h.append(0)

imos = [0]*(n+1)

atk = math.ceil(itv[0][1]/a)
imos[0] += atk * a
b = bisect.bisect(x,itv[0][0] + (2*d))
imos[b] -= atk * a
ans += atk
    
for i in range(1,n):
    atk = 0
    imos[i] += imos[i-1]
    if itv[i][1] > imos[i]:
        atk = math.ceil((itv[i][1]-imos[i])/a)
        imos[i] += atk * a
        b = bisect.bisect(x,itv[i][0] + (2*d))
        imos[b] -= atk * a
    ans += atk

print(ans)

Solution (Python):
def binary(N, LIST, num):  
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [(j + a - 1) // a for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bnum = max(h[i] - (bsum[i - 1] + bomb[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bsum[i - 1] + bomb[i]
    ans += bnum
print(ans)

Solution (Python):
def binary(N, LIST, num):  
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [(j + a - 1) // a for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(h[i] - bsum[i], 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Solution (Python):
def binary(N, LIST, num):  
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [j for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max((h[i] + a - 1) // a - bsum[i], 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Solution (Python):
from math import ceil


def binary(N, LIST, num):  
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [j for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(ceil(h[i] / a - bsum[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Solution (Python):
from math import ceil

def binary(N,LIST,num):  
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [j for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i, xi in enumerate(x):
    j = binary(n, x, xi + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(ceil(h[i] / a - bsum[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Solution (Python):
from collections import deque
n , d , a = map(int,input().split())
mon = [tuple(map(int,input().split())) for i in range(n)]
mon.sort()
p = deque(mon)
baku = deque()
cou = 0
ans = 0
while p:
    nowx , nowh = p.popleft()
    while baku:
        bx , bh = baku.popleft()
        if bx >= nowx:
            baku.appendleft((bx,bh))
            break
        elif bx < nowx:
            cou -= bh
    if nowh <= cou:
        continue
    elif nowh > cou:
        k = -((-nowh+cou)//a)
        ans += k
        cou += a*k
        baku.append((nowx+2*d,a*k))
print(ans)

Solution (Python):
from bisect import bisect_right

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

x = []
h = []
for d, i in sorted(X):
    x.append(d)
    h.append(i)

ans = 0
k = [-(-v // A) for v in h]
y = [0] * (N + 2)
for i in range(N):
    y[i + 1] += y[i]
    s = max(0, k[i] - y[i + 1])
    ans += s
    y[i + 1] += s
    y[bisect_right(x, x[i] + 2 * D) + 1] -= s
    
print(ans)

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

XH = sorted(tuple(map(int,input().split())) for _ in range(N))

X = [x for x,h in XH]
H = [h for x,h in XH]

dH = [0]*(N+1)

cnt = 0
acc = 0

cnt = 0
i = 0
j = 0
while i < N:
    while j < N and X[j] <= X[i]+2*D:
        j += 1

    acc -= dH[i]
    H[i] -= acc
    if H[i] > 0:
        c = (H[i]-1)//A + 1
        acc += c*A
        dH[j] += c*A
        cnt += c
    i += 1

print(cnt)

Solution (Python):
import math
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

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

    attack = []
    for i in range(N):
        attack.append(math.ceil(monster[i][1] / A))

    acc_damage = 0
    attacked = deque([])
    answer = 0

    for i in range(N):
        x = monster[i][0]
        h = attack[i]

        while attacked and x > attacked[0][0]:
            limit, damage = attacked.popleft()
            acc_damage -= damage

        need = max(0, h - acc_damage)
        answer += need

        acc_damage += need

        if need:
            attacked.append((x + 2 * D, need))

    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

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


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()

    
    q = deque([])

    acc_damage = 0

    ans = 0
    for i in range(N):
        x = X[i]
        h = monster[x]

        while q and q[0][0] < x:
            p, damage = q.popleft()
            acc_damage -= damage

        if h - acc_damage <= 0:
            continue

        cnt = (h - acc_damage + A - 1) // A
        ans += cnt
        acc_damage += cnt * A

        q.append((x + 2 * D, cnt * A))

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
from collections import deque
minusd=deque()
nowd=0
ans=0
for x,h in xh:
  while minusd and minusd[0][1]<=x:
    d_,_=minusd.popleft()
    nowd-=d_
  tmp=max(0,(h-nowd+a-1)//a)
  ans+=tmp
  nowd+=tmp*a
  minusd.append([tmp*a,x+2*d+1])
  
print(ans)

Solution (Python):
import bisect
import itertools
import sys

input=sys.stdin.readline

def main(args):
    n, d, a = map(int,input().split())
    
    monster = [0]*n
    pos = [0]*n
    for i in range(n):
        x, h = map(int,input().split())
        monster[i] = (x, -(-h//a))
        pos[i] = x
    
    pos.sort()
    monster.sort()
    
    limit = [0]*n
    
    for i in range(n):
        limit[i] = bisect.bisect_right(pos, pos[i]+2*d)-1
    
    
    
    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        if damage[i] >= monster[i][1]:
            pass
        else:
            plus = monster[i][1] - damage[i]
            ans += plus
            damage[i] += plus
            damage[limit[i]+1] -= plus
        
        
        damage[i+1] += damage[i]
    
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    dq = deque([])
    damage = 0
    ans = 0

    for x, h in monster:
        while dq and dq[0][0] < x:
            damage -= dq.popleft()[1]

        if h > damage:
            dq.append((x + 2 * D, h - damage))
            ans += h - damage
            damage += h - damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    X = [x for x, h in monster]
    S = [0] * (N + 1)
    idx = 0
    ans = 0

    for i, (x, h) in enumerate(monster):
        d = h - S[i]
        if d > 0:
            right = x + 2 * D
            while idx < N and X[idx] <= right:
                idx += 1

            S[i] += d
            S[idx] -= d
            ans += d

        S[i + 1] += S[i]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0
    cur_damage = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            cur_damage += h - cur_damage

    print(sum(damage))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0
    cur_damage = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            cur_damage += h - cur_damage

    print(sum(damage))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0

    cur_damage = 0
    ans = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            ans += h - cur_damage
            cur_damage += h - cur_damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    left = right = 0

    cum_damage = 0
    ans = 0

    for x, h in monster:
        left = right
        right = bisect_left(pos, x)
        cum_damage -= sum(damage[left:right])

        if h > cum_damage:
            pos.append(x + 2 * D)
            damage.append(h - cum_damage)
            ans += h - cum_damage
            cum_damage += h - cum_damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

n, d, a = map(int, input().split())
lxh = [tuple(map(int, input().split())) for _ in range(n)]

lxh.sort()
lx, lh = [], []
for x, h in lxh:
    lx.append(x)
    lh.append(h)

n_bomb = 0
total_damage = 0
subtract = [0 for _ in range(n + 1)]

for i in range(n):
    total_damage -= subtract[i]

    x = lx[i]
    h = lh[i] - total_damage

    if h > 0:
        n_bomb += -(-h // a)
        damage = -(-h // a) * a
        total_damage += damage

        i_sub = bisect_right(lx, x + 2 * d)
        subtract[i_sub] += damage

print(n_bomb)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    total = 0
    end = deque([])
    for i in range(n):
        x, h = XH[i]
        while end and end[0][0] < x:
            r = end.popleft()
            total -= r[1]

        if total < h:
            res += ((h - total) + a - 1) // a
            damage = ((h - total + a - 1) // a) * a
            total += damage
            end.append([x + 2 * d, damage])
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-1)//a+1
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)

Solution (Python):
from bisect import bisect_right

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

monsters.sort(key=lambda x: x[0])
xlst=[x for x,_ in monsters]

delta=[0]*(N+1)
csum=0

ans=0

for i in range(N):
    xi,hi=monsters[i]
    csum+=delta[i]
    hi-=csum

    if hi<=0:
        continue

    cnt=(hi+A-1)//A
    ans+=cnt

    csum+=A*cnt
    right=bisect_right(xlst,xi+2*D)
    delta[right]-=A*cnt

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,d,a = map(int, input().split())
xh = [None]*n

for i in range(n):
    xh[i] = tuple(map(int, input().split()))
xh.sort()

r = 0
val = 0
from queue import deque
q = deque([])
s = 0
for l,(x,h) in enumerate(xh):
    bound = x+2*d
    while q and l>=q[0][1]:
        s -= q[0][0]
        q.popleft()
    while r<n and xh[r][0]<=bound:
        r += 1
    nokori = h - s
    if nokori>0:
        num = nokori//a + int(nokori%a!=0)
        val += num
        q.append((num*a, r))
        s += num*a
        
print(val)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

n,d,a = map(int, input().split())
xh = [None]*n

for i in range(n):
    xh[i] = tuple(map(int, input().split()))
xh.sort()

bit = [0] * (n+1)
r = 0
val = 0
done = False
for l,(x,h) in enumerate(xh):
    bound = x+2*d
    while r<n and xh[r][0]<=bound:
        r += 1
    nokori = h + query(bit, l+1)
    if nokori>0:

        num = nokori//a + int(nokori%a!=0)
        val += num
        update(bit, l+1, -num*a)
        if r<n:
            update(bit, r+1, num*a)
print(val)

Solution (Python):
import math
from collections import deque
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
total = 0
q = deque([])

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

  if h <= 0:
    continue
  attack = math.ceil(h/A)
  damage = attack*A
  total += damage
  q += [[x+2*D, damage]]
  ans += attack

print(ans)

Solution (Python):
import math
from collections import deque
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 x, h in XH:
  while len(q) and q[0][0] < x:
    total -= q.popleft()[1] 
  h -= total

  if h > 0:
    num = math.ceil(h/A)
    ans += num
    damage = num*A
    total += damage
    q += [[x+D, damage]]
print(ans)

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

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans


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

    XHs.sort()
    Xs, Hs = [], []
    for X, H in XHs:
        Xs.append(X)
        Hs.append(H)

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for i in range(N):
        rest = getValue(i)
        if rest <= 0: continue
        pos = Xs[i] + D
        iR = bisect_right(Xs, pos + D) - 1
        num = -(-rest // A)
        ans += num
        damage = num*A
        addValue(iR, -damage)

    print(ans)


solve()

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

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans


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

    XHs.sort()
    Xs, Hs = [], []
    for X, H in XHs:
        Xs.append(X)
        Hs.append(H)

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for i in range(N):
        rest = getValue(i)
        if rest <= 0: continue
        pos = Xs[i] + D
        iR = bisect_right(Xs, pos + D) - 1
        num = -(-rest // A)
        ans += num
        damage = num*A
        addValue(iR, -damage)

    print(ans)


solve()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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




def main():
    n, d, a = ns()
    x = []
    for _ in range(n):
        xi, hi = ns()
        x.append([xi, hi])

    x.sort()
    x.append([INF, INF])

    perm = [0 for _ in range(n + 1)]
    idx = [xi for xi, hi in x]

    ans = 0
    cnt = 0
    for i in range(n):
        cnt -= perm[i]

        if x[i][1] - cnt * a > 0:
            tmp = ((x[i][1] - cnt * a) + a - 1) // a
        else:
            continue
        ans += tmp
        cnt += tmp

        if cnt > 0:
            tmp_idx = bisect.bisect_right(idx, x[i][0] + 2 * d)
            perm[tmp_idx] += tmp

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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




def main():
    n, d, a = ns()
    x = []
    for _ in range(n):
        xi, hi = ns()
        x.append([xi, hi])

    x.sort()
    x.append([INF, INF])

    perm = [0 for _ in range(n + 1)]
    idx = [xi for xi, hi in x]

    ans = 0
    cnt = 0
    for i in range(n):
        cnt -= perm[i]

        if x[i][1] - cnt * a > 0:
            tmp = ((x[i][1] - cnt * a) + a - 1) // a
        else:
            tmp = 0
        ans += tmp
        cnt += tmp

        if cnt > 0:
            tmp_idx = bisect.bisect_right(idx, x[i][0] + 2 * d)
            perm[tmp_idx] += tmp

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    N, D, A = map(int, input().split())
    
    
    S = list(tuple(map(int, input().split())) for i in range(N)) 
    S.sort()
    xs=[0]*N
    hs=[0]*N
    
    for i,s in enumerate(S):
        x,h=s
        xs[i]=x
        hs[i]=h
    tot=[0]*N
    accu=0
    count=0
    for i,x in enumerate(xs):
        accu+=tot[i]
        h=hs[i]-accu*A
        num=max(0,math.ceil(h/A))
        accu+=num
        count+=num
        ei=bisect_right(xs,x+2*D)
        if ei<N:
            tot[ei]-=num
    print(count)

if __name__ == "__main__":
    main()

Solution (Python):
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

dic={}

ans=0
atk_cnt=0
while B:
    x,h=heappop(B)
    if h==-1:
        atk_cnt-=dic[x-1]
        continue
    if h<=A*atk_cnt:
        continue
    h-=A*atk_cnt
    sup=x+2*D
    bomb=(h-1)//A+1
    ans+=bomb
    dic[sup]=bomb
    atk_cnt+=bomb
    heappush(B,(sup+1,-1))
    
    
print(ans)

Solution (Python):
n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xi, hi = map(int, input().split())
    xh.append([xi, hi])

xh.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(xh[i][0])
    h.append(xh[i][1])

cnt = 0
dmg = [0 for i in range(n+1)]
for i in range(n):
    xi, hi = x[i], h[i]
    dmg[i] += dmg[i-1]
    hi -= dmg[i]
    if hi <= 0:
        continue
    else:
        num = (hi+a-1)//a
        cnt += num
    point = xi + 2*d
    left = i
    right = n
    while left+1 < right:
        mid = (left+right)//2
        if x[mid] <= point:
            left = mid
        else:
            right = mid
    dmg[i] += num*a
    dmg[left+1] -= num*a
print(cnt)

Solution (Python):
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)

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):
n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    h = (h - 1) // a + 1
    xh.append([x, h])
xh.sort()
damage = xh[0][1]
ans = damage
damage_lst = [[xh[0][0] + d * 2, damage]]
pos = 0
for i, (x, h) in enumerate(xh[1:], start = 1):
    while x > damage_lst[pos][0]:
        damage -= damage_lst[pos][1]
        pos += 1
        if pos == i:
            break
    damage_tmp = max(h - damage, 0)
    ans += damage_tmp
    damage += damage_tmp
    damage_lst.append([x + d * 2, damage_tmp])
print(ans)

Solution (Python):
import bisect
import math

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

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

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

X_array = [xh[0] for xh in XH_array]



ans = 0
bomb_count = [0] * N
now_bomb = 0

for i, xh in enumerate(XH_array):
    
    x, h = xh
    remain = h - A * now_bomb
    if remain <= 0:
        now_bomb += bomb_count[i]
        continue
    bomb_add = math.ceil(remain / A)
    ans += bomb_add
    bomb_count[i] += bomb_add
    bomb_end = bisect.bisect_right(X_array, x + 2 * D)
    bomb_count[bomb_end - 1] -= bomb_add
    now_bomb += bomb_count[i]


print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    que = deque()
    total = 0
    res = 0
    for i in range(n):
        x, h = XH[i]
        while que and que[0][0] < x:
            total -= que[0][1]
            que.popleft()
        h -= total

        if h > 0:
            num = (h + a - 1) // a
            res += num
            damage = num * a
            total += damage
            que.append([x + d * 2, damage])
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

print(cnt)

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

def main():
    n, d, a = map(int, input().split())
    XH = []
    for i in range(n):
        x, h = map(int, input().split())
        XH.append((x, h))

    XH.sort()
    from collections import deque
    q = deque()

    ans = 0
    t = 0
    import copy
    for x, h in XH:
        while q:
            r, s = q.popleft()
            if r+d < x:
                t -= s
            else:
                q.appendleft((r, s))
                break
        h -= t
        if h > 0:
            if h%a == 0:
                b = h//a
                ans += b
                t += a*b
                q.append((x+d, a*b))
            else:
                b = h//a+1
                ans += b
                t += a*b
                q.append((x+d, a*b))
    print(ans)

if __name__ == '__main__':
    main()