Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Accepted

Solution code:
import bisect
import itertools
import sys

input=sys.stdin.readline

def main(args):
    n, d, a = map(int,input().split())
    
    monster = [0]*n
    pos = [0]*n
    for i in range(n):
        x, h = map(int,input().split())
        monster[i] = (x, -(-h//a))
        pos[i] = x
    
    pos.sort()
    monster.sort()
    
    limit = [0]*n
    #そのモンスターを攻撃したとき巻き添えにできるやつらの中で一番右のヤツのindex
    for i in range(n):
        limit[i] = bisect.bisect_right(pos, pos[i]+2*d)-1
    
    #print(limit)
    
    damage = [0]*(n+1)
    ans = 0
    for i in range(n):
        if damage[i] >= monster[i][1]:
            pass
        else:
            plus = monster[i][1] - damage[i]
            ans += plus
            damage[i] += plus
            damage[limit[i]+1] -= plus
        #print(damage)
        
        damage[i+1] += damage[i]
    
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    dq = deque([])
    damage = 0
    ans = 0

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

        if h > damage:
            dq.append((x + 2 * D, h - damage))
            ans += h - damage
            damage += h - damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    X = [x for x, h in monster]
    S = [0] * (N + 1)
    idx = 0
    ans = 0

    for i, (x, h) in enumerate(monster):
        d = h - S[i]
        if d > 0:
            right = x + 2 * D
            while idx < N and X[idx] <= right:
                idx += 1

            S[i] += d
            S[idx] -= d
            ans += d

        S[i + 1] += S[i]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0
    cur_damage = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            cur_damage += h - cur_damage

    print(sum(damage))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0
    cur_damage = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            cur_damage += h - cur_damage

    print(sum(damage))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    idx = 0

    cur_damage = 0
    ans = 0

    for x, h in monster:
        while idx < len(pos) and pos[idx] < x:
            cur_damage -= damage[idx]
            idx += 1

        if h > cur_damage:
            pos.append(x + 2 * D)
            damage.append(h - cur_damage)
            ans += h - cur_damage
            cur_damage += h - cur_damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, D, A, *XH = map(int, read().split())
    monster = [0] * N
    for i, (x, h) in enumerate(zip(*[iter(XH)] * 2)):
        monster[i] = (x, (h + A - 1) // A)

    monster.sort()

    pos = []
    damage = []
    left = right = 0

    cum_damage = 0
    ans = 0

    for x, h in monster:
        left = right
        right = bisect_left(pos, x)
        cum_damage -= sum(damage[left:right])

        if h > cum_damage:
            pos.append(x + 2 * D)
            damage.append(h - cum_damage)
            ans += h - cum_damage
            cum_damage += h - cum_damage

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

lxh.sort()
lx, lh = [], []
for x, h in lxh:
    lx.append(x)
    lh.append(h)

n_bomb = 0
total_damage = 0
subtract = [0 for _ in range(n + 1)]

for i in range(n):
    total_damage -= subtract[i]

    x = lx[i]
    h = lh[i] - total_damage

    if h > 0:
        n_bomb += -(-h // a)
        damage = -(-h // a) * a
        total_damage += damage

        i_sub = bisect_right(lx, x + 2 * d)
        subtract[i_sub] += damage

print(n_bomb)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    total = 0
    end = deque([])
    for i in range(n):
        x, h = XH[i]
        while end and end[0][0] < x:
            r = end.popleft()
            total -= r[1]

        if total < h:
            res += ((h - total) + a - 1) // a
            damage = ((h - total + a - 1) // a) * a
            total += damage
            end.append([x + 2 * d, damage])
    print(res)


if __name__ == '__main__':
    resolve()

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()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-1)//a+1
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

monsters.sort(key=lambda x: x[0])
xlst=[x for x,_ in monsters]

delta=[0]*(N+1)
csum=0

ans=0

for i in range(N):
    xi,hi=monsters[i]
    csum+=delta[i]
    hi-=csum

    if hi<=0:
        continue

    cnt=(hi+A-1)//A
    ans+=cnt

    csum+=A*cnt
    right=bisect_right(xlst,xi+2*D)
    delta[right]-=A*cnt

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,d,a = map(int, input().split())
xh = [None]*n
# h = [None]*n
for i in range(n):
    xh[i] = tuple(map(int, input().split()))
xh.sort()

r = 0
val = 0
from queue import deque
q = deque([])
s = 0
for l,(x,h) in enumerate(xh):
    bound = x+2*d
    while q and l>=q[0][1]:
        s -= q[0][0]
        q.popleft()
    while r<n and xh[r][0]<=bound:
        r += 1
    nokori = h - s
    if nokori>0:
        num = nokori//a + int(nokori%a!=0)
        val += num
        q.append((num*a, r))
        s += num*a
        
print(val)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### BIT 
def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

n,d,a = map(int, input().split())
xh = [None]*n
# h = [None]*n
for i in range(n):
    xh[i] = tuple(map(int, input().split()))
xh.sort()

bit = [0] * (n+1)
r = 0
val = 0
done = False
for l,(x,h) in enumerate(xh):
    bound = x+2*d
    while r<n and xh[r][0]<=bound:
        r += 1
    nokori = h + query(bit, l+1)
    if nokori>0:
#         print(nokori, a, l, r, bit)
        num = nokori//a + int(nokori%a!=0)
        val += num
        update(bit, l+1, -num*a)
        if r<n:
            update(bit, r+1, num*a)
print(val)

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 = sorted(XH)
ans = 0
total = 0
q = deque([])

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

  if h <= 0:
    continue
  attack = math.ceil(h/A)
  damage = attack*A
  total += damage
  q += [[x+2*D, damage]]
  ans += attack

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 = sorted(XH)
total = 0
D = 2*D
ans = 0
q = deque()
for x, h in XH:
  while len(q) and q[0][0] < x:
    total -= q.popleft()[1] 
  h -= total

  if h > 0:
    num = math.ceil(h/A)
    ans += num
    damage = num*A
    total += damage
    q += [[x+D, damage]]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans


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

    XHs.sort()
    Xs, Hs = [], []
    for X, H in XHs:
        Xs.append(X)
        Hs.append(H)

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for i in range(N):
        rest = getValue(i)
        if rest <= 0: continue
        pos = Xs[i] + D
        iR = bisect_right(Xs, pos + D) - 1
        num = -(-rest // A)
        ans += num
        damage = num*A
        addValue(iR, -damage)

    print(ans)


solve()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, d, a = ns()
    x = []
    for _ in range(n):
        xi, hi = ns()
        x.append([xi, hi])

    x.sort()
    x.append([INF, INF])

    perm = [0 for _ in range(n + 1)]
    idx = [xi for xi, hi in x]

    ans = 0
    cnt = 0
    for i in range(n):
        cnt -= perm[i]

        if x[i][1] - cnt * a > 0:
            tmp = ((x[i][1] - cnt * a) + a - 1) // a
        else:
            continue
        ans += tmp
        cnt += tmp

        if cnt > 0:
            tmp_idx = bisect.bisect_right(idx, x[i][0] + 2 * d)
            perm[tmp_idx] += tmp

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, d, a = ns()
    x = []
    for _ in range(n):
        xi, hi = ns()
        x.append([xi, hi])

    x.sort()
    x.append([INF, INF])

    perm = [0 for _ in range(n + 1)]
    idx = [xi for xi, hi in x]

    ans = 0
    cnt = 0
    for i in range(n):
        cnt -= perm[i]

        if x[i][1] - cnt * a > 0:
            tmp = ((x[i][1] - cnt * a) + a - 1) // a
        else:
            tmp = 0
        ans += tmp
        cnt += tmp

        if cnt > 0:
            tmp_idx = bisect.bisect_right(idx, x[i][0] + 2 * d)
            perm[tmp_idx] += tmp

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, D, A = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列
    S.sort()
    xs=[0]*N
    hs=[0]*N
    
    for i,s in enumerate(S):
        x,h=s
        xs[i]=x
        hs[i]=h
    tot=[0]*N
    accu=0
    count=0
    for i,x in enumerate(xs):
        accu+=tot[i]
        h=hs[i]-accu*A
        num=max(0,math.ceil(h/A))
        accu+=num
        count+=num
        ei=bisect_right(xs,x+2*D)
        if ei<N:
            tot[ei]-=num
    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

dic={}

ans=0
atk_cnt=0
while B:
    x,h=heappop(B)
    if h==-1:
        atk_cnt-=dic[x-1]
        continue
    if h<=A*atk_cnt:
        continue
    h-=A*atk_cnt
    sup=x+2*D
    bomb=(h-1)//A+1
    ans+=bomb
    dic[sup]=bomb
    atk_cnt+=bomb
    heappush(B,(sup+1,-1))
    
    
print(ans)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xi, hi = map(int, input().split())
    xh.append([xi, hi])

xh.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(xh[i][0])
    h.append(xh[i][1])

cnt = 0
dmg = [0 for i in range(n+1)]
for i in range(n):
    xi, hi = x[i], h[i]
    dmg[i] += dmg[i-1]
    hi -= dmg[i]
    if hi <= 0:
        continue
    else:
        num = (hi+a-1)//a
        cnt += num
    point = xi + 2*d
    left = i
    right = n
    while left+1 < right:
        mid = (left+right)//2
        if x[mid] <= point:
            left = mid
        else:
            right = mid
    dmg[i] += num*a
    dmg[left+1] -= num*a
print(cnt)

Submission status: Accepted

Solution code:
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i 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:
#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:
n, d, a = map(int, input().split())
xh = []
for _ in range(n):
    x, h = map(int, input().split())
    h = (h - 1) // a + 1
    xh.append([x, h])
xh.sort()
damage = xh[0][1]
ans = damage
damage_lst = [[xh[0][0] + d * 2, damage]]
pos = 0
for i, (x, h) in enumerate(xh[1:], start = 1):
    while x > damage_lst[pos][0]:
        damage -= damage_lst[pos][1]
        pos += 1
        if pos == i:
            break
    damage_tmp = max(h - damage, 0)
    ans += damage_tmp
    damage += damage_tmp
    damage_lst.append([x + d * 2, damage_tmp])
print(ans)

Submission status: Accepted

Solution code:
import bisect
import math

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

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

XH_array = sorted(XH_array, key=lambda x: x[0])

X_array = [xh[0] for xh in XH_array]

# print(X_array)

ans = 0
bomb_count = [0] * N
now_bomb = 0

for i, xh in enumerate(XH_array):
    # print(now_bomb, bomb_count)
    x, h = xh
    remain = h - A * now_bomb
    if remain <= 0:
        now_bomb += bomb_count[i]
        continue
    bomb_add = math.ceil(remain / A)
    ans += bomb_add
    bomb_count[i] += bomb_add
    bomb_end = bisect.bisect_right(X_array, x + 2 * D)
    bomb_count[bomb_end - 1] -= bomb_add
    now_bomb += bomb_count[i]


print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    que = deque()
    total = 0
    res = 0
    for i in range(n):
        x, h = XH[i]
        while que and que[0][0] < x:
            total -= que[0][1]
            que.popleft()
        h -= total

        if h > 0:
            num = (h + a - 1) // a
            res += num
            damage = num * a
            total += damage
            que.append([x + d * 2, damage])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

print(cnt)

Submission status: Accepted

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

def main():
    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()
    from collections import deque
    q = deque()

    ans = 0
    t = 0
    import copy
    for x, h in XH:
        while q:
            r, s = q.popleft()
            if r+d < x:
                t -= s
            else:
                q.appendleft((r, s))
                break
        h -= t
        if h > 0:
            if h%a == 0:
                b = h//a
                ans += b
                t += a*b
                q.append((x+d, a*b))
            else:
                b = h//a+1
                ans += b
                t += a*b
                q.append((x+d, a*b))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

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

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda t: t[0])
Xs = [X for X, _ in XH]
bit = BIT(N+1)
ans = 0

for i in range(N):
    X = XH[i][0]
    H = max(0, XH[i][1]-A*bit.acc(i+1))
    cnt = (H+A-1)//A
    ans += cnt
    j = bisect_right(Xs, X+2*D)
    bit.add(i, cnt)
    bit.add(j, -cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
memo = deque()
cnt = 0
for x, h in XH:
    while memo and memo[0][0] < x:
        _, i = memo.popleft()
        cnt -= i
    h -= cnt * A
    h = max(h, 0)
    bomb = (h + A - 1) // A
    ans += bomb
    cnt += bomb
    memo.append((x + 2 * D, bomb))

print(ans)

Submission status: Accepted

Solution code:
n,d,a=map(int,input().split())
d*=2
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[i for i,j in xh]+[10**20]
h=[j for i,j in xh]
notimos=[0]*(n+1)
c=0
ans=0
from bisect import bisect_right
for i in range(n):
  c+=notimos[i]
  xx,hh=xh[i]
  hh=max(0,hh-c*a)
  m=0--hh//a
  ans+=m
  c+=m
  notimos[bisect_right(x,xx+d)]-=m
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    if i != 0:
        damage[i] += damage[i-1]
    bi = bisect.bisect(x,2*d+x[i])
    count = max(math.ceil((h[i]-damage[i])/a),0)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count
    
print(point)

Submission status: Accepted

Solution code:
n,d,a=map(int,input().split())

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

cnt=0

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

bomb=0
he=[]
heapq.heapify(he)
dic={}

for i in range(n):
    #print(xh[i],bomb,he)
    (x,h)=xh[i]

    if bomb==0:
        secchi=x+d
        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        dic[secchi]=damage
        bomb+=damage
        heapq.heappush(he, secchi)
    else:
        while a:
            tmp=heapq.heappop(he)  
            if tmp+d<x:
                bomb-=dic[tmp]
            else:
                heapq.heappush(he, tmp)
                break
            if bomb==0:
                break

        if bomb<h:
            h-=bomb
            secchi=x+d
            count=((-1*h)//a)*(-1)
            damage=count*a
            cnt+=count
            dic[secchi]=damage
            bomb+=damage
            heapq.heappush(he, secchi)



print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline
 
 
class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
 
        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    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
 
    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)
 
        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
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
 
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    l = [list(map(int, input().split())) for _ in range(N)]

    l.sort()
    lh = [h for x,h in l]
    lx = [x for x,h in l]
    tree = LazySegTree(N)
    tree.set_list(lh, N)
    ans = 0

    for i in range(N):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            pos = bisect_right(lx, lx[i]+2*D)
            tree.update(i, pos, -c*A)
            ans += c

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,d,a=map(int,input().split())
d=d*2
M=sorted([list(map(int,input().split())) for i in range(n)])
l=0
A=[0]*n
B=[0]
ans=0
for i in range(n):
  while M[l][0]+d<M[i][0]:
    l=l+1
  ans=ans+max(0,(M[i][1]-B[i]+B[l]+a-1)//a)
  A[i]=max(0,(M[i][1]-B[i]+B[l]+a-1)//a)*a
  B.append(B[-1]+A[i])
print(ans)