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:
"""
Given N, D, A, N means no. of monsters, D means distances of bombs, A attack of the bombs

Find the minimum of bombs required to win.

Each monster out of N pairs - pair[0] = position, pair[1] = health

hashmap[i] = H

pref

"""
from collections import deque

mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    INF = 1e9 + 7
    N, D, A = [int(x) for x in raw_input().split()]
    D *= 2
    monsters = []
    #m = {}
    change = [0 for _ in range(N)]
    for _ in range(N):
        pos, health = [int(x) for x in raw_input().split()]
        #m[pos] = m.get(pos, 0) + health
        #smallest_x = min(smallest_x, pos)
        #biggest_x = max(biggest_x, pos)
        health = (health + A - 1) // A
        #print(health)
        
        monsters.append([pos, health])    
    """
    remain_attack = 0
    ans = 0
    for cur in range(smallest_x, biggest_x+1):
        if cur in m and m[cur] > remain_attack:
            remained_health = m[cur] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            attack = times * A
            pref_sum[cur + D] = pref_sum.get(cur + D, 0) - attack
            remain_attack += attack
            ans += times
        remain_attack += pref_sum.get(cur, 0)
            
    """   
            
    monsters.sort(key = lambda x : x[0])
    
    #remain_attacks_queue = deque([])
    
    #remain_attack = 0
    running_sum = 0
    
    ans = 0
    
    for i in range(N):
        pos, health = monsters[i]
        running_sum += change[i]
        #print(health, running_sum)
        my_health = health - running_sum
        if my_health <= 0:
            continue # Already killed
        
        # Find the last monster hit by this range
        lo = i+1
        hi = N-1
        ok = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            #print(mid, monsters[mid])
            if monsters[mid][0] <= pos + D:
                ok = mid
                lo = mid + 1
            else:
                hi = mid - 1
        
        if ok != -1:
            running_sum += my_health
        if ok + 1 < N:
            change[ok+1] -= my_health
            
            
        ans += my_health
        
                
        """
        while len(remain_attacks_queue) and monster[0] - D > remain_attacks_queue[0][0]:
            remain_attack -= remain_attacks_queue.popleft()[1]
        if remain_attack < monster[1]:
            remained_health = monster[1] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            #print(times)
            attack = times * A
            remain_attacks_queue.append([monster[0], attack])
            ans += times
            remain_attack += attack
        """
    
        
    print(ans)
    

main()

Submission status: Accepted

Solution code:
"""
Given N, D, A, N means no. of monsters, D means distances of bombs, A attack of the bombs

Find the minimum of bombs required to win.

Each monster out of N pairs - pair[0] = position, pair[1] = health
"""
from collections import deque

mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    N, D, A = [int(x) for x in raw_input().split()]
    D *= 2
    monsters = []
    
    for _ in range(N):
        pos, health = [int(x) for x in raw_input().split()]
        monsters.append([pos, health])    
    
    
    monsters.sort(key = lambda x : x[0])
    
    remain_attacks_queue = deque([])
    
    remain_attack = 0
    
    ans = 0
    
    for monster in monsters:
        # monster[0] - pos, monster[1] - health
        # queue[0] - position, queue[1] - attack points
        while len(remain_attacks_queue) and monster[0] - D > remain_attacks_queue[0][0]:
            remain_attack -= remain_attacks_queue.popleft()[1]
        if remain_attack < monster[1]:
            remained_health = monster[1] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            #print(times)
            attack = times * A
            remain_attacks_queue.append([monster[0], attack])
            ans += times
            remain_attack += attack
        
    print(ans)
    

main()

Submission status: Accepted

Solution code:
import math
from bisect import bisect_right

n, d, a = map(int, input().split())
x_list = []
max_x = 0
for _ in range(n):
    x, h = map(int, input().split())
    x -= 1
    x_list.append([x, h])
    max_x = max(max_x, x)
x_list.sort()
xx = [x[0] for x in x_list]
hh = [x[1] for x in x_list]
ans = 0
accum = [0 for _ in range(n)]
for index, [x, h] in enumerate(x_list):
    if index != 0:
        accum[index] += accum[index - 1]
    cnt = max(math.ceil((hh[index] - accum[index]) / a),  0)
    ans += cnt
    index_right = bisect_right(xx, xx[index] + (2 * d))
    accum[index] += cnt * a
    if index_right < n:
        accum[index_right] -= cnt * a
print(ans)

Submission status: Accepted

Solution code:
import bisect
n, d, a = map(int, input().split())
fox = [None]*n
for i in range(n):
  x, h = map(int, input().split())
  fox[i] = (x, h)

fox.sort()
x = [int(fox[i][0]) for i in range(n)]
h = [int(fox[i][1]) for i in range(n)]

ans = 0
bit = [0]*n
for i in range(n):
  if i != 0:
    bit[i] += bit[i-1]
  if bit[i] >= h[i]:
    continue
  sub = (h[i]-bit[i]-1)//a+1
  ans += sub
  bit[i] += sub*a
  index = bisect.bisect_right(x, x[i]+2*d)
  if index == n:
    continue
  bit[index] -= sub*a
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys

def main():
  input = sys.stdin.readline
  n, d, a = map(int, input().split())
  fox = [None]*n
  for i in range(n):
    x, h = map(int, input().split())
    fox[i] = (x, h)

  fox.sort()
  x = [int(fox[i][0]) for i in range(n)]
  h = [int(fox[i][1]) for i in range(n)]

  ans = 0
  bit = [0]*n
  for i in range(n):
    if i != 0:
      bit[i] += bit[i-1]
    sub = max([(h[i]-bit[i]-1)//a+1, 0])
    ans += sub
    bit[i] += sub*a
    index = bisect.bisect_right(x, x[i]+2*d)
    if index != n:
      bit[index] -= sub*a
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,d,a=map(int,readline().split())
    xh=[list(map(int,readline().split())) for _ in range(n)]
    xh.sort()
    x=[0]*n
    h=[0]*n
    for i in range(n):
        x[i],h[i]=xh[i][0],xh[i][1]

    dq=deque()
    now=0
    cnt=0
    for i in range(n):
        if i==0:
            cnt+=(h[i]+a-1)//a
            now+=(h[i]+a-1)//a*a
            dq.append([x[i]+2*d,now])
        else:
            while len(dq)!=0 and dq[0][0]<x[i]:
                tmp=dq.popleft()
                now-=tmp[1]
            if h[i]<=now:
                pass
            else:
                dq.append([x[i]+2*d,(h[i]-now+a-1)//a*a])
                cnt+=(h[i]-now+a-1)//a
                now+=(h[i]-now+a-1)//a*a

    print(cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, d, a = map(int, input().split())

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    while dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
        else:
            break
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)

Submission status: Accepted

Solution code:
N,D,A=map(int, input().split())
B=[list(map(int, input().split())) for _ in range(N)]
C=sorted(B)
d,E=zip(*C)
import bisect
Damage=[0]*N
for i in range(N):
  e=bisect.bisect_right(d,d[i]+2*D)
  Damage[i]=e
dd=[0]*(N+1)
cnt=0
for i in range(N):
  if i!=0:
    dd[i]+=dd[i-1]
  h=E[i]
  h-=dd[i]
  if h>0:
    bomb=-(-h//A)
    cnt+=bomb
    dd[i]+=A*bomb
    dd[Damage[i]]-=A*bomb
print(cnt)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque

n, d, a = map(int, input().split())
m = sorted([list(map(int, input().split())) for _ in range(n)])
m = [[x, ceil(h / a)] for x, h in m]

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    rest_h = max(0, h - acc_damage)
    ans += rest_h
    acc_damage += rest_h

    if rest_h:
        que.append([x + 2 * d, rest_h])

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque

n, d, a = map(int, input().split())
m = sorted([list(map(int, input().split())) for _ in range(n)])
m = [[x, ceil(h / a)] for x, h in m]

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

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

    if need:
        que.append([x + 2 * d, need])

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

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

    if need:
        que.append([x + 2 * D, need])

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect
def main():
    n,d,a=map(int,input().split())
    XH=[list(map(int,input().split())) for i in range(n)]
    XH.sort()
    X,H=zip(*XH)
    right=[0]*n
    for i,x in enumerate(X):
        right[i]=bisect(X,x+2*d)
    damage=[0]*(n+1)
    ans=0
    for i,(x,h) in enumerate(XH):
        if i!=0:
            damage[i]+=damage[i-1]
        h-=damage[i]
        if h>0:
            cunt=-(-h//a)
            ans+=cunt
            damage[i]+=a*cunt
            damage[right[i]]-=a*cunt
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
from collections import deque
damage = deque()
dmg = 0
for x,h in enemies:
    if len(damage) == 0:
        bomb = -(-h//A)
        damage.append([x+2*D,bomb])
        dmg += bomb*A
        ans += bomb
    else:
        while len(damage) > 0:
            d,bomb = damage.popleft()
            if x > d:
                dmg -= bomb*A
            else:
                damage.appendleft([d,bomb])
                break
        if h > dmg:
            bomb = -(-(h-dmg)//A)
            dmg += bomb*A
            damage.append([x+2*D,bomb])
            ans += bomb

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, D, A = MAP()
XH = [LIST() for _ in range(N)]
XH.sort(key=lambda x:x[0])
X, H = zip(*XH)
right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

damage = [0]*(N+1)
ans = 0
for i, (X, H) in enumerate(XH):
	if i != 0:
		damage[i] += damage[i-1]
	H -= damage[i]
	if H > 0:  # 追加攻撃が必要
		n = -(-H//A)
		ans += n
		d = A*n
		damage[i] += d
		damage[right[i]] -= d  # 範囲外の敵
print(ans)

Submission status: Accepted

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

def main():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)
 
        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2
 
        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2
 
        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret
 
    N, D, A = map(int,readline().split())
    X = [list(map(int,readline().split())) for _ in range(N)]
    X.sort()
    L = [0]*N
    for i in range(N):
        L[i] = X[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i,[x,h] in enumerate(X):
        H = h - S.query(i)
        if H<=0:
            continue
        ind = bisect.bisect(L,x+2*D)
        need = (H-1)//A + 1
        S.update(i,ind,need*A)
        ans += need
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    bom = deque()
    cur = 0
    for i, mi in enumerate(mon):

        while len(bom) != 0 and bom[0][0] < mi[0]:
            b = bom.popleft()
            cur -= b[1]

        if mi[1] <= cur:
            continue
        else:
            b1 = mi[1] - cur
            bom.append((mi[0] + 2 * d, b1))
            cur += b1
            ans += b1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
def main():
    N,D,A = map(int, input().split())
    # 座標X[i]のモンスターはceil(H[i]/A)回攻撃すれば倒せる
    # N=5, D=2
    # 0 1 2 3 4 5 6 7 8 9 10
    # 0 5 0 2 0 0 3 3 0 0 4 (倒すのに必要な回数; 全部0にすれば終了)
    # 0 0 0 0 0 0 3 3 0 0 4 (座標3で5回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 1 (座標8で3回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 0 (座標10で1回爆破したあと)
    # ->よって5+3+1=9回が最小回数..?

    Monsters = sorted([list(map(int, input().split())) for i in range(N)])
    Monsters = [[x-1, ceil(h / A)] for x, h in Monsters]

    acc_damage = 0
    que = deque([])

    ans = 0
    for x, h in Monsters:
        # 期限切れの蓄積ダメージを削除
        while que and x > que[0][0]:
            limit, damage = que.popleft()
            acc_damage -= damage

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

        if need:
            que.append([x + 2 * D, need])

    print(ans)


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, d, a = map(int, input().split())
actions = []
for _ in range(n):
    x, h = map(int, input().split())
    heappush(actions, (x, 0, (h + a - 1) // a))
cnt = 0
bomb = 0
current_bomb = 0
while cnt < n:
    a, c, b = heappop(actions)
    if c:
        current_bomb -= b
        continue
    else:
        HP = b
        if HP <= current_bomb:
            cnt += 1
            continue
        else:
            HP -= current_bomb
            cnt += 1
            current_bomb += HP
            bomb += HP
            heappush(actions, (a + 2 * d, 1, HP))
print(bomb)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, d, a = list(map(int, readline().split()))
    xh = [list(map(int, readline().split())) for _ in range(n)]

    from operator import itemgetter, add
    import bisect

    xh.sort(key=itemgetter(0))
    coordinate = [xh[i][0] for i in range(n)]
    hp = [xh[i][1] for i in range(n)]

    ans = 0
    dmg_cur = 0
    dmg_cum = [0] * (n + 1)

    for i in range(n):
        x = coordinate[i]
        h = hp[i]

        dmg_cur += dmg_cum[i]
        h -= dmg_cur

        if h > 0:
            num = (h + a - 1) // a
            ans += num
            dmg = a * num
            dmg_cur += dmg
            range_left = x
            range_right = x + 2 * d
            index_right = bisect.bisect_right(coordinate, range_right)
            dmg_cum[index_right] -= dmg
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, D, A = list(map(int, input().split()))
pair_xh = [[-1, -1] for _ in range(N)] # 1回ずつしか使わないけどソートするから必要
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))
pair_xh.sort(key = lambda x: x[0]) #座標でソート

q_lim_d = deque() # 累積和に含まれる攻撃範囲とダメージを保存する場所
total = 0 # 喰らいダメージの累積和
count = 0 # 攻撃回数
for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    while len(q_lim_d) and q_lim_d[-1][0] < x: # 範囲外になったら喰らわないから累積和から外す
        total -= q_lim_d[-1][1]
        q_lim_d.pop()
    h -= total
    if h > 0: # 見てる敵の体力が0になる攻撃回数を求めその分を累積和に足す
        times = (h + A - 1) // A # 0にするのに必要な回数(切り上げ)
        count += times
        damage = A * times
        total += damage
        q_lim_d.appendleft([x + 2 * D, damage])
print(count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,D,A = LI()
    X = []; XH = []
    for _ in range(N):
        x,h = LI()
        X.append(x); XH.append((x,h))
    XH.sort()
    X.sort()
    down = [0] * (N+1)


    p = 0
    ans = 0
    for i in range(N):
        if p < XH[i][1]:
            b = -(-(XH[i][1]-p)//A)
            ans += b
            p += b * A
            down[bisect.bisect(X,X[i]+2*D)-1] += b*A
        p -= down[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for _ in range(n)]
xh.sort()

ans = 0
att = [0]*n
cnt = 0
f = []
f1 = [0]*n

for x,h in xh:
    f.append(h)

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

for i in range(n):
    if f[i] > 0:
        da = -(-f[i]//a)
        ans += da
        f1[i] -= da * a
        if att[i]+1 < n:
            f1[att[i]+1] += da * a
    if i < n-1:
        f1[i+1] += f1[i]
        f[i+1] += f1[i+1]
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
xh = deque(xh)

xh_field = deque()

cnt = 0
now_damage = 0
while xh:
    pos, hp = xh.popleft()
    if xh_field:
        while (xh_field and xh_field[0][0] < pos) :
            now_damage -= a * xh_field[0][1]
            xh_field.popleft() 
    if hp <= now_damage:
        pass
    elif hp > now_damage:
        atk_cnt = math.ceil((hp - now_damage) / a)
        cnt += atk_cnt
        now_damage += atk_cnt * a
        xh_field.append((2*d + pos, atk_cnt))        
print(cnt)

Submission status: Accepted

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

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

xh.sort()

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

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

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

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

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

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

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

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

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

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

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)

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

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

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

print(ans)

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
def solve():
    N,D,A = map(int,input().split())
    monster = []
    for i in range(N):
        x,h = map(int,input().split())
        monster.append([x,h])
    
    monster.sort(key=lambda x:x[0])

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#problems2
#silver fox vs monster
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
import sys 
input = sys.stdin.readline
N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh = sorted(xh)
total = 0 # 今与えているダメージの総和
D = 2*D
ans = 0
q = deque()
for i in range(N):
  x, h = xh[i]
  # 今いる場所が前回までの爆撃の範囲外になるならその分totalから引く
  while len(q) >= 1 and q[0][0] < x:
    total -= q.popleft()[1]
  h -= total

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

from math import ceil

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

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

C = [0]  #C[i] = (X[j] <= X[i]+2*D たる最大の j)
for i in range(1,N+1):
    a = i
    b = N+1
    while a+1 < b:
        mid = (a+b)//2
        if B[mid][0] <= B[i][0] + 2*D:
            a = mid
        else:
            b = mid
    C.append(a)

D = [0]*(N+2)  #D[i] = (i番目の敵が攻撃される回数)
ans = 0
for i in range(1,N+1):
    D[i] = max(0,D[i-1]+D[i])
    if D[i] >= B[i][1]:
        continue
    else:
        k = -D[i]+B[i][1]
        D[i] += k
        D[C[i]+1] -= k
        ans += k
print(ans)