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:
def resolve():
    N, D, A = map(int, input().split())
    lXH = []
    while True:
        try:
            x, h = map(int, input().split())
            lXH.append([x, h])
        except:
            break
    lXHs = sorted(lXH, key=lambda k: k[0])
    from collections import deque
    q = deque()
    tot = 0
    ans = 0
    for i in range(N):
        x, h = lXHs[i]
        while len(q) > 0 and q[0][0] < x:
            qx, qh = q.popleft()
            tot -= qh
        h -= tot
        if h > 0:
            num = (h+A-1)//A
            ans += num
            dam = num*A
            tot += dam
            q.append([x+2*D, dam])
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    s = S[i]
    rec = h-s
    if rec<=0:
      S[i+1]+=s
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (rec+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=s+y
  print(ans)
main()

Submission status: Accepted

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

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT2:
    """ 区間加算BIT(区間加算・区間合計取得) """

    def __init__(self, N):
        # 添字0が使えないので、内部的には全て1-indexedとして扱う
        N += 1
        self.N = N
        self.data0 = [0] * N
        self.data1 = [0] * N

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

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

    def add(self, l, r, x):
        """ 区間[l,r)に値xを追加 """

        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def query(self, l, r):
        """ 区間[l,r)の和を取得 """

        return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
             - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

N, D, K = MAP()

XH = []
for i in range(N):
    x, h = MAP()
    XH.append((x, h))

XH.sort()
X, H = zip(*XH)
D = D * 2

bit = BIT2(N)
ans = 0
for i, (x, h) in enumerate(XH):
    h -= bit.query(i, i+1) * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D) - 1
    bit.add(i, idx+1, cnt)
    ans += cnt
print(ans)

Submission status: Accepted

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

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小(大)値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, D, K = MAP()

XH = []
for i in range(N):
    x, h = MAP()
    XH.append((x, h))

XH.sort()
X, H = zip(*XH)
D = D * 2

sst = StarrySkyTree(N, max, 0)
ans = 0
for i, (x, h) in enumerate(XH):
    h -= sst.query(i, i+1) * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D) - 1
    sst.update(i, idx+1, cnt)
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from heapq import heappush, heappop

def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]
    # n = 5
    # d = 1
    # a = 3
    # xh = [[0, 7],[1, 9], [2, 10], [4, 15], [20, 8]]

    xh = [[]] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    xh.sort()

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

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = remaining_life // a
        if remaining_life % a:
            needed += 1
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = XH[::2] + [-1]
H = XH[1::2] + [-1]
D *= 2
X, H = zip(*sorted(zip(X, H)))

damages = [0] * (N + 2)
answer = 0

for i in range(1, N + 1):
    damages[i] += damages[i - 1]
    h = H[i]
    if damages[i] >= h:
        continue
    else:
        h -= damages[i]

    x = X[i]
    cnt = (h + A - 1) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D)] -= damage

print(answer)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = XH[::2]
H = XH[1::2]
D *= 2
X, H = zip(*sorted(zip(X, H)))

damage = [0] * (N + 1)
answer = H[0] // A + min(1, H[0] % A)
damage[0] += A * answer
damage[bisect_right(X, X[0] + D)] -= A * answer

for i in range(1, N):
    damage[i] += damage[i - 1]
    h = H[i]
    x = X[i]
    if damage[i] >= h:
        continue
    else:
        h -= damage[i]

    cnt = h // A + min(1, h % A)
    answer += cnt
    damage[i] += A * cnt
    damage[bisect_right(X, x + D)] -= A * cnt

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
input = sys.stdin.readline
 
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(key=lambda xh: xh[0])
que = deque()
D = 2*D
 
H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
que.append([XH[0][0]+D,a*A])
tot = a * A
ans = a
for i in range(1,N):
	while XH[i][0] > que[0][0] :
		tot -= que[0][1]
		que.popleft()
		if(len(que)==0): break
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N,D,A = map(int,input().split())
mons = [list(map(int,input().split())) for i in range(N)]
for i in range(N):
    mons[i][1] = (mons[i][1]+A-1)//A

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

damages = deque()
nowdmg = 0
ans = 0
for i in range(N):
    while len(damages) != 0:
        if mons[i][0] >= damages[0][0]+1:
            rec = damages.popleft()
            nowdmg += rec[1]
        else:
            break
    if mons[i][1]+nowdmg > 0:
        c = mons[i][1]+nowdmg
        ans += c
        damages.append([mons[i][0]+2*D,c])
        nowdmg -= c

#print(mons)
print(ans)

Submission status: Accepted

Solution code:
import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
count = 0
min_x = 0
acm = [0] * (n + 1)
dif = [0] * (n + 1)
while min_x < n:
    place = x[min_x] + d
    num = (h[min_x] - acm[min_x + 1] - 1) // a + 1
    count += num
    dif[min_x] += num
    dif[bisect.bisect(x, place + d)] -= num
    for i in range(min_x, bisect.bisect(x, place + d)):
        acm[i + 1] = acm[i] + dif[i] * a
        if acm[i + 1] >= h[i]:
            min_x += 1
            continue
        else:
            break
print(count)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,D,A=map(int,input().split())
XH=[list(map(int,input().split())) for i in range(N)]
XH=sorted(XH,key=lambda x:x[0])

lst=[]
bomb=[]
count=0
nowbomb=0
idx=0
#print(XH)
for x,h in XH:
    #print(lst,bomb)
    if lst:
        while idx<len(lst) and lst[idx]<x-D:
            nowbomb-=bomb[idx]
            idx+=1
    #print(nowbomb)
    a=h-nowbomb
    if a>0:

        b=a//A+(a%A>0)*1
        #print(a,b)
        nowbomb+=b*A
        count+=b
        lst.append(x+D)
        bomb.append(b*A)

print(count)

Submission status: Accepted

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

que = deque([])
ans = 0
total = 0

for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue
    while que and XH[i][0] > que[0][0]:
        _, tmp = que.popleft()
        total -= tmp

    h -= total
    if h > 0:
        atk = (h + A - 1) // A
        damage = atk * A
        ans += atk
        total += damage
        que.append((x+2*D, damage))

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]
class StarrySkyTree:
    # Range Minimum Query
    def __init__(self, N):
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.INF = 2**31 - 1
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1

        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小値を求める
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


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

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

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

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i,i+1)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

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

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

XH.sort()

# 以下、1-based
# [0]はダミー
X = [-1]
H = [0]
for x, h in XH:
  X.append(x)
  H.append(h)


# J[i] = i番目のモンスターが左端で攻撃を受ける際に、
#最も右側で攻撃を受けるモンスターのインデックス
J = [0]
for x in X[1:]:
  J.append(bisect.bisect_left(X, x+W+1))


damage = [0]*(N+1)
ans = 0
for i in range(1, N+1):
  damage[i] += damage[i-1]
  H[i] -= damage[i]
  x, h = X[i], H[i]
  if h <= 0:
    continue
  
  count = -(-h//A)
  ans += count
  dmg = count*A
  damage[i] += dmg
  if J[i] <= N:
    damage[J[i]] -= dmg # 攻撃範囲外への影響をなくすために先に引いておく

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)

not_imos=[0]*(n+1)
atk_n=0
ans=0
for i in range(n):
  atk_n-=not_imos[i]
  h[i]-=atk_n*a
  if h[i]<0:h[i]=0
  atk_i=0--h[i]//a
  ans+=atk_i
  atk_n+=atk_i
  not_imos[bisect_right(x,x[i]+d*2)]+=atk_i
print(ans)

Submission status: Accepted

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

    mon = namedtuple('mon', 'x h')

    N, D, A = map(int, readline().split())
    mons = []
    for _ in range(N):
        x, h = map(int, readline().split())
        mons.append(mon(x=x, h=h))
    mons.sort(key=attrgetter('x'))

    imos = [0] * (N + 1)

    bomb = 0
    j = 0
    for i, mon in enumerate(mons):
        while (j + 1 < N) and (mons[j + 1].x - mon.x) <= D * 2:
            j += 1
        count = max(0, (mon.h - imos[i] * A + A - 1) // A)
        bomb += count

        imos[i] += count
        imos[j + 1] -= count

        imos[i + 1] += imos[i]

    print(bomb)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
ys = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,-(-H//A)))
ys.sort(key=lambda x : x[0])
li = dmg = r = 0
hs = [0]*N
for i, (y, h) in enumerate(ys):
    while ys[li][0]+2*D < y:
        dmg -= hs[li]
        li += 1
    hs[i] = max(0, h-dmg)
    dmg += hs[i]
    r += hs[i]
print(r)

Submission status: Accepted

Solution code:
from subprocess import*
call(("pypy3","-c","""
from bisect import*
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)
N,d,a,*t=map(int,open(0).read().split())
data0=[0]*(N+1)
data1=[0]*(N+1)
z=sorted(zip(*[iter(t)]*2))
y=[x for x,_ in z]
c=0
for i,(x,h)in enumerate(z,1):
    h-=query(i,i+1)
    t=0--max(0,h)//a
    j=bisect(y,x+d+d)
    add(1,j+1,t*a)
    c+=t
print(c)
"""))

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_right as br
    n, d, a = map(int, input().split())
    xh = [list(map(int, input().split())) for _ in [0]*n]
    xh.sort()
    x_list = [x for x, h in xh]
    ac = [0]*(n+1)
    ans = 0
    temp = 0
    for i in range(n):
        j = xh[i][1]-temp
        if j > 0:
            atk_cnt = (j-1)//a+1
            k = br(x_list, x_list[i]+2*d)-1
            ac[i] += a*atk_cnt
            ac[k] -= a*atk_cnt
            ans += atk_cnt
        temp += ac[i]
    print(ans)


main()

Submission status: Accepted

Solution code:
import bisect

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

XH.sort()
X, H = zip(*XH)

K = [-(-h // A) for h in H]
L = [0] * (N + 2)

ans = 0
for i in range(N):
    L[i + 1] += L[i]
    s = max(K[i] - L[i + 1], 0)
    ans += s
    L[i + 1] += s
    L[bisect.bisect_right(X, X[i] + 2 * D) + 1] -= s

print(ans)

Submission status: Accepted

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

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,-(-H//A)))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = dmg = r = 0
hs2 = [0]*N
for i, (y, h) in enumerate(ys):
    while l < y:
        dmg -= hs2[li]
        li += 1
        l = ys[li][0] + 2*D
    hs2[i] = max(0, h-dmg)
    dmg += hs2[i]
    r += hs2[i]
print(r)

Submission status: Accepted

Solution code:
N,D,A=map(int,input().split())
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  if X[i][1]>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        X[i][1]-=d[1]
    for p in dele:
      del damage[p]
  if X[i][1]>0:
    turn=(X[i][1]+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split(" "))
line = []
line_append = line.append
for i in range(N):
    x,h = map(int,input().split(" "))
    line_append((x,-(-h//A)))
line.sort()
X = list(map(lambda x: x[0],line))
dmg = [0 for _ in range(N+1)]
ans = 0
for i in range(N):
    x,h = line[i]
    h = max(0,h - dmg[i])
    dmg[i] += h
    dmg[bisect_right(X,x+2*D)] -= h
    dmg[i+1] += dmg[i]
    ans += h

print(ans)

Submission status: Accepted

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:
        #ms[i][1]-=tmp　二回引いてるわ
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

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

def ceil(x,y):
  return (x-1)//y+1


def solve_binary(mid,k):
    return k < XH[mid][0]

def binary_search(s,n,k):
    ok=n
    ng=s
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,k):
            ok=mid
        else:
            ng=mid
    return ok

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort(key=lambda tup: tup[0])
XH.append((inf,0))
data=[0]*(n+1)
# if D==0:
#     for xi,hi in XH:
#         count += ceil(hi,A)
#     print(count)
#     exit()
for i in range(n):
    xi,hi = XH[i]
    hi-=data[i]
    K=max(0,ceil(hi,A)*A); count += max(0,ceil(hi,A))
    data[i]+=K; data[binary_search(i,n,xi+2*D)]-=K
    data[i+1]+=data[i]
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()

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


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

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


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


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


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
dq = deque()
s_i = 0
sum_q = 0
for i in range(N):
    while dq and dq[0][1] < XH[i][0]:
        b, _ = dq.popleft()
        sum_q -= b

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        dq.append([bomb[i], XH[i][0] + 2 * D])

print(ans)

Submission status: Accepted

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

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,i))
    hs.append(-(-H//A))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = 0
dmg = 0
r = 0
for y, i in ys:
    while (not l >= y):
        li += 1
        l = ys[li][0] + 2*D
        dmg -= hs[ys[li-1][1]]
    tr = max(0, hs[i]-dmg)
    hs[i] = tr
    dmg += tr
    r += tr
print(r)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0 + D, h0))
    r = h0
    c = h0
    for x, h in XH:
        while Q and Q[0][0] < x:
            _, hh = Q.popleft()
            c -= hh
        h -= c
        if h > 0:
            Q.append((x + D, h))
            c += h
            r += h
    print(r)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    q = deque()
    ans = 0
    dmg = 0
    for i in range(N):
        while q and q[0][0] < X[i]:
            _, d = q.popleft()
            dmg -= d
        if H[i] <= dmg:
            continue
        ans += -(-(H[i] - dmg) // A)
        q.append((X[i]+2*D, (-(-(H[i] - dmg) // A))*A))
        dmg += (-(-(H[i] - dmg) // A))*A
    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


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)