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
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,D,A = MI()
    XH = LLIN(N)
    XH.sort()
    q = deque()
    ans = 0
    now = 0
    for x,h in XH:
        while q and x > q[0][0]:
            now -= q.popleft()[1]
        h-=now
        if h>0:
            ans += (h+A-1)//A
            q.append((x+2*D, ((h+A-1)//A)*A))
            now += ((h+A-1)//A)*A
    print(ans)
    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)

Submission status: Accepted

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

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0
atk_que = deque()
atk_acm_p = 0

for i in range(n):
    while len(atk_que) > 0:
        if atk_que[0][0] < e[i][0]:
            atk_u,atk_p = atk_que.popleft()
            atk_acm_p -= atk_p
        else:
            break
    e[i][1] -= atk_acm_p
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk_p = a * atk_times
    atk_acm_p += atk_p
    atk_que.append([atk_u,atk_p])

print(atk_times_sum)

Submission status: Accepted

Solution code:
import math
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [math.ceil(xh[i][1]/a) for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
# bisectより尺取り法のほうが速いと思ったんだけど…
bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = h[i]
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = bomb_ruisekiwa[i-1]
        else:
            damage = bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]
        if h[i] - damage > 0:
            bomb = h[i] - damage
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Submission status: Accepted

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Submission status: Accepted

Solution code:
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Submission status: Accepted

Solution code:
n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
# bisectより尺取り法のほうが圧倒的に速いだろjk
bomb_syakutori = [0 for i in range(n)]
l = 0
r = 0
flag = 0
while r <= n - 1:
    if x[r] <= x[l] + 2*d:
        bomb_syakutori[r] = l
        r += 1
    else:
        l += 1


bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_syakutori[i] == i:
            damage = 0
        elif bomb_syakutori[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_syakutori[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Submission status: Accepted

Solution code:
import math
from collections import deque
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法1 - 貪欲法
"""
キューを使った貪欲法で間に合わせる。
que = [[ダメージ量,そのダメージがどこまで使えるか],...]
とすることにより、高速にダメージ管理をすることができる。
"""

que = deque()
ans = 0
dmg = 0

for i in range(n):
    while que:
        lim = que.popleft()
        if lst1[i][0] > lim[1]:
            dmg -= lim[0]
        else:
            que.appendleft(lim)
            break
    
    if lst1[i][1] > dmg:
        need = math.ceil((lst1[i][1]-dmg)/a)
        ans += need
        dmg += need*a
        que.append([need*a,lst1[i][0]+2*d])

print(ans)

Submission status: Accepted

Solution code:
import collections

N, D, A = [int(i) for i in input().split()]  # 数, 範囲, 攻撃力
XH = [tuple(map(int, input().split())) for _ in range(N)]  # 座標, 体力
XH.sort()

queue = collections.deque()
ans = 0
damage = 0

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

    h -= damage
    if h > 0:
        count = -(-h // A)
        ans += count

        queue.append((x + 2*D, count * A))
        damage += count * A

print(ans)

Submission status: Accepted

Solution code:
import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法2 - imos法
"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""
x = []
for i in lst1:
    x.append(i[0])

#process1
index = 0
reach = []
for i in range(n):
    index = bisect.bisect_right(x,lst1[i][0]+2*d)
    reach.append(index)

#process2
ans = 0
imos = [0]*(n+1) #その座標に効いている魔法の回数(ダメージ量ではない)

for i in range(n):
    if imos[i]*a < lst1[i][1]: #ダメージが足りないなら
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]] -= need #届かなくなったとこでマイナス
        ans += need
    imos[i+1] += imos[i] #累積和を逐一とる

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    buf = sys.stdin.buffer

    n, d, a = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))

    bomb_area = []
    bomb_power = []
    bomb_length = 0
    total_damage = 0
    ans = 0
    idx = 0
    for pos, hp in monsters:
        while idx < bomb_length:
            area = bomb_area[idx]
            if area < pos:
                power = bomb_power[idx]
                total_damage -= power
                idx += 1
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp - total_damage + a - 1) // a
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
            bomb_length += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

N, D, A = map(int, input().split())
E = []
for _ in range(N):
    x, h = map(int, input().split())
    E.append((x, h))
    E.append((x+2*D, 0))

E = sorted(E, key=lambda x: (x[0], -x[1]))

for i in range(len(E)-1, -1, -1):
    x, h = E[i]
    if h != 0:
        xmax = x
        break

bomb = defaultdict(int)
damage = 0
ans = 0
for i in range(len(E)):
    x, h = E[i]

    if x > xmax:
        break

    # x+2D: damageをマイナス
    if h == 0:
        damage -= bomb[x]
        continue

    h -= damage

    if h <= 0:
        continue

    x = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    bomb[x] = cnt * A
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

# 攻撃に巻き込めるインデックスを求める
left = 0 # 可能
right = n # 不可能
while left+1 < right:
    mid = (left + right) // 2
    if x[mid] - x[0] <= 2*d:
        left = mid
    else:
        right = mid
makikomi = [left]
right = left
for i in range(1, n):
    while x[right] - x[i] <= 2*d:
        right += 1
    right -= 1
    makikomi.append(right)

cnt = [0 for i in range(n)]
left = 0
already = 0
for i in range(n):
    while x[makikomi[left]] < x[i]:
        already -= cnt[left]
        left += 1
    cnt[i] = max(h[i] - already, 0)
    already += cnt[i]

print(sum(cnt))

Submission status: Accepted

Solution code:
N,D,A=map(int,input().split())
P=sorted([list(map(int,input().split())) for i in range(N)])
l=r=a=d=0
m=[0]*(N+1)
while l<N:
    while r<N and P[r][0]<=P[l][0]+2*D:
        r+=1
    d+=m[l]
    x=-(-max(0,P[l][1]-d)//A)
    a+=x
    d+=x*A
    m[r]-=x*A
    l+=1
print(a)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n, d, a = map(int, input().split())
    m = [list(map(int, input().split())) for _ in range(n)]
    m.sort()
    r = 1
    d *= 2
    q=deque([])
    for i in range(n):
        while r < n and m[i][0] + d >= m[r][0]:
            r += 1
        m[i].append(r)
        m[i][1] = (m[i][1] + a - 1) // a
    res = 0
    tdamage = 0
    for i in range(n):
        while q and q[0][0] <= i:
            minus = q.popleft()
            tdamage -= minus[1]
        m[i][1] -= tdamage
        if m[i][1] > 0:
            res += m[i][1]
            tdamage += m[i][1]
            q.append([m[i][2],m[i][1]])
    print(res)
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort()
x=[];h=[]
for xi,hi in XH:
    x.append(xi); h.append(hi)
x.append(inf); h.append(0)
data=[0]*(n+1)
for  i in range(n):
    xi=x[i]; hi=h[i]
    hi-=data[i]
    K=max(0,(A+hi-1)//A); count += K
    data[i]+=K*A
    data[bisect.bisect_left(x,xi+2*D+1)]-=K*A
    data[i+1]+=data[i]
print(count)

Submission status: Accepted

Solution code:
from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
from operator import itemgetter
def main():
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
import queue
import math
n, d, a = map(int, input().split())
xh = list(list(map(int, input().split())) for _ in range(n))

xh.sort(key=lambda x: x[0])
d = d * 2
total = 0
q = queue.Queue()
ans = 0
for i in range(n):
    while(not q.empty() and q.queue[0][0] < xh[i][0]):
        total -= q.queue[0][1]
        q.get()
    h = xh[i][1] - total
    if h > 0:
        c = math.ceil(h/a)
        ans += c
        damage = c * a
        total += damage
        q.put((xh[i][0]+d, damage))

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    d*=2
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d)]+=t*a
        s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
import bisect

n, d, a = [int(i) for i in input().split()]

xh = []
for i in range(n):
    xh.append([int(i) for i in input().split()])

# 座標でソート
xh.sort()

x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]

# i番目のモンスターに、i-k番目で使った爆弾が届いた場合の最小のi-k
bomb_bisect = []
for i in range(n):
    bomb_bisect.append(bisect.bisect_left(x, x[i]-2*d))

bomb_ruisekiwa = [0 for i in range(n)]
# 左から貪欲に爆弾を使用
for i in range(n):
    bomb = 0
    if i == 0:
        bomb = (h[i]) // a + ((h[i]) % a != 0)
        bomb_ruisekiwa[i] = bomb
    else:
        if bomb_bisect[i] == i:
            damage = 0
        elif bomb_bisect[i]-1 < 0:
            damage = (bomb_ruisekiwa[i-1]) * a
        else:
            damage = (bomb_ruisekiwa[i-1] - bomb_ruisekiwa[bomb_bisect[i]-1]) * a
        if h[i] - damage > 0:
            bomb = (h[i] - damage) // a + ((h[i] - damage) % a != 0)
        bomb_ruisekiwa[i] = bomb + bomb_ruisekiwa[i-1]

print(bomb_ruisekiwa[-1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,d,a = LI()
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,h in xh]
que = deque()
for i,[x,h] in enumerate(xh):
    r = br(X,x+2*d)
    que.append((h,i,r))

ans = 0
lst = [0]*(n+1)
while que:
    h,l,r = que.popleft()
    tmp = max(0,math.ceil((h - lst[l])/a))
    ans += tmp
    lst[l] += tmp*a
    lst[r] -= tmp*a
    lst[l+1] += lst[l]
print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):c[i]+=c[i-1];h-=c[i];t=min(-h//a,0);c[i]-=t*a;c[bisect(z,(x+d+d,9e9))]+=t*a;s-=t
print(s)

Submission status: Accepted

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


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bomb_area = deque([])
bomb_power = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bomb_area:
        area = bomb_area[0]
        if area < pos:
            bomb_area.popleft()
            power = bomb_power.popleft()
            total_damage -= power
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        power = a * count
        total_damage += power
        bomb_area.append(pos+2*d)
        bomb_power.append(power)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bomb_area = deque([])
bomb_power = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bomb_area:
        area = bomb_area[0]
        if area < pos:
            bomb_area.popleft()
            power = bomb_power.popleft()
            total_damage -= power
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        power = a * count
        total_damage += power
        bomb_area.append(pos+2*d)
        bomb_power.append(power)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


n, d, a = map(int, input().split())
monsters = []
for _ in range(n):
    pos, hp = map(int, input().split())
    monsters.append([pos, hp])

monsters.sort()

bombs = deque([])
total_damage = 0
ans = 0
for pos, hp in monsters:
    while bombs:
        area, count = bombs[0]
        if area < pos:
            bombs.popleft()
            total_damage -= a * count
        else:
            break
    if hp <= total_damage:
        continue
    else:
        count = (hp-total_damage + a-1) // a
        ans += count
        total_damage += a * count
        bombs.append([pos + 2*d, count])

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    M=10**9
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,(x+d+d,M))]+=t*a
        s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=0
    for i,(x,h)in enumerate(z):
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(y,x+d+d)]+=t*a
        s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,9e9))]+=t*a
    s-=t
print(s)

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=min(-h//a,0)
    c[i]-=t*a
    c[bisect(z,(x+d+d,10e9))]+=t*a
    s-=t
print(s)

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=-min(-h//a,0)
    c[i]+=t*a
    c[bisect(z,(x+d+d,10e9))]-=t*a
    s+=t
print(s)

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=0--max(0,h)//a
    c[i]+=t*a
    c[bisect(z,(x+d+d,10e9))]-=t*a
    s+=t
print(s)

Submission status: Accepted

Solution code:
from bisect import*
n,d,a,*t=map(int,open(0).read().split())
c=[0]*-~n
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
s=0
for i,(x,h)in enumerate(z):
    c[i]+=c[i-1]
    h-=c[i]
    t=0--max(0,h)//a
    c[i]+=t*a
    c[bisect(y,x+d+d)]-=t*a
    s+=t
print(s)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    N, D, A = map(int, input().split())
    M = [tuple(int(m) for m in input().split()) for _ in range(N)]
    M.sort()
    #print(M)
    HP = [0] * (N + 2)
    count = 0
    for i, m in enumerate(M):
        HP[i + 1] += HP[i]
        #print(HP)
        x, h = m
        right = x + 2 * D
        if HP[i + 1] < h:
            add = (h - HP[i + 1]) // A
            if (h - HP[i + 1]) % A > 0: add += 1
            small, large = i, N
            while large - small > 1:
                mid = (small + large) // 2
                if M[mid][0] > right: large = mid
                else: small = mid
            HP[i + 1] += add * A
            HP[small + 2] -= add * A
            count += add
    #print(HP)
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

XH=[[0,0] for _ in range(N)]
for i in range(N):
    x,h=map(int,input().split())
    XH[i][0]=x
    XH[i][1]=h
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]



ans=0
S=[0]*(N+1)#累積和


for i in range(N):
    if S[i]<XH[i][1]:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        num=(XH[i][1]-S[i])//A
        if (XH[i][1]-S[i])%A!=0:
            num+=1
        ans+=num
        dam=num*A
        #imosで遅延
        S[Lb]+=dam
        S[Rb]-=dam
    S[i+1]+=S[i]
        
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq

N, D, A = map(int,input().split())
m = []
for i in range(N):
    hq.heappush(m, tuple(map(int,input().split())))
ans = 0
dmg = 0; d = []
while m:
    X, H = m[0]
    if not d or (X <= d[0][0]):
        if dmg < H:
            k = (H - dmg + A - 1) // A
            ans += k
            dmg += k * A
            hq.heappush(d, (X + 2 * D, - k * A))
        hq.heappop(m)
    else:
        dmg += d[0][1]
        hq.heappop(d)
    # print(dmg, m, d) #DB

print(ans)

Submission status: Accepted

Solution code:
import heapq as hq

N, D, A = map(int,input().split())
m = []
for i in range(N):
    hq.heappush(m, tuple(map(int,input().split())))
ans = 0
dmg = 0; d = []
while m:
    X, H = m[0] # 
    if not d or (X <= d[0][0]):
        if dmg >= H:
            hq.heappop(m)
        else:
            k = (H - dmg + A - 1) // A
            ans += k
            dmg += k * A
            hq.heappush(d, (X + 2 * D, - k * A))
    else:
        dmg += d[0][1]
        hq.heappop(d)
    # print(dmg, m, d) #DB

print(ans)

Submission status: Accepted

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

n, d, a = (int(v) for v in stdin.readline().split())
monsters = [(int(v) for v in line.split()) for line in stdin.readlines()]

monsters = [[x, (h // a + 1) if h % a > 0 else (h // a)] for x, h in monsters]
monsters = sorted(monsters)
bomb_size = 2 * d + 1
num_bombs = 0

current_bombs = 0
bomb_endpoints = deque()
bomb_endnumbers = deque()

for i in range(len(monsters)):
    while len(bomb_endpoints) > 0 and bomb_endpoints[0] <= monsters[i][0]:
        current_bombs -= bomb_endnumbers[0]
        bomb_endpoints.popleft()
        bomb_endnumbers.popleft()
    monsters[i][1] -= current_bombs
    if monsters[i][1] > 0:        
        bombs_now = monsters[i][1]
        monsters[i][1] = 0
        num_bombs += bombs_now
        current_bombs += bombs_now
        bomb_endpoints.append(monsters[i][0] + bomb_size)
        bomb_endnumbers.append(bombs_now)

print(num_bombs)

Submission status: Accepted

Solution code:
import sys
import math

def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]
    xh = [[]] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    # n = 3
    # d = 1
    # a = 1
    # xh = [[1, 4], [2, 1], [3, 100]]
    xh.sort()

    cur = 0
    right_indices = [0] * n
    for i in range(n):
        cur = max(cur, i)
        x, h = xh[i]
        right_val = x + d * 2
        while cur < n-1 and xh[cur+1][0] <= right_val:
            cur += 1
        right_indices[i] = cur

    imos = [0] * (n+1)
    ans = 0
    for i in range(n):
        if imos[i] < xh[i][1]:
            need = math.ceil((xh[i][1] - imos[i]) / a)
            ans += need
            imos[i] += need * a
            right_idx = right_indices[i]
            imos[right_idx+1] -= need * a
        imos[i+1] += imos[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
M = []
for i in range(N):
  x, h = map(int, input().split())
  M.append((x, -(-h//A)))
M.sort(key=lambda x: x[0])
X = list(map(lambda x: x[0], M))
H = list(map(lambda x: x[1], M))

dmg = [0] * (N+1)
ans = 0

for i in range(N):
  x, h = M[i]
  h = max(0, h - dmg[i])
  dmg[bisect_right(X, x + 2*D)] -= h
  dmg[i+1] += dmg[i] + h
  ans += h
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  if h <= 0:
    continue
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)

Submission status: Accepted

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
d = [0]*(N+1)
for l in range(N):
  if d[l]<xh[l][1]:
    la = (xh[l][1]-d[l]+A-1)//A
    for _ in range(N):
      if l<N and r<N and 2*D>=xh[r][0]-xh[l][0]:
        r+=1
      else:
        break
    ans += la
    d[l]+=la*A
    d[r]-=la*A
  d[l+1]+=d[l]
print(ans)