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:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        # add x to [l, r)
        # l, r: 0-indexed
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        # return sum of [l, r)
        # l, r: 0-indexed
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        return self.bit1._sum(i)*i + self.bit2._sum(i)

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x-d, h))
XH.sort()
X = []
H = []
for x, h in XH:
    X.append(x)
    H.append(h)

bit = RangeAddBIT(n+1)
bit.init(H)
import bisect
ans = 0
for i in range(n):
    h = bit.sum(i, i+1)
    if h > 0:
        q = (h+a-1)//a
        ans += q
        j = bisect.bisect_right(X, X[i]+2*d)
        bit.add(i, j, -q*a)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from heapq import *

def main():
	n,d,a=MI()
	Q=[]
	heapify(Q)
	for _ in range(n):
		x=LI()
		heappush(Q,x)

	ans=0
	now=0
	li=[[10**10,0]]
	heapify(li)
	while Q:
		#print(Q,li,ans,now)
		if Q[0][0]<li[0][0]:
			x,h=heappop(Q)
			if h-now>0:
				k=(h-now-1)//a+1
				ans+=k
				now+=k*a
				heappush(li,[x+2*d+1,-k*a])
		else:
			x,h=heappop(li)
			now+=h
	print(ans)
















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque

N, D, A = map(int, input().split())
Monsters = [tuple(map(int, input().split())) for _ in range(N)]
Monsters.sort()
Attack = deque()
attack = 0
ans = 0
for x, h in Monsters:
    while Attack and Attack[0][0] <= x:
        y, at = Attack.popleft()
        attack -= at
    h -= attack
    num = max((h - 1) // A + 1, 0)
    attack += num * A
    ans += num
    Attack.append((x + 2 * D + 1, num * A))
print(ans)

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
from math import ceil
times = ceil(XH[0][1]/A)
ans = times
damege = [times*A]
coor = [XH[0][0]+2*D]
start = 0
end = 1
dam = sum(damege[start:end])
for i in range(1,N):
    st = start
    while start < end and coor[start] < XH[i][0]:
        start += 1
    dam -= sum(damege[st:start])
    H = XH[i][1] - dam
    if H > 0:
        times = ceil(H/A)
        ans += times
        damege.append(times*A)
        dam += times*A
        coor.append(XH[i][0]+2*D)
        end += 1
print(ans)

Submission status: Accepted

Solution code:
# 解説放送の方針
# ダメージが消える右端をキューで管理
# 右端を超えた分は、累積ダメージから引いていく

from collections import deque

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

XH = sorted(XH)
que=deque()
cum = 0
ans = 0
for i in range(N):
  x,h = XH[i]
  if i == 0:
    r,n = x+2*D,(h+A-1)//A
    d = n*A
    cum += d
    que.append((r,d))
    ans += n
    continue
  while que and que[0][0]<x:
    r,d = que.popleft()
    cum -= d
  h -= cum
  if h<0:
    continue
  r,n = x+2*D,(h+A-1)//A
  d = n*A
  cum += d
  que.append((r,d))
  ans += n
  
print(ans)

Submission status: Accepted

Solution code:
"""

普通に端っこを基準にして、貪欲的に爆弾をおいていく方法を考えるのがよさそう。
座標圧縮したうえで、遅延セグ木で各座標に蓄積しているダメージを管理しておけばよい。
一番左端のやつの体力を削れるだけの爆弾を設置してみる:O(1)
次の左端になるモンスターの位置(体力が1以上あるモンスターのなかで一番左端のやつの座標)を探す。これはO(logN)かかる。
このサイクルをモンスターが全滅するまで行うので、O(N)サイクル回す。したがって全体でO(NlogN)
"""
from math import ceil
class lazySegTree:
    def __init__(self,n):
        self.end_leave = 2**(n.bit_length()+1)
        self.tree = [0]*(2*self.end_leave)
        self.lazy = [0]*(2*self.end_leave)

    def gindex(self,left,right):
        #leftとrightの真上にあるノードを返す
        left = left + self.end_leave
        right = right + self.end_leave
        left >>= 1
        while left:
            yield left
            left >>= 1

        right >>= 1
        while right:
            yield right
            right >>= 1

    def add(self,left,right,x):
        L = left + self.end_leave
        R = right + self.end_leave
        while L < R:
            if L&1:
                self.lazy[L] += x
                self.tree[L] += x
                L += 1
            if R&1:
                R -= 1
                self.lazy[R] += x
                self.tree[R] += x
            L >>= 1
            R >>= 1
        for i in self.gindex(left,right):
            self.tree[i] = max(self.tree[i*2],self.tree[i*2+1])+self.lazy[i]
    
    def propagates(self,*ids):
        for i in reversed(ids):
            self.lazy[i*2] += self.lazy[i]
            self.lazy[i*2+1] += self.lazy[i]
            self.tree[i*2] += self.lazy[i]
            self.tree[i*2+1] += self.lazy[i]
            self.lazy[i] = 0

    def get(self,left,right):
        self.propagates(*self.gindex(left,right))
        L = left + self.end_leave
        R = right + self.end_leave
        res = 0
        while L < R:
            if L&1:
                res = max(res,self.tree[L])
                L += 1
            if R&1:
                R -= 1
                res = max(res,self.tree[R])
            L >>= 1
            R >>= 1
        return res
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
compSet = []
for x,h in XH:
    compSet.append(x)
    compSet.append(x+2*D)
compSet.sort()
compSet = sorted(set(compSet))
compDic = {x:i for i,x in enumerate(compSet)}

LST = lazySegTree(len(compDic))
ans = 0
for x,h in XH:
    compX = compDic[x]
    h -= LST.get(compX,compX+1)
    if h > 0:
        bomb = ceil(h/A)
        ans += bomb
        damage = bomb*A
        compRight = compDic[x+2*D]
        LST.add(compX,compRight+1,damage)
print(ans)

Submission status: Accepted

Solution code:
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    N, D, A = map(int, input().split())
    mlist = []
    for _ in range(N):
        x, h = map(int, input().split())
        mlist.append([x, (h+A-1)//A])
    mlist.sort(key=lambda x: x[0])
    db = deque()
    dnotb = deque()
    left = mlist[0][0]
    ans = 0
    for monster in mlist:
        if monster[0] <= left+2*D:
            db.append(monster)
        else:
            dnotb.append(monster)
    ans = 0
    while db or dnotb:
        if not db:
            monster = dnotb.popleft()
            monster[1] += ans
            db.append(monster)
        bmonster = db.popleft()
        while dnotb:
            if dnotb[0][0] <= bmonster[0]+2*D:
                monster = dnotb.popleft()
                monster[1] += ans
                db.append(monster)
            else:
                break
        ans = max(ans, bmonster[1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def zaatsu(nums):
    ref = list(set(copy.copy(nums)))
    ref.sort()
    dic = dict()
    for i, num in enumerate(ref):
        dic[num] = i

    return [dic[num] for num in nums]

def solve():
    n, d, a = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort()
    ichi = [x[0] for x in li]
    imos = [0] * n
    cur = 0
    ans = 0
    for i, (x, h) in enumerate(li):
        cur -= imos[i]
        hp = h - cur * a
        if hp <= 0:
            continue
        thr = hp // a
        if hp % a != 0:
            thr += 1
        ans += thr
        cur += thr
        owari = bisect_right(ichi, x + 2 * d)
        if owari != n:
            imos[owari] += thr

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())


def is_ok(arg):
    return h[arg][0] <= h[i][0] + d*2

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n, d, a = MAP()
h = [LIST() + [0] for i in range(n)]
h = sorted(h, key=itemgetter(0))
attack = 0

ans = 0
for i in range(n):
    bomb = ceil( (h[i][1] - attack) / a )
    if bomb > 0:
        j = min(meguru_bisect(n, i), n-1)
        h[j][2] -= bomb
        attack += bomb*a
        ans += bomb
    attack += h[i][2]*a

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque


def bisect(ng, ok, x, q):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if q[mid][0] >= x:
            ok = mid
        else:
            ng = mid
    return ok


def solve_greedy(N, D, A, XH):
    ret = 0
    q = deque([(0, 0)])
    for i, (x, h) in enumerate(XH):
        if q[-1][0] < x:
            damaged = 0
        else:
            i = bisect(0, len(q) - 1, x, q)
            damaged = q[-1][1] - q[i - 1][1]
            # q = q[i-1:]
        if h <= damaged:
            continue
        tmp = math.ceil((h - damaged) / A)
        ret += tmp
        q.append((x + 2 * D, A * tmp + q[-1][1]))
    return ret


input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split()))
             for _ in range(N)], key=lambda x: x[0])
ans = solve_greedy(N, D, A, XH)
print(ans)

Submission status: Accepted

Solution code:
# F - Silver Fox vs Monster
N,D,A = map(int,input().split())
XH = [0]*N
for i in range(N):
    X,H = map(int,input().split())
    XH[i] = (X,(H-1)//A+1)
XH = sorted(XH, key=lambda x:x[0])
X = [xh[0] for xh in XH]
M = [XH[0][1]]+[XH[i][1]-XH[i-1][1] for i in range(1,N)]
Y = [0]*N
r = 0
for l in range(N):
    r = max(r,l+1)
    while r<N and X[r]<=X[l]+2*D:
        r += 1
    Y[l] = r-1
ans = 0
tmp = 0
for i in range(N):
    tmp += M[i]
    if tmp>0:
        ans += tmp
        r = Y[i]+1
        if r<N:
            M[r] += tmp
        tmp = 0
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
from collections import defaultdict

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

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

XH.sort()
Xs = [ xh[0] for xh in XH ]
HP = [ xh[1] for xh in XH ]

XR = []
for x in Xs:
  XR.append(bisect(Xs, x+2*D))

cnt = 0
temp = 0
D = defaultdict(int)

for i in range(N):
  temp -= D[i]
  HP[i] -= temp
  if HP[i] > 0:
    temp += HP[i]
    cnt += HP[i]
    D[XR[i]] += HP[i]
    HP[i] -= temp

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(n)])
ret = 0
surface = 0
dec = []
j = 0
for i in range(n):
    x, h = xh[i]
    while j < len(dec) and dec[j][0] < x:
        surface -= dec[j][1]
        j += 1
    h = (h + a - 1) // a - surface
    if h > 0:
        dec.append((x + 2 * d, h))
        ret += h
        surface += h
print(ret)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_table(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

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

    # get sum of [0, i]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i = max(i, 1)
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # get sum of [l, r], or just l
    def get(self, l, r=None):
        if r is None: r = l
        return self.sum(r) - self.sum(l-1)

class ExBIT:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    # add x to [l, r] (not [l, r)])
    def add(self, x, l, r=None):
        if r is None: r = l
        r += 1
        self.p.add(l, -x * l)
        self.p.add(r, x * r)
        self.q.add(l, x)
        self.q.add(r, -x)

    def sum(self, l, r):
        r += 1
        return self.p.sum(r) + self.q.sum(r) * r - self.p.sum(l) - self.q.sum(l) * l

    def get(self, l, r=None):
        if r is None: r = l
        return self.sum(l, r)

def main():
    N, D, A = LI()
    XH = sorted(LIR(N), key=lambda x: x[0])
    X = [xi for xi, _ in XH]
    bit = ExBIT(N)

    for i in range(N):
        _, hi = XH[i]
        bit.add(math.ceil(hi / A), i)

    ans = 0

    for i, (xi, hi) in enumerate(XH):
        right = bisect_right(X, xi + 2 * D) - 1
        cnt = bit.get(i)
        if cnt > 0:
            bit.add(-cnt, i, right)
            ans += cnt

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import*
INF=10**18
n,d,a=map(int,input().split())
mon=[]
for _ in range(n):
  mon+=[list(map(int,input().split()))]
mon.sort()
ans=0
tot=0
q=deque()
for i in range(n):
  x,h=mon[i]
  while q and q[0][0]<x:
    tot-=q.popleft()[1]
  h-=tot
  if h>0:
    b=(h+a-1)//a
    tot+=b*a
    ans+=b
    q.append((x+2*d,b*a))
print(ans)

Submission status: Accepted

Solution code:
import bisect
import math
N, D, A = map(int, input().split())
cusum = [0] * (N+1)
X = []
XH =[]
for i in range(N):
    xi, hi = map(int, input().split())
    X += [xi]
    XH += [(xi, hi)]
X = sorted(X)
XH = sorted(XH)
cusumD = 0
ans = 0
for i, (xi, hi) in enumerate(XH):
    cusumD -= cusum[i]
    hi = max(0, hi-cusumD)
    r = bisect.bisect_right(X, xi+2*D)
    b = int(math.ceil(hi/A))
    d = b * A
    ans += b
    cusumD += d
    cusum[r] += d
    
print(ans)

Submission status: Accepted

Solution code:
#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
from collections import deque
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for i in range(n)]
xh.sort()
queue = deque()
ans = 0
cur = 0
for i in range(n):
    x, h = xh[i]
    while queue != deque() and queue[0][0] < x:
        cur -= queue.popleft()[1]
    h -= cur
    if h > 0:
        cur += a * ((h - 1) // a + 1)
        ans += (h - 1) // a + 1
        queue.append([x + 2 * d, a * ((h - 1) // a + 1)])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

fox.sort()

sub = [0]*(n+1)

def bisect(x):
    l, r = 0, n
    while r-l > 1:
        k = (r+l)//2
        if fox[k][0] <= x:
            l = k
        else:
            r = k
    if fox[l][0] <= x:
        return l
    return r


def main():
    ans = 0
    
    for i in range(n):
        if i != 0:
            sub[i] += sub[i-1]
        if fox[i][1]-a*sub[i] <= 0:
            continue
        count = (fox[i][1]-sub[i]*a-1)//a+1
        ans += count
        sub[i] += count
        sub[bisect(fox[i][0]+2*d)+1] -= count

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from itertools import islice
from operator import itemgetter


def resolve(in_):
    N, D, A = map(int, next(in_).split())
    def f(line):
        x, h = map(int, line.split())
        return x, (h + A - 1) // A
    XH = list(map(f, islice(in_, N)))
    XH.sort(key=itemgetter(0))
    assert N == len(XH)

    bomb_attack = deque()
    bomb = 0
    ans = 0
    for x, h in XH:
        while bomb_attack and bomb_attack[0][0] < x:
            e = bomb_attack.popleft()
            bomb -= e[1]

        h_real = h - bomb
        if h_real <= 0:
            continue
        ans += h_real
        bomb_attack.append((x + D * 2, h_real))
        bomb += h_real

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
monster = {}
x = []
for i in range(n):
    xx, hh = MAP()
    monster[xx] = hh
    x.append(xx)
x.sort()

q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = x[i], monster[x[i]]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
import math

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

# 爆発範囲がとても広く、全ての爆発が右端まで及ぶとひとまず考える
# 各xを見る際に、影響の及ばない爆発分のダメージは引く

# 合計の爆発回数
ans = 0
# 爆発ダメージの合計
total_damage = 0
# 各爆発の情報
dq = deque()

# 左端から順にモンスターを見る
for x, h in XH:
    # 爆発が及ばない場合
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    # 爆発させる必要がある場合
    if total_damage < h:
        # 残っているHPに更新
        h -= total_damage
        # 必要な爆発回数
        cnt = math.ceil(h / A)
        ans += cnt
        # 爆発回数 * 単発のダメージ
        dmg = cnt * A
        total_damage += dmg
        # [爆発で与えるダメージ、及ぶ範囲の右端]
        dq.append((dmg, x + D * 2))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math

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

# 爆発範囲がとても広く、全ての爆発が右端まで及ぶとひとまず考える
# 各xを見る際に、影響の及ばない爆発分のダメージは引く

# 合計の爆発回数
ans = 0
# 爆発ダメージの合計
total_damage = 0
# 各爆発の情報
dq = deque()

# 左端から順にモンスターを見る
for x, h in XH:
    # 爆発が及ばない場合
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    # 爆発させる必要がある場合
    if total_damage < h:
        # 残っているHPに更新
        h -= total_damage
        # 必要な爆発回数
        # cnt = math.ceil(h // A)
        cnt = (h + A - 1) // A
        ans += cnt
        # 爆発回数 * 単発のダメージ
        dmg = cnt * A
        total_damage += dmg
        # [爆発で与えるダメージ、及ぶ範囲の右端]
        dq.append((dmg, x + D * 2))

print(ans)

Submission status: Accepted

Solution code:
from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import deque
import math
n,d,a = map(int,input().split())
F = []
for _ in range(n):
    x,h = map(int,input().split())
    F.append((x,h))
F.sort()
total = 0
d *=2
ans = 0
q = deque([])
for x,h in F:
    while q and q[0][0]<x:#累積和
        total -= q.popleft()[1]
    h-=total
    if h >0:
        tmp = math.ceil(h/a)
        ans += tmp
        damage = tmp*a
        total += damage
        q.append((x+d,damage))
print(ans)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np

def solve(N, D, A, XH):
    q = []
    idx_q = 0
    I = XH[:, 0].argsort()
    XH = XH[I]
    XH[:, 1] = -(-XH[:, 1]//A)
    d = 0
    ans = 0
    for i in range(N):
        x, h = XH[i]
        while idx_q < len(q) and q[idx_q][0] <= x:
            d -= q[idx_q][1]
            idx_q += 1
        if d < h:
            q.append((x + D*2+1, h-d))
            ans += h-d
            d = h
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8[:,:])"],
])

import sys
def main():
    N, D, A = map(int, input().split())
    XH = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N, 2)
    ans = solve(N, D, A, XH)
    print(ans)

main()