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:
#!/usr/bin/env python3

import sys
import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, d, a = mi()
    monsters = sorted([lmi() for _ in range(n)])
    monster_points = []
    monster_hps= []
    for pair in monsters:
        monster_points.append(pair[0])
        monster_hps.append(pair[1])
    
    # どの monster_points[ind] での ind の表すモンスターまで巻き込めるか (右端)
    right_end_monster_ind = [0] * (n)
    for i in range(n):
        right_end_monster_ind[i] = bisect_right(monster_points, monster_points[i]+2*d) - 1
    
    # print(right_end_monster_ind)
    imos_list = [0] * (n+1)
    damage = 0
    ans = 0
    for i in range(n):
        damage += imos_list[i]
        rest_hp = max(0, monster_hps[i] - damage)
        # print("rest {}".format(rest_hp))
        cnt = math.ceil(rest_hp / a)
        ans += cnt
        imos_list[i+1] += (a * cnt)
        imos_list[right_end_monster_ind[i]+1] -= (a * cnt)
        # print(imos_list)
    
    print(ans)    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n, d, a = [int(i) for i in input().split()]
  chk = []
  for i in range(n):
    x, h = [int(i) for i in input().split()]
    chk.append((x, 0, h))

  from heapq import heapify, heappop, heappush
  heapify(chk)
  atk_cnt = 0; ans = 0
  while chk:
    x, t, h = heappop(chk)
    if t == 0:
      if atk_cnt * a >= h:
          continue
      remain = h - atk_cnt * a
      new_atk = (remain - 1) // a + 1
      heappush(chk, (x + 2 * d, 1, new_atk))
      ans += new_atk
      atk_cnt += new_atk
    else:
      atk_cnt -= h
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,d,A = inpl()
d *= 2
xh = [inpl() for _ in range(n)]
xh.sort()
ln = 1
f = [0]
a = [0]
for i in range(n):
    x,h = xh[i]
    r = bisect_left(f,x+d)
    l = bisect_left(f,x)
    tmp = a[r-1] - a[l-1]
    # print(i,l,r)
    h -= tmp * A
    if h > 0:
        ind = x + d
        att = (h+A-1)//A
        f.append(ind)
        a.append(a[-1] + att)
        ln += 1
# print(f,a)
print(a[-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Mon = namedtuple('Mon', 'x h')  # 座標xにライフh
    Eff = namedtuple('Eff', 'x cnt')  # [,x]区間にcnt回爆発

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

    ms = []
    for _ in range(N):
        x, h = map(int, input().split())
        m = Mon(x=x, h=h)
        ms.append(m)

    ms.sort(key=attrgetter('x'))

    dq = deque()

    effect = 0
    cnt = 0
    for m in ms:
        while dq and dq[0].x < m.x:
            e = dq.popleft()
            effect -= e.cnt * A
        need_dmg = max(0, m.h - effect)
        if need_dmg:
            need_cnt = (need_dmg + A - 1) // A
            e = Eff(x=m.x + D * 2, cnt=need_cnt)
            dq.append(e)
            effect += need_cnt * A
            cnt += need_cnt
    print(cnt)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
# n, d, a = 9, 2, 2
# X = [1, 3, 4, 6, 9, 10, 12, 13, 16]
# H = [7, 6, 7, 5, 10, 3, 8, 9, 6]
X.append(10**10)
H.append(0)
j = 0
c = 0
S = [0]*(n+1)
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + -(-H[i]//a)*a
    S[j] -= -(-H[i]//a)*a
    # print(i)
    # print(H)
    # print(S)
# print(H)
# print(S)
print(c)

Submission status: Accepted

Solution code:
import math
N,D,A = map(int,input().split())
l = []
for i in range(N):
  l.append(list(map(int,input().split())))
l.sort()  
lx = []
lc = []
for i in l:
  X,H = i[0],i[1]
  lx.append(X)
  lc.append(math.ceil(H/A))

migi = []
m = 0
i = 0
while i <= N-1:
  if lx[m] - lx[i] > 2*D:
    migi.append(m)
    i += 1
  elif m != N-1:
    m += 1
  elif m == N-1:
    migi.append(-1)
    i += 1 

cnt = 0
dam = [0 for i in range(N)]
for i in range(N):
  if dam[i] < lc[i]:
    c = lc[i] - dam[i]  
    dam[i] += c
    if migi[i] >= 0:
      dam[migi[i]] -= c
    cnt += c
  if i <=N-2:
    dam[i+1] += dam[i]   
print(cnt)

Submission status: Accepted

Solution code:
# imos解
n,d,a=map(int,input().split())
xh=[]
for i in range(n):
  xx,hh=map(int,input().split())
  xh.append([xx,hh])
xh.sort(key=lambda x:x[0])
xl=[x for x,h in xh]
# print(xh)
from math import ceil
from bisect import bisect_right

ans=0
damage=[0]*(n+1)

for i in range(n):
  x,h=xh[i]
  if damage[i]<h:
    need=ceil((h-damage[i])/a)
    right=x+2*d
    # 爆発に巻き込まれる範囲の右端のindexを取得する
    r_idx=bisect_right(xl,right)
    # imosしながら爆発させる
    damage[i]+=need*a
    damage[r_idx]-=need*a
    ans+=need
  # imosの累積和を取る
  damage[i+1]+=damage[i]
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque
N,D,A = map(int,input().split(' '))
XHn = [ list(map(int,input().split(' '))) for _ in range(N)]
ans = 0
XHn.sort()
attacks = deque([]) # (区間,攻撃回数)
attack = 0
ans = 0
for i  in range(N):
    x = XHn[i][0]
    h = XHn[i][1]
    while len(attacks) > 0 and x > attacks[0][0]:
        distance,attack_num = attacks.popleft()
        attack -= attack_num*A
    if h > attack:
        diff = h - attack 
        distance_attack = x + D*2
        need_attack = math.ceil(diff/A)
        attacks.append((distance_attack,need_attack))
        attack += A*need_attack
        ans += need_attack
print(ans)

Submission status: Accepted

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

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

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
# いつ効力が切れるか記録
z=[0]*(n+1)
# 今の攻撃力
atk=0
for i in range(n):
    atk+=z[i]
    if x[i][1]-atk>0:
        ans+=x[i][1]-atk
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        z[q]-=x[i][1]-atk
        atk+=x[i][1]-atk
print(ans)

Submission status: Accepted

Solution code:
import bisect
import math
N,D,A=map(int,input().split())
tmp=[list(map(int,input().split())) for i in range(N)]
tmp.sort(key=lambda x:x[0])
monster=[];X=[]
for i in range(N):
    monster.append(tmp[i][1]);X.append(tmp[i][0])
minus=[0]*(N+1)
ans=0
damage=0
for i in range(N):
    damage-=minus[i]
    monster[i]=max(0,monster[i]-damage)
    if(monster[i]==0):
        continue
    cnt=math.ceil(monster[i]/A)
    monster[i]=0
    ans+=cnt
    b=bisect.bisect_left(X,X[i]+2*D+1)
    minus[b]+=cnt*A
    damage+=A*cnt
print(ans)

Submission status: Accepted

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

def main():
    N, D, A = map(int, input().split())
    monsters = sorted([list(map(int, input().split())) for _ in range(N)])
    
    for i in range(N):
        monsters[i][1] = (monsters[i][1] + A - 1) // A
    
    attacks = deque([]) # [(有効範囲, 攻撃回数)]
    ans = 0
    atk = 0
    for i in range(N):
        atk_this = monsters[i][1]
        while attacks and monsters[i][0] > attacks[0][0]:
            _, atk_ = attacks.popleft()
            atk -= atk_
        if atk_this - atk > 0:
            ans += atk_this - atk
            attacks.append((monsters[i][0]+2*D, atk_this-atk))
            atk += atk_this - atk
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

out = [0]*(n+1)
ans = 0
accu = 0
for ind, (x, h) in enumerate(xh):
    accu -= out[ind]
    h -= accu
    if h<=0:
        continue
    ans += (h+a-1)//a
    accu += ((h+a-1)//a)*a
    out[bisect(x+2*d)] += ((h+a-1)//a)*a
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,d,a = map(int,input().split())
f = [list(map(int,input().split()))for i in range(n)]
queue = deque()
f.sort()
tot = 0
ans = 0
for i in range(n):
    x = f[i][0]
    h = f[i][1]
    while queue and queue[0][0] < x:
        now = queue.popleft()
        tot -= now[1]
    h -= tot
    if h > 0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        tot+=damage
        queue.append((x+2*d,damage))
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import math
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LIR(n):
    return [LI() for i in range(n)]

class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

def solve():
    n,d,a = LI()
    g = LIR(n)
    g.sort()
    X = [i for (i,_) in g]
    s = SegmentTree(n)
    ans = 0
    for i in range(n):
        x = g[i][0]
        j = bisect.bisect_left(X,x-2*d)
        h = g[i][1]-s.get(j,i)
        if h <= 0:
            continue
        k = math.ceil(h/a)
        ans += k
        s.update(i,k*a)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import math
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LIR(n):
    return [LI() for i in range(n)]

class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

def solve():
    n,d,a = LI()
    g = LIR(n)
    g.sort()
    X = [i for (i,_) in g]
    s = SegmentTree(n)
    ans = 0
    for i in range(n):
        x = g[i][0]
        j = bisect.bisect_left(X,x-2*d)
        h = g[i][1]-s.get(j,i+1)
        if h <= 0:
            continue
        k = math.ceil(h/a)
        ans += k
        s.update(i,k*a)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

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

ans = 0
bomb = []
SUMD = 0 # ダメージの総和
for x, h in XH:
    while bomb:
        right, damage = heappop(bomb)
        if right < x:
            SUMD -= damage
        else:
            heappush(bomb, (right, damage))
            break
    h -= SUMD
    if h > 0:
        cnt = (h + A - 1) // A
        SUMD += cnt * A
        heappush(bomb, (x + 2 * D, cnt * A))
        ans += cnt

print(ans)

Submission status: Accepted

Solution code:
import math
import collections
N, D, A = map(int, input().split())

XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q and q[0][0] < x):
        c -= q[0][1]
        q.popleft()
    h -= c * A
    if h < 0:
        h = 0
    ans += math.ceil(h/A)
    c += math.ceil(h/A)

    q.append((x+2*D, math.ceil(h/A)))

print(ans)

Submission status: Accepted

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

x.sort()
for i in range(n):
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # ダメージの有効期限を超過している場合
    while len(qq)>0 and x[i][0] > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        # 有効期限　ダメージ
        qq.append([x[i][0]+2*d,w-atk])
        atk += w - atk
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
INF = 10**18
x_list = [x for x, h in xh]
x_list.append(INF)

end_idx_list = [0]*n
idx = 0
for i in range(n):
    while True:
        if x_list[i]+2*d < x_list[idx]:
            end_idx_list[i] = idx
            break
        idx += 1

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    if 0 < h:
        cnt = -(-h//a)
        ans += cnt
        damage[i] += cnt*a
        end_idx = end_idx_list[i]
        damage[end_idx] -= cnt*a

    damage[i+1] += damage[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
x_list = [x for x, h in xh]

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    if h <= 0:
        damage[i+1] += damage[i]
        continue
    cnt = -(-h//a)
    ans += cnt
    damage[i] += cnt*a
    end_idx = bisect.bisect_right(x_list, x+2*d)
    damage[end_idx] -= cnt*a
    damage[i+1] += damage[i]

print(ans)

Submission status: Accepted

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

data0=[0]*(n+1)
data1=[0]*(n+1)

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

def add(l,r,x):
  _add(data0,l,-x*(l-1))
  _add(data0,r,x*(r-1))
  _add(data1,l,x)
  _add(data1,r,-x)

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

def query(l,r):
  return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)

x=[]
for i in range(n):
  x.append(l[i][0])
  add(i+1,i+2,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p+1,p+2)
  add(p+1,Right[p]+1,-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p+1,p+2)<=0:
    p+=1
    if p==n:
      break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# F
# queueの使い方、累積ダメージの更新の仕方がポイント
# 参考：https://atcoder.jp/contests/abc153/submissions/9750027

'''
3 3 2
1 2
5 4
9 2
'''

from collections import deque

N, D, A = map(int, input().split())
a = sorted(list(map(int, input().split())) for _ in range(N))
D *= 2

bomb_queue = deque()
bomb_dmg = 0
ans = 0

for x, h in a:
    # 過去の爆弾が有効でない座標に達していれば、その爆弾を捨て、累積ダメージからも差し引く
    while bomb_queue and bomb_queue[0][0] < x:
        # deque.popleft : 左側から要素を削除し、値を返す
        bomb_dmg -= bomb_queue.popleft()[1]

    # これまでの累積ダメージを差し引く
    h -= bomb_dmg
    if h > 0:
        # このモンスターを倒すのに必要な回数
        cnt = (h + A - 1) // A
        ans += cnt
        # x + Dまでダメージが与えられる
        # deque.append : 右側に付け加える
        bomb_queue.append((x + D, cnt * A))
        bomb_dmg += cnt * A

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]

atack = np.zeros(N+1, np.int64)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, D, A = map(int, input().split())
XH = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort(key=lambda x: x[0])
D = 2 * D
tot = 0
q = deque()
ans = 0
for i in range(N):
    x, h = XH[i]
    while 0 < len(q) and q[0][0] < x:
        tot -= q[0][1]
        q.popleft()
    h -= tot
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        tot += damage
        q.append((x + D, damage))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
    
#solve
def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 0
    rdi = 0
    bit = BinaryIndexedTree(n+1)
    for i in range(n):
        x, h = xh[i]
        h -= bit.sum(i)
        if h > 0:
            t = (h - 1) // a + 1
            for rdi in range(rdi, n):
                if x + 2 * d < xh[rdi][0]:
                    rdi -= 1
                    break
            ans += t
            bit.add(rdi + 1, -t * a)
            bit.add(i, t * a)

    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

N, D, A = map(int, input().split())
mons = []
for _ in range(N):
    X, H = map(int, input().split())
    mons.append((X, (H + A - 1) // A))
mons.sort()

ans = 0
q = deque([])
tot = 0
for x, h in mons:
    while q:
        x0, h0 = next(iter(q))
        if x - 2 * D <= x0:
            break
        tot -= h0
        q.popleft()
    h = max(0, h - tot)
    ans += h
    tot += h
    q.append((x, h))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
from collections import deque
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0
q=deque()
q_sum = 0

for x,h in xh:
    while len(q) > 0:
        bx, bh = q[0]
        if bx < x:
            q.popleft()
            q_sum -= bh
        else:
            break
    h -= q_sum
    if h > 0:
        q.append((x+2*d, h))
        q_sum += h
        res += h

print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil
from bisect import bisect_right

n, d, a = map(int, readline().split())
xh = [list(map(int, readline().split())) for i in range(n)]
xh.sort()
imos = [0] * (n + 1)
cnt = 0
ans = 0
x = []
for i in range(n):
    xh[i][1] = ceil(xh[i][1] / a)
    x.append(xh[i][0])
for i in range(n):
    cnt += imos[i]
    n_h = xh[i][1] - cnt
    if n_h > 0:
        cnt += n_h
        ans += n_h
        imos[bisect_right(x, x[i] + 2 * d)] -= n_h
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    # 左からgreedyに
    N, D, A = lr()
    monsters = []
    for _ in range(N):
        x, h = lr()
        monsters.append((x, h))

    monsters.sort()
    bomb = deque()
    answer = 0
    attack = 0
    for x, h in monsters:
        while bomb:
            if bomb[0][0] + D < x:
                attack -= bomb[0][1]
                bomb.popleft()
            else:
                break
        h -= attack
        if h > 0:
            t = -(-h//A)
            answer += t
            bomb.append((x + D, A * t))
            attack += A * t

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

readline = sys.stdin.readline
sr = lambda: readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左からgreedyに
N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
attack = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            attack -= bomb[0][1]
            bomb.popleft()
        else:
            break
    h -= attack
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, A * t))
        attack += A * t

print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左からgreedyに
N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
attack = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            attack -= bomb[0][1]
            bomb.popleft()
        else:
            break
    h -= attack
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, A * t))
        attack += A * t

print(answer)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import math
n, d, A = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
xh.sort(key=lambda x: x[0])

monster_x = []
monster_hp = []
for i in range(n):
    monster_x.append(xh[i][0])
    monster_hp.append(xh[i][1])

dist = 2 * d
ans = 0
damage = 0
cum_damage = [0] * (n + 1)
for i in range(n):
    cum_damage[i + 1] += cum_damage[i]
    damage = cum_damage[i + 1] * A
    if damage < monster_hp[i]:
        min_attack_num = math.ceil((monster_hp[i] - damage) / A) 
        index = bisect.bisect_right(monster_x, monster_x[i] + dist)
        cum_damage[i + 1] += min_attack_num
        if index < n:
            t = min(index + 1, n)
            cum_damage[t] -= min_attack_num
        ans += min_attack_num

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque

N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, math.ceil(h/A)))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 # 有効なダメージ合計
for i in range(N):
    x, h = data[i]

    # 爆破範囲が届いていなければ削除していく
    while damage_que and x > damage_que[0][0]:
        _, a = damage_que.popleft()
        attack -= a
    
    # 有効な過去の爆破攻撃を受ける
    remain = max(h - attack, 0)
    # 0になるまで爆破    
    attack += remain
    c += remain

    # 爆破回数追加    
    damage_que.append([x+2*D, remain])

print(c)