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:
n,d,a = map(int,input().split())
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x:x[0])
x = [0]*n
h = [0]*n
for i in range(n): x[i],h[i] = lst[i]

length = [0]*n
for i in range(n):
    left = i+1
    right = n-1
    while left <= right:
        mid = (left+right)//2
        if x[mid] - x[i] <= 2*d:
            left = mid+1
        else:
            right = mid-1
    length[i] = left-1

d = [0]*n
dmg = 0
idx = 0
ans = 0
for i in range(n):
    while i > length[idx]:
        idx += 1
    h[i] = max(h[i]-dmg+d[idx-1],0)
    cnt = (h[i]+a-1)//a
    ans += cnt
    dmg += cnt*a
    d[i] = dmg

print(ans)

Submission status: Accepted

Solution code:
import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
ans = 0
a,s = 0,0
for i in range(N):
    x,h = L1[i]
    h -= a
    if h > 0:
        ans += h
        a += h
        L1[i][1] = h
    else:
        L1[i][1] = 0
    while s < N and L2[s] <= i:
        a -= L1[s][1]
        s += 1
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())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]
from math import ceil
from bisect import bisect_right
imos=[0]*(N+1)
hit=0
ans=0
for i in range(N):
  hit+=imos[i]
  restH=H[i]-hit*A
  if restH>0:
    ans+=ceil(restH/A)
    hit+=ceil(restH/A)
    ind=bisect_right(X,X[i]+2*D)
    imos[ind]-=ceil(restH/A)
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
n, d, a = map(int, input().split())
monster = []

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

monster.sort()
hp = []
x = []
damage = [0] * (n+1)

for i in range(n):
    hp.append(monster[i][1])
    x.append(monster[i][0])

ans = 0
for i in range(n):
    bomb = max((hp[i] - damage[i] - 1) // a + 1, 0)
    ans += bomb
    damage[i] += bomb * a
    damage[bisect_right(x, x[i]+2*d)] -= bomb * a
    damage[i+1] += damage[i]

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque


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


damage_sum = 0
ans = 0
q = deque([])
for i in range(N):
    x, h = monsters[i]
    while q and q[0][0] < x:
        damage_sum -= q[0][1]
        q.popleft()
    h -= damage_sum
    if h > 0:
        hit = ceil(h / A)
        ans += hit
        damage = hit * A
        damage_sum += damage
        q.append((x + 2 * D, damage))

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque

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

damege_sum = 0
ans = 0
q = deque([])
for i in range(N):
    x, h = monsters[i]
    while q and q[0][0] < x:
        damege_sum -= q[0][1]
        q.popleft()
    h -= damege_sum
    if h > 0:
        hit = ceil(h / A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)

Submission status: Accepted

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

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

import math

ans=0
S=0
P=0
RL=[0]
RC=[0]
cnt=0
for i in range(N):
    for j in range(P,len(RL)):
        if RL[P]<L[i][0]:
            cnt+=RC[P]
            P+=1
        else:
            break
    if L[i][1]-S+cnt>0:
        ans+=math.ceil((L[i][1]-S+cnt)/A)
        
        RL+=[L[i][0]+2*D]
        RC+=[math.ceil((L[i][1]-S+cnt)/A)*A]
        S+=math.ceil((L[i][1]-S+cnt)/A)*A
    #print(i,ans,P,RL,RC,S,cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    from collections import deque
    buf = sys.stdin.buffer
    
    n, d, a = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))
    
    bomb_area = deque([])
    bomb_power = deque([])
    total_damage = 0
    ans = 0
    for pos, hp in monsters:
        while bomb_area:
            area = bomb_area[0]
            if area < pos:
                bomb_area.popleft()
                power = bomb_power.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp - total_damage + a - 1) // a
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n, d, a = MI()
    hp = []
    for _ in range(n):
        x, h = MI()
        heappush(hp, (x, 1, h))
    p = 0
    ans = 0
    while hp:
        x, op, h = heappop(hp)
        if op:
            h -= p
            if h > 0:
                ad = (h + a - 1) // a
                ans += ad
                p += ad * a
                heappush(hp, (x + 2 * d + 1, 0, ad * a))
        else:
            p -= h

    print(ans)

main()

Submission status: Accepted

Solution code:
# try AfterContestCase
from collections import deque
from math import ceil
import sys
input = sys.stdin.readline

def main():
    N,D,A = map(int,input().split())
    XH = sorted([[int(i) for i in input().split()] for _ in range(N)],key=lambda x: x[0])

    ans = 0
    index = deque()
    damage = 0
    for i in range(N):
        # 爆弾が届かない場合
        while index:
            if index[0][0] + 2*D < XH[i][0]:
                _,c = index.popleft()
                damage -= A * c
            else:
                break
        
        # 爆弾投下
        XH[i][1] -= damage

        # 生き残り
        if XH[i][1] > 0:
            count = ceil(XH[i][1]/A)
            damage += count * A
            index.append([XH[i][0],count])
            ans += count

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import collections
n,d,a=map(int,input().split())
XH=[]
for i in range(n):
  XH.append([int(i) for i in input().split()])
XH.sort(key=lambda x:x[0])
D=collections.deque()
x,h=XH[0]
t=(h-1)//a+1
ans=t
D.append([x,h,t])
adj=t
for i in range(1,n):
  x,h=XH[i]
  while D:
    lx,lh,t=D.popleft()
    if lx<x-2*d:
      adj-=t
    else:
      D.appendleft([lx,lh,t])
      break
  h=max(0,h-adj*a)
  t=(h-1)//a+1
  ans+=t
  adj+=t
  D.append([x,h,t])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    from collections import deque

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

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = X[left]
        h = BIT_query(left+1)
        while right < N and X[right] <= x + 2*D:
            right += 1
        if h > 0:
            cur = (h + A - 1) // A
            damage = cur * A
            BIT_update(left+1, -damage)
            BIT_update(right+1, damage)
            ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

M.sort()
X = [M[i][0] for i in range(N)]
H = [M[i][1] for i in range(N)]
ans = 0
diff = 0
q = deque()
for i in range(N):
    Xi, Hi = M[i]
    while len(q) > 0 and q[0][0] < Xi:
        diff += q.popleft()[1]
    Hi += diff
    if Hi <= 0:
        continue
    c = (Hi + A - 1) // A
    ans += c
    diff -= A * c
    q.append((Xi + 2 * D, A * c))
print(ans)

Submission status: Accepted

Solution code:
from math import ceil


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


def problem_a(h):
    if h <= 0:
        return 0
    return ceil(h/A)


cnt_sum = 0
cnt = [0] * N
l = 0
for i in range(N):
    while monsters[l][0] + 2 * D < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
    already = cnt_sum * A
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

print(sum(cnt))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc153/submissions/9784108

import numpy as np
i8 = np.int64

def solve(X, H, D):
    xi = np.empty_like(X)
    hi = np.empty_like(H)
    p = 0
    N = X.shape[0]
    for i in range(1, N):
        if X[i] > X[i - 1]:
            xi[p] = X[i - 1]
            hi[p] = H[i - 1]
            p += 1
    xi[p] = X[N - 1]
    hi[p] = H[N - 1]
    p += 1
    area = 2 * D
    res = 0
    sum_right = 0
    sum_left = 0
    left = 0
    for i in range(p):
        while xi[i] - xi[left] > area:
            sum_left += hi[left]
            left += 1
        x = hi[i] - (sum_right - sum_left)
        if x > 0:
            res += x
            sum_right += x
            hi[i] = x
        else:
            hi[i] = 0
    return res


def main(X, H, D, A):
    arg = np.lexsort((H, X))
    X = X[arg]
    H = H[arg]
    H = (H - 1) // A + 1
    print(solve(X, H, D))


if __name__ == '__main__':
    stdin = np.fromstring(open(0).read(), np.int64, sep=' ')
    N, D, A = stdin[:3]
    XH = stdin[3:].reshape((-1, 2)).T
    ans = main(XH[0], XH[1], D, A)

Submission status: Accepted

Solution code:
from collections import deque
import math
import bisect
n, d, a = map(int, input().split())
data = []
x_point = []
for i in range(n):
    x,h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
data.sort()
x_point.sort()
imos = [0] * (n+2)
ans = 0
for i in range(1,n+1):
    x, h = data[i-1]
    imos[i] += imos[i-1]
    index = bisect.bisect_right(x_point, x + 2*d)
    h -= imos[i]
    count = max(math.ceil(h/a), 0)
    ans += count
    imos[i] += count*a
    if index + 1 <= n:
        imos[index+1] -=count*a
print(ans)

Submission status: Accepted

Solution code:
import sys
N, D, A = map(int, sys.stdin.readline().split())
XH = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

XH = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

def findi(v):
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid
    return ok

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    ans += XH[i][1]
    index = findi(XH[i][0] + D * 2)
    done += XH[i][1]
    adjust[index] += XH[i][1]

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        while right < N and P[right][0] <= x + 2*D:
            right += 1
        if h > 0:
            cur = (h + A - 1) // A
            damage = cur * A
            BIT_update(left+1, -damage)
            BIT_update(right+1, damage)
            ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    from bisect import bisect_right
    ans = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        if h > 0:
            cur = (h + A - 1) // A
            damage = cur * A
            BIT_update(left+1, -damage)
            right = bisect_right(X, x + 2*D)
            BIT_update(right+1, damage)
            ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
from math import ceil
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
x,h=[],[]
for i in range(n):
  x.append(l[i][0])
  h.append(l[i][1])
accum=[0]*(n+1)
bomb,ans=0,0
for i in range(n):
  bomb+=accum[i]
  hp=h[i]-bomb*a
  if hp>0:
    ans+=ceil(hp/a)
    bomb+=ceil(hp/a)
    inde=bisect_right(x,x[i]+2*d)
    accum[inde]-=ceil(hp/a)
print(ans)

Submission status: Accepted

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

xh.sort()

R = [0] * n
H = 0
for L in range(n):
    while H < n:
        if xh[H][0] > xh[L][0] + d * 2:
            H -= 1
            break
        H += 1
    if H == n:
        H -= 1
    R[L] = H + 1

cs = [0] * (n+1)
H = n - 1
ans = 0
for i in range(n-1, -1, -1):
    x = xh[i][1] // a
    if xh[i][1] % a > 0:
        x += 1
    y = cs[i+1] - cs[R[i]]
    if y >= x:
        cs[i] = cs[i+1]
    else:
#        ans += x - y
        cs[i] = cs[i+1] + x - y

print(cs[0])

Submission status: Accepted

Solution code:
from math import *

n, d, a = map(int, input().split())
damage_diff = [0] * n
damage = 0
p = sorted(tuple(map(int, input().split())) for _ in range(n))

j = 0
c = 0

for i in range(n):
  damage -= damage_diff[i]
  
  x, h = p[i]
  h -= damage
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j < n and p[j][0] - x <= 2 * d:
    j += 1

  if j < n:
    damage_diff[j] += m
  damage += m
print(c)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque

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

q = deque([])
s = 0

ans = 0
for i in range(N):
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
dmg = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        dmg += bomb * A
        ans += bomb
    else:
        while len(q) > 0:
            d, bomb = q.popleft()
            if d < x:
                dmg -= bomb * A
            else:
                q.appendleft((d, bomb))
                break
        if h > dmg:
            bomb = ((h - dmg) + A - 1) // A
            q.append((x + 2 * D, bomb))
            dmg += bomb * A
            ans += bomb

print(ans)

Submission status: Accepted

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

from collections import deque

p.sort()

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

print(ans)

Submission status: Accepted

Solution code:
import bisect

N,D,A = map(int,input().split())
mons = []; X = []; need = [0]*N; bomb_range = []

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

for i in range(N):
    X.append(mons[i][0])
    need[i] = mons[i][1] // A
    if mons[i][1] % A != 0: need[i] += 1

for i in range(N):
    bomb_range.append(bisect.bisect_right(X,X[i] + 2*D))

if N == 1:
    ans = need[0]
else:
    # imos setting
    imos = [0]*(N+1)
    imos[0] = need[0]
    imos[bomb_range[0]] = - need[0]
    #
    ans = need[0]
    for i in range(1,N):
        imos[i] += imos[i-1]
        bomb = need[i] - imos[i]
        if bomb > 0:
            ans += bomb
            imos[i] += bomb
            imos[bomb_range[i]] -= bomb
        else:
            continue

print(ans)

Submission status: Accepted

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

XH.sort()
q = []
t = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h < 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)

Submission status: Accepted

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

XH.sort()
q = []
t = 0
result = 0
for x, h in XH:
    while True:
        if len(q) == 0:
            break
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h < 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)

Submission status: Accepted

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

d *= 2
monster.sort()

count = 0
damage_total = 0
q = deque([])

for i in range(n):
    x = monster[i][0]
    h = monster[i][1]
    while len(q) > 0 and q[0][0] < x:
        damage_total -= q[0][1]
        q.popleft()

    h -= damage_total
    if h > 0:
        count_now = (h + a - 1) // a
        count += count_now
        damage_now = a * count_now
        damage_total += damage_now
        q.append([x + d, damage_now])

print(count)

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)

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

# range = xrange
# input = raw_input


def main():
    from bisect import bisect as br
    n, d, A= lin()
    a = [lin() for i in range(n)]
    a.sort()
    a+= [[10**9+1+2*d,0]]
    a1=[i for i, j in a ]
    a2 = [0]*(n+1)
    ch = 0
    ans = 0
    for i in range(n):
        ch -= a2[i]
        x = a[i][1]-A*ch
        if x>0:    
            pos = a[i][0]
            r = br(a1, pos+2*d)
            amt = (x+A-1)//A
            a2[r]+=amt
            ch += amt
            ans += amt
    print(ans)





            
        

        
main()
# threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

N,d,a=LI()

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
    

show_flg=False
show_flg=True

ans=0
n=N
m=[]
for i in range(n):
    x,h=LI()
    m.append((x,h))

m.sort(key=lambda x:x[0])
X=[x for x,h in m]

for j in range(n):
    i=j+1
    #show(data)
    dm=query(i,i+1)
    dm=data[N0-1+i]
    if m[j][1]>dm:
        c=(m[j][1]-dm+a-1)//a
        r=bisect.bisect(X,m[j][0]+2*d)
        update(i,r+1,c*a)
        ans+=c

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
import math
n,d,a=map(int,input().split())
X, H=[], []; ans=0; L=[]
for i in range(n):
  x,h=map(int,input().split())
  L.append((x,h))
L.sort()
for x,h in L:
  X.append(x); H.append(h)
X.append(10**9); H.append(10**9)
imos=[0]*(n+5)
de=0 # decrease count
for i in range(n):
  de+=imos[i]
  HP=H[i]-de*a
  # 右から貪欲にダメージを減らす
  # 敵の体力が残ってるとき
  # print("HP is",HP)
  if HP>0:
    atk_cnt=math.ceil(HP/a) # 何回殴る必要があるか
    de+=atk_cnt
    ans+=atk_cnt
    index=upper_bound(X,X[i]+2*d)
    # print(X,X[i]+2*d)
    # print(index, atk_cnt)
    imos[index]-=atk_cnt
print(ans)

Submission status: Accepted

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

import sys
from bisect import bisect_right
from operator import itemgetter

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

N, D, K = MAP()

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

XH.sort(key=itemgetter(0))
X, _ = zip(*XH)
D = D * 2

imos = [0] * (N+1)
ans = 0
for i, (x, h) in enumerate(XH):
    imos[i+1] += imos[i]
    h -= imos[i] * K
    if h <= 0:
        continue
    cnt = ceil(h, K)
    idx = bisect_right(X, x+D)
    imos[i+1] += cnt
    imos[idx] -= cnt
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    c = [[int(i) for i in input().split()] for j in range(N)]
    c.sort()

    from collections import deque
    q = deque([])
    ans = 0
    tot = 0
    for i in range(N):
        x = c[i][0]
        h = c[i][1]
        while 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+2*D, damage))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
import math
n,d,a=map(int,input().split())
X, H=[], []; ans=0; L=[]
for i in range(n):
  x,h=map(int,input().split())
  L.append((x,h))
L.sort()
for x,h in L:
  X.append(x); H.append(h)
X.append(10**9); H.append(10**9)
imos=[0]*(n+5)
de=0 # decrease count
for i in range(n):
  de+=imos[i]
  HP=H[i]-de*a
  # 右から貪欲にダメージを減らす
  # 敵の体力が残ってるとき
  # print("HP is",HP)
  if HP>0:
    atk_cnt=math.ceil(HP/a) # 何回殴る必要があるか
    de+=atk_cnt
    ans+=atk_cnt
    index=upper_bound(X,X[i]+2*d)
    # print(X,X[i]+2*d)
    # print(index, atk_cnt)
    imos[index]-=atk_cnt
print(ans)