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.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,d,a = map(int,input().split())
H = [list(map(int,input().split())) for i in range(n)]
H.sort()

ans = 0
m = 0
M = []
t = 0
for i in range(n):
    while t < len(M) and M[t][1] < H[i][0]:
        m -= M[t][0]
        t += 1
    H[i][1] -= m
    if H[i][1] > 0:
        dn = -(-H[i][1]//a)
        dd = dn * a
        M.append([dd, H[i][0]+d*2])
        ans += dn
        m += dd
    # print(m,M)
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
import math
from operator import itemgetter
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, D, A = IL()
X = []
xx = []
H = []
for i in range(N):
  x, h = IL()
  xx.append(x)
  X.append([x, i])
  H.append(h)
else:
  xx.append(MAX_INT)
xx.sort()
X.sort(key=itemgetter(0))
data = [0]*(N+1)

D = D*2
damage = 0
ans = 0
for i in range(N):
  x,j = X[i]
  hp = H[j]
  damage += data[i]
  num = max(0,math.ceil((hp - damage)/A))
  damage += num*A
  ans += num
  rng = x + D
  nxt = bisect.bisect_right(xx, rng)
  data[nxt] -= num*A
#print(data)
#print(xx)
print(ans)

"""
9 2 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
"""

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,D,A = map(int,readline().split())
m = map(int,read().split())
X, H = zip(*sorted(zip(m,m)))

Xs = sorted(set(X) | set(x + D + D for x in X))
x_to_i = {x:i for i,x in enumerate(Xs)}

L = len(Xs)
d_atk = [0] * L

HP = [0] * L
for x,h in zip(X,H):
    i = x_to_i[x]
    HP[i] = h

d_atk = [0] * L

atk = 0 # 予約済の値を管理
answer = 0
for i in range(L):
    x = Xs[i]
    h = HP[i]
    if h > atk:
        rest = h - atk
        n = (rest + A - 1) // A
        atk += n * A
        answer += n
        d_atk[x_to_i[x+D+D]] = -n * A
    atk += d_atk[i]

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    p = []
    for i in range(N):
        p.append([X[i], H[i]])
    p.sort()
    ret = 0
    idx = []
    val = []
    nex = 0
    minus = 0
    l = 0
    for i in range(N):
        #print(i)
        #print(p[i])
        v = ret
        while l < i and idx[l] < i:
            minus = val[l]
            l += 1
        v -= minus
        p[i][1] = max(0, p[i][1] - v * A)
        tmp = math.ceil(p[i][1] / A)
        ret += tmp
        x = p[i][0] + D
        while nex < N and p[nex][0] <= x + D:
            nex += 1
        nex -= 1
        idx.append(nex)
        val.append(ret)
        #print(idx)
        #print(val)
        #print('tmp ', tmp)
        #print(ret)
        #print()
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n,d,a=map(int,input().split())
XH=[]
for _ in range(n):
    x,h=map(int,input().split())
    h=math.ceil(h/a)
    XH.append([x,h])
XH.sort()
if n==1:
    print(XH[0][1])
    exit()
l=0
r=0
ans=XH[0][1]
c=XH[0][1]
L=[c]
while l<=n-1:
    left=XH[l][0]
    right=left+2*d
    if XH[r+1][0]<=right:
        cc=max(0,XH[r+1][1]-c)
        L.append(cc)
        c+=cc
        ans+=cc
        r+=1
        if r>=n-1:
            r-=1
            l+=1
    else:
        c-=L[l]
        l+=1
print(ans)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

import math

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

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q*A))
        s += q*A
        t += q

print(t)

Submission status: Accepted

Solution code:
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N; V = [[]for _ in range(N)]
    for i in range(N):
        A[i],B[i] = LI()
        V[i] = [A[i],B[i],A[i]/B[i]]
    V.sort(key=lambda x:x[2],reverse=True)
    dp = [[inf]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            if j <= H - V[i][0]:
                dp[i + 1][j + V[i][0]] = min(dp[i + 1][j + V[i][0]], dp[i][j] + V[i][1])
            else:
                dp[i + 1][H] = min(dp[i + 1][H], dp[i][j] + V[i][1])
    loop = (H-1) // V[0][0] + 1
    ans = [0]*loop
    for i in range(loop):
        curH = H - V[0][0]*i
        ans[i] = i * V[0][1] + min(dp[N][curH:])
    print(ans)
#    print(dp)
    print(min(ans))
    return

def examF():
    class segment_():
        def __init__(self, A, n, segfunc):
            #####単位元######要設定0or1orinf
            self.ide_ele = 0
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update_add(self, k,u):
            k += self.num
            self.seg[k] += u
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    B = [0] * (N + 1)
    S = segment_(B,(N+1),lambda a, b: a+b)
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        left = bisect.bisect_left(X,X[i]-D*2)
#        print(now)
        cur -= min(S.query(left,i),cur)
        ans +=cur
        S.update_add(i,cur)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

Solution code:
import sys
n,d,a=map(int,input().split())
xh=[]
xx=[]
for i in range(n):
    x,h=map(int,input().split())
    xx.append(x)
    xh.append((x,h//a+(h%a>0)))
xh.sort()
xx.sort()
dp=[0]*n
import bisect
buf=0
count=0
if d==0:
    for i in range(n):
        count+=xh[i][1]
    print(count)
    sys.exit()
for i in range(n):
    #print(buf)
    buf+=dp[i]
    y=max(xh[i][1]-buf,0)
    count+=y
    buf+=y
    idx=bisect.bisect_left(xx,xx[i]+2*d+1)
    if idx>=n:
        continue
    dp[idx]-=y
    #print(dp,y,buf)
print(count)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

import collections

dms = collections.deque()
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []
for i in range(N):
    xh.append(LI())
xh.sort()

# sum_dm = [] # start + 2 * D
ans = 0
sum_dm = 0
for i in range(N):
    X, H = xh[i]
    while len(dms) > 0:
        if dms[0][0] + 2 * D < X:
            x, dm = dms.popleft()
            sum_dm -= dm
        else:
            break
    H -= sum_dm
    if H > 0:
        ans += math.ceil(H / A)
        dms.append([X, math.ceil(H/A) * A])
        sum_dm += math.ceil(H/A) * A
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret




def main():
    N,D,A = list(map(int,input().split()))

    enemy = []
    for i in range(N):
        x,h = list(map(int,input().split()))
        if h%A==0:
            enemy.append([x,h//A])
        else:
            enemy.append([x,h//A+1])

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l

    bit = BIT([0]*N)

    count1 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v=0
        if enemy[i][1] - v>0:
            count1 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)

    enemy = enemy[::-1]
    for i in range(N):
        enemy[i][0] = -enemy[i][0]

    bit = BIT([0]*N)

    count2 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v = 0
        if enemy[i][1] - v>0:
            count2 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)


    print(min(count1,count2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
XH = [tuple(map(int,input().split())) for i in range(N)]
XH.sort()
from collections import deque
q = deque()

ans = dmg = 0
for x,h in XH:
    while q and q[0][0] < x:
        _,d = q.popleft()
        dmg -= d
    rem = h - dmg
    if rem <= 0: continue
    a = -(-rem // A)
    ans += a
    dmg += a*A
    q.append((x + 2*D, a*A))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, D, A = map(int, input().split(' '))
X_H_pairs = [list(map(int, input().split(' '))) for _ in range(N)]

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

import math
i, ans = 0, 0
powers = []
damage = 0
while i < N:
    x, h = X_H_pairs[i]
    if powers:
        while powers and x - powers[0][0] > 2*D:
            damage -= powers[0][1]
            powers.pop(0)

    h -= damage
    if h <= 0:
        i += 1
        continue
    else:
        times = int(math.ceil(h / A))
        ans += times

        dh = times * A
        damage += dh
        powers.append((x, dh))
        i += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n, d, a = LI()
X = []
H = []
xh = LIR(n)
xh.sort()
for x, h in xh:
    X += [x]
    H += [h]

X2 = [0] * n
ret = 0
ans = 0
for i in range(n):
    x = X[i]
    ret -= X2[i]
    remain = H[i] - ret
    if remain > 0:
        j = remain // a + bool(remain % a)
        ans += j
        ret += j * a
        if x + d * 2 < X[-1]:
            l = i
            r = n
            while l + 1 < r:
                mid = (l + r) // 2
                if X[mid] <= x + d * 2:
                    l = mid
                else:
                    r = mid
            X2[r] += j * a


print(ans)

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
import heapq
def main():
    N,D,A=map(int,input().split())
    xh = [tuple(map(int,input().split())) for _ in range(N)]
    xh = sorted(xh, key = lambda x:x[0])
    x = [elem[0] for elem in xh]
    h = [elem[1] for elem in xh]
    res = 0
    buff = 0
    q = []
    heapq.heapify(q)
    #heapq.heappush(q,x[0])
    for i in range(N):
        while len(q)!=0:
            p = heapq.heappop(q)
            if p[0] < x[i]:
                #buff -= int((p-int(p))*(10**9))
                buff -= p[1]
            else:
                heapq.heappush(q,p)
                break
        nowhp = h[i] - buff*A
        if nowhp <= 0:
            continue
        cnt = math.ceil(nowhp/A)
        res += cnt
        buff += cnt
        #print(cnt,buff)
        ins = (x[i]+2*D, cnt)
        heapq.heappush(q,ins)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    n, d, a = get_list()
    monsters = [get_list() for _ in range(n)]
    monsters.sort()
    sm = 0
    updates = []
    ptr = 0
    res = 0
    for x, helth in monsters:
        while ptr<len(updates) and updates[ptr][0]<=x:
            sm += updates[ptr][1]
            ptr += 1
        if helth>sm:
            times = (helth-sm+a-1)//a
            k = times*a
            res += times
            sm += k
            updates.append([x+2*d+1, -k])
    print(res)

''' Pythonista fLite 1.1 '''
import sys
#from collections import defaultdict, Counter
#from bisect import bisect_left, bisect_right
#from functools import reduce
#import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
tekis = []
for i in range(N):
    x, h = map(int, input().split())
    tekis.append((x, h))

tekis.sort()

haba = 2 * D

# iryoku, zahyoumigihaji
ruisekiwa = [(0, float("-inf"))]

left = 0

ans = 0
for i in range(N):
    x, h = tekis[i]

    while left < len(ruisekiwa) and ruisekiwa[left][1] < x:
        left += 1
    left -= 1
    # print("------x=", x, "h=", h)
    # print(ruisekiwa)
    # print("left=", left)

    imamadeiryoku = 0
    if left < len(ruisekiwa):
        imamadeiryoku = ruisekiwa[-1][0] - ruisekiwa[left][0]
    # print("imamadeiryoku=", imamadeiryoku)

    h -= imamadeiryoku

    bakudankaisuu = 0
    if h > 0:
        bakudankaisuu = h // A + (1 if h % A > 0 else 0)
    ans += bakudankaisuu
    # print("bakudannkaisuu", bakudankaisuu)
    bakudaniryoku = A * bakudankaisuu
    ruisekiwa.append((bakudaniryoku + ruisekiwa[-1][0], x + haba))

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
from operator import itemgetter
from math import ceil
def main():
    N ,D ,A  = map(int,input().split())
    XH = [list(map(int,input().split())) for _ in range(N)]
    XH.sort(key = itemgetter(0))
    X = [x for x,h in XH]
    S = [0]*(N + 10)
    sm = 0
    for i in range(N):
        x,h = XH[i]
        right = br(X,x + 2*D) - 1
        h -= (sm - S[i-1])
        sm += max(0,ceil(h/A))*A
        S[right] += max(0,ceil(h/A))*A
        S[i] += S[i-1]
    print(sm // A)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def solve():
    from bisect import bisect_right

    N,D,A = II()
    X,H = Line(N,2)
    #Binary Indexed Tree（区間加算）
    #1-indexed
    class Range_BIT():
        def __init__(self, N):
            self.size = N
            self.data0 = [0]*(N+1)
            self.data1 = [0]*(N+1)

        def _add(self, data, k, x):
            while k <= self.size:
                data[k] += x
                k += k & -k

        # 区間[l,r)にxを加算
        def add(self, l, r, x):
            self._add(self.data0, l, -x*(l-1))
            self._add(self.data0, r, x*(r-1))
            self._add(self.data1, l, x)
            self._add(self.data1, r, -x)

        def _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s

        # 区間[l,r)の和を求める
        def query(self, l, r):
            return self._get(self.data1, r-1)*(r-1)+self._get(self.data0, r-1)\
                    -self._get(self.data1, l-1)*(l-1)-self._get(self.data0, l-1)

    #インデックス付きソート
    #(index,value)の順に格納
    from operator import itemgetter
    def index_sort(A):
        return sorted(enumerate(A),key=itemgetter(1))

    num = [math.ceil(H[i]/A) for i in range(N)]
    temp = index_sort(X)

    X2 = [temp[i][1] for i in range(N)]
    num = [num[t[0]] for t in temp]

    bit = Range_BIT(N)
    for i in range(1,N+1):
        bit.add(i,i+1,num[i-1])

    ans = 0
    for i in range(1,N+1):
        c = bit.query(i,i+1)
        if c<=0:
            continue
        p = bisect_right(X2,X2[i-1]+2*D)
        bit.add(i,p+1,-c)
        ans += c

    print(ans)

solve()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

max_H = 10**9
ans = 0
damage = 0
while monsters:
    x, h = heappop(monsters)
    if h <= max_H:
        h -= damage
        if h <= 0:
            continue
        bomb = (h+A-1) // A
        damage += bomb * A
        ans += bomb
        heappush(monsters, (x+2*D, max_H+bomb*A))
    else:
        damage -= h-max_H
print(ans)

Submission status: Accepted

Solution code:
import operator
import os
import sys
from functools import reduce

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353


class LazySegmentTree:
    # http://codeforces.com/blog/entry/18051
    def __init__(self, values, fn=operator.add):
        """
        :param list values:
        :param callable fn:
        """
        # 単位元
        self._id = 0
        self._size = len(values)
        self._fn = fn

        tree = [self._id] * self._size * 2
        tree[self._size:] = values[:]
        for i in reversed(range(1, self._size)):
            tree[i] = fn(tree[i << 1], tree[i << 1 | 1])
        self._tree = tree
        self._delay = [self._id] * self._size * 2

    def _add(self, k, value):
        if k < self._size:
            self._delay[k] = self._delay[k] + value
        else:
            self._tree[k] = self._tree[k] + value

    def add(self, l, r, value):
        """
        :param int l:
        :param int r:
        :param value:
        """
        l += self._size
        r += self._size
        l0, r0 = l, r
        while l < r:
            if l & 1:
                # 右側の子
                self._add(l, value)
                l += 1
            if r & 1:
                # 左側の子
                r -= 1
                self._add(r, value)
            l >>= 1
            r >>= 1
        self._update(l0)
        self._update(r0)

    def _update(self, p):
        """
        self._tree[p] の親たちを最新化する
        :param int p:
        """
        p >>= 1
        while p > 0:
            self._tree[p] = self._fn(
                self._tree[p << 1] + self._delay[p << 1],
                self._tree[p << 1 | 1] + self._delay[p << 1 | 1]
            )
            p >>= 1

    def _eval(self, p):
        """
        self._tree[p] に遅延配列から値を移す
        :param int p:
        """
        # root から葉に向かって遅延配列を移していく
        for h in reversed(range(1, p.bit_length())):
            k = p >> h
            self._tree[k] = self._tree[k] + self._delay[k]
            self._add(k << 1, self._delay[k])
            self._add(k << 1 | 1, self._delay[k])
            self._delay[k] = self._id

    def get(self, l, r=None):
        """
        :param int l:
        :param int|None r:
        """
        if r is None:
            self._eval(self._size + l)
            return self._tree[self._size + l]
        ret_l = []
        ret_r = []
        l += self._size
        r += self._size
        self._eval(l)
        self._eval(r)
        while l < r:
            if l & 1:
                ret_l.append(self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret_r.append(self._tree[r])
            l >>= 1
            r >>= 1
        return reduce(self._fn, ret_l + ret_r)


N, D, A = list(map(int, sys.stdin.buffer.readline().split()))
XH = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

XH.sort()
X = []
H = []
for x, h in XH:
    X.append(x)
    H.append(h)

lr = []
r = 0
for l in range(N):
    while r < N and X[r] <= X[l] + D * 2:
        r += 1
    lr.append((l, r))

st = LazySegmentTree(values=H + [0], fn=operator.add)
ans = 0
for l, r in lr:
    h = st.get(l, l + 1)
    if h > 0:
        cnt = (h + A - 1) // A
        st.add(l, r, -cnt * A)
        ans += cnt
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
n,d,a=map(int,input().split())
s=sorted([list(map(int,input().split()))for i in range(n)])
c=0
p=[0]
q=[0]
for i in range(n):
    g=bl(q,s[i][0])
    s[i][1]-=a*(p[-1]-p[g-1])
    if s[i][1]>0:
        t=((s[i][1]-1)//a+1)
        c+=t
        p.append(p[-1]+t)
        q.append(s[i][0]+2*d)
print(c)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

window = deque()
windowSum = 0
total = 0
for x, h in XH:
    while window and x - window[0][0] > 2 * D:
        oldX, oldBombs = window.popleft()
        windowSum -= A * oldBombs

    h = max(0, h - windowSum)
    bombs = h // A + (1 if h % A else 0)
    total += bombs

    window.append((x, bombs))
    windowSum += A * bombs
    #print(x, bombs, window, windowSum)


print(total)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil
import sys
input = sys.stdin.readline

def main():
    N,D,A = map(int,input().split())
    XH = sorted([[int(i) for i in input().split()] for _ in range(N)],key=lambda x: x[0])

    ans = 0
    index = deque()
    damage = 0
    for i in range(N):
        # 爆弾が届かない場合
        while index:
            if index[0][0] + 2*D < XH[i][0]:
                _,c = index.popleft()
                damage -= A * c
            else:
                break
        
        # 爆弾投下
        XH[i][1] -= damage

        # 生き残り
        if XH[i][1] > 0:
            count = ceil(XH[i][1]/A)
            damage += count * A
            index.append([XH[i][0],count])
            ans += count

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
def main():

    N, D, A = map(int, input().split())
    XH = []
    for _ in range(N):
        X, H = map(int, input().split())
        XH.append([X, H])

    if N == 1:
        x, h = XH[0]
        if h % A == 0: return h // A
        return h // A + 1

    XH.sort()
    ans = 0
    B = [[XH[0][0], XH[0][1], 0]]
    j = 0
    k = 0
    count = [0]
    while j < N or len(B) > 0:
        if len(B) > 0:
            x, h, i = heapq.heappop(B)
            h -= (count[k]- count[i])*A
            if h > 0:
                if h % A == 0: n = h // A
                else: n = h // A + 1
                ans += n
                count.append(count[-1]+n)
                while j < N and XH[j][0] <= x + 2*D:
                    heapq.heappush(B, [XH[j][0], XH[j][1], k])
                    j += 1
                k += 1
        else:
            heapq.heappush(B, [XH[j][0], XH[j][1], k])
            j += 1

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from math import ceil
from bisect import bisect
from operator import itemgetter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key=itemgetter(0))
X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

bit = BIT(N)
ans = 0
for i in range(N):
    bit.add(i+1,H[i])
    bit.add(i+2,-H[i])
    h = bit.sum(i+1)
    if h>0:
        ans += ceil(h/A)
        x = -ceil(h/A)*A
        j = bisect(X,X[i]+2*D)
        bit.add(i+1,x)
        bit.add(j+1,-x)

print(ans)