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 sys
input=sys.stdin.readline
from bisect import bisect_right

def main():
    n,d,a=map(int,input().split())
    XH=[list(map(int,input().split())) for _ in range(n)]
    XH.sort()
    X=[i[0] for i in XH]
    Damage=[0]*(n+1)
    ans=0
    for i,(x,h) in enumerate(XH):
        Damage[i]+=Damage[i-1]
        h-=Damage[i]
        if h<=0:
            continue
        cnt=(h+a-1)//a
        ans+=cnt
        Damage[i]+=a*cnt
        br=bisect_right(X,x+2*d)
        Damage[br]-=a*cnt
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, D, A = map(int, input().split())
ls = []
for i in range(N):
  x,h = map(int, input().split())
  h = h//A if h%A==0 else h//A+1
  ls += [(x,h)]
ls.sort(key=lambda x:x[0])
deq = deque([])
ans = 0
acc = 0
for i in range(N):
  x, h = ls[i]
  while deq and deq[0][0]<x:
    y, d = deq.popleft()
    acc -= d
  n = max(0,h-acc)
  ans += n
  acc += n
  if n:
    deq += [(x+2*D,n)]
print(ans)

Submission status: Accepted

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


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

XH = []
for _ in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()

answer = 0
damage = 0
QUEUE = deque()
for x, h in XH:
    if QUEUE:
        while x > QUEUE[0][0]:
            damage -= QUEUE[0][1]
            QUEUE.popleft()
            if not QUEUE:
                break
    h -= damage
    if h <= 0:
        continue
    bomb = math.ceil(h / a)
    QUEUE.append((x + 2 * d, a * bomb))
    damage += a * bomb
    answer += bomb

print(answer)

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
XH = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans, r, S, R = 0, 0, [0] * (N + 2), []
for l in range(N):
    while r + 1 < N and XH[r + 1][0] - XH[l][0] <= 2 * D:
        r += 1
    S[l + 1] += S[l]
    bomb = (max(XH[l][1] - S[l + 1], 0) + A - 1) // A
    ans += bomb
    S[l + 1] += bomb * A
    S[r + 1 + 1] -= bomb * A
    R.append(r)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque

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

ans = 0
acc = 0
deq = deque([])

for x, h in Monsters:
  while deq and x>deq[0][0]:
    lim, dam = deq.popleft()
    acc -= dam
  c = max(0, h-acc)
  ans += c
  acc += c
  if c:
    deq += [(x+2*D, c)]
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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()

q = deque([])
qs = 0
ans = 0

for i in range(N):

    X = XH[i][0]
    H = XH[i][1]

 
    while len(q) > 0 and q[0][0] < X-D:
        po = q.popleft()
        qs -= po[1] * A

    if H - qs <= 0:
        continue
        
    else:
        pl = updiv(H-qs,A)
        qs += pl * A
        ans += pl
        q.append([X+D,pl])

print (ans)

Submission status: Accepted

Solution code:
from collections import deque


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

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = deque()
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            if 0 < H:
                attack_count = H // -A * -1
                damege = A * attack_count
                ans += attack_count
                XHN[i][1] -= damege

                acc_damege += damege
                q.append((bomb_p, damege))

    print(ans)


main()

Submission status: Accepted

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

from heapq import heapify, heappop, heappush

N, D, A = map(int, input().split())
XH = []
XH_append = XH.append
for _ in range(N):
    x, h = map(int, input().split())
    XH_append((x, 0, h))

heapify(XH)
atk_cnt = 0
ans = 0
while XH:
    x, t, h = heappop(XH)
    if t == 0: #新しいのが出てきたタイミング
        if atk_cnt * A >= h:
            continue
        
        remain = h - atk_cnt * A #攻撃が足りない場合、追加する
        new_atk = (remain + A - 1) // A
        heappush(XH, (x + 2 * D, 1, new_atk))

        ans += new_atk
        atk_cnt += new_atk
    
    else:
        atk_cnt -= h

print (ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,d,a = mi()
lis = []
for  i in range(n):
    x,h = mi()
    h = (h + a - 1) // a
    lis.append([x,h])

lis.sort()
dis = []
hp = []
for i in range(n):
    dis.append(lis[i][0])
    hp.append(lis[i][1])
#imos?
from collections import deque
hiku = deque()
sums = hp[0]
ans = hp[0]
hiku.append([dis[0] + 2 * d,hp[0]])
imadis,imahp = hiku.popleft()
for i in range(1,n):
    while True:
        if dis[i] <= imadis:
            break
        else:
            sums -= imahp
            imahp = 0
            if hiku:
                imadis,imahp = hiku.popleft()
            else:
                break
    diff = hp[i] - sums
    if diff > 0:
        ans += diff
        sums += diff
        hiku.append([dis[i] + 2 * d,diff])

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)

Submission status: Accepted

Solution code:
from math import ceil
from bisect import bisect_right

n, d, a = map(int, input().split())
l = []
l2 = []
l3 = []
l4 = [0 for i in range(n+1)]
l5 = [0 for i in range(n+1)]
ans = 0
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])
  l2.append(x + 2 * d)
  l3.append(x)
l.sort(key=lambda x: x[0])
l2.sort()
l3.sort()
for i in range(n):
  cnt = ceil((l[i][1] - l4[i] * a) / a)
  if cnt > 0:
    ans += cnt
    ind = bisect_right(l3, l2[i])
    l5[ind] += cnt
    l4[i] += cnt
  l4[i+1] = l4[i] - l5[i+1]
    
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from bisect import bisect_right
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)

Submission status: Accepted

Solution code:
import heapq

n, d, a = map(int, input().split())
bom = []

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

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

ans = 0
tot = 0
q = []
for x, h in bom:
    while q:
        if q[0][0] >= x: break
        else:
            _, t = heapq.heappop(q)
            tot -= t
    
    r = max((h-tot-1)//a + 1, 0)
    ans += r
    tot += r * a
    heapq.heappush(q, (x+2*d, r*a))

print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
damage=[0]*(N+1)

for i in range(len(x)):
    damage[i] += damage[i-1]
    h[i] -= damage[i]
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    damage[i]+=h_int*A
    r=bisect(x,x[i]+2*D)
    #print(damage[i])
    damage[r]-= A*h_int
    

print(int(cnt))

Submission status: Accepted

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

D = True

pos = []
pos1 = []

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

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

bombs = 0
damage = 0
y, z = 0, 0


while y < n:
	x0 = pos[y][0]
	try:
		x1 = pos1[z][0]
	except IndexError:
		x1 = 1e16
	if x0 <= x1:
		health = pos[y][1]
		health -= damage
		number = max(0, (health-1) // a + 1)
		bombs += number
		damage += number*a
		pos1.append((x0+2*d, number*a))
		y+=1
	else:
		damage -= pos1[z][1]
		z += 1
	

print(bombs)

Submission status: Accepted

Solution code:
from operator import itemgetter
import bisect
N, D, A = map(int, input().split())
enemies = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
d_enemy = [enemy[0] for enemy in enemies]
b_left = bisect.bisect_left
logs = []
logs_S = [0, ]
ans = 0
for i, enemy in enumerate(enemies):
    X, hp = enemy

    start_i = b_left(logs, X-2*D)
    count = logs_S[-1] - logs_S[start_i]

    hp -= count * A
    if hp > 0:
        attack_num = (hp + A-1) // A
        logs.append(X)
        logs_S.append(logs_S[-1]+attack_num)
        ans += attack_num
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
from operator import itemgetter

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
XH = sorted(zip(*[iter(XH)] * 2), key=itemgetter(0))
D *= 2
X = [i for i, _ in XH]

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

for i, (x, h) in enumerate(XH, 1):
    damages[i] += damages[i - 1]
    if damages[i] >= h:
        continue

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

print(answer)

Submission status: Accepted

Solution code:
n,d,a = map(int,input().split())
attack = [0 for _ in range(n)]
event = []
for i in range(n):
  x,h = map(int,input().split())
  h = (h-1)//a+1
  event.append([x-d,0,h,i])
  event.append([x+d,1,h,i])
event.sort()
#print(event)
ans = 0
now = 0
for j in range(2*n):
  x,m,h,i = event[j]
  if m == 0:
    if h > now:
      attack[i] += h-now
      ans += h-now
      now = h
  else:
    now -= attack[i]
print(ans)

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


import heapq
def main():
    N, D, A = read_values()
    M = [read_list() for _ in range(N)]
    M.sort(key=lambda l: l[0])
    Q = []

    F = 0
    res = 0
    for x, h in M:
        while Q:
            if Q[0][0] >= x:
                break
            else:
                _, f = heapq.heappop(Q)
                F -= f
        R = max((h - F - 1) // A + 1, 0)
        res += R
        F += R * A
        heapq.heappush(Q, (x + 2 * D, R * A))

    print(res)
       

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N, D, A = map(int, input().split())
    enemies = [None] * N
    for i in range(N):
        enemies[i] = tuple(map(int, input().split()))
    enemies.sort()
    q = deque()
    cur = 0
    ans = 0
    for x, h in enemies:
        while len(q) and q[0][0] < x:
            cur -= q.popleft()[1]
        remain = max(h - cur * A, 0)
        tmp = -(-remain//A)
        q.append((x + 2 * D, tmp))
        ans += tmp
        cur += tmp
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = [tuple(map(int, input().split())) for _ in range(n)]
xh.sort()
x, h = zip(*xh)
h = list(map(lambda x: -(-x//a), h))

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

for i in range(n):
    add = max(0, h[i] - s[i])
    j = bisect_right(x, x[i]+d*2)
    if j < n: s[j] -= add
    s[i] += add
    ans += add
    s[i+1] += s[i]

print(ans)

Submission status: Accepted

Solution code:
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]
#print(r,hp)

d=2*d
i,ans,damages=0,0,[0]*n
while i<n:
  if i>0:
    damages[i]+=damages[i-1]
    s=hp[i]+damages[i]
  else:
    s=hp[i]
  if s>0:
    cnt=(s+a-1)//a
    ans+=cnt
    #print(ans)
    damage=cnt*a
    damages[i]-=damage
    zone=bisect(r,r[i]+d)
    if zone<n:
      damages[zone]+=damage 
  i+=1
  #print(damages)
  #print(hp)
print(ans)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
l = [[0, 0] for _ in range(n)]
for i in range(n):
  x, h = map(int, input().split())
  l[i][0] = x
  l[i][1] = h
  
l.sort()
from collections import deque
d = 2*d
q = deque([])
total = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from collections import deque


def solve():
    N, D, A = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    XH = sorted(list(zip(m, m)), key=itemgetter(0))
    H = deque()
    X = deque()
    h_popleft = H.popleft
    x_popleft = X.popleft
    h_append = H.append
    x_append = X.append
    count = 0
    num = 0
    for x, h in XH:
        while X and X[0] < x:
            x_popleft()
            num -= (h_popleft() + (A - 1)) // A
        h -= A * num
        if h > 0:
            count += (h + (A - 1)) // A
            x_append(x + D*2)
            h_append(h)
            num += (h + (A - 1)) // A
    return count


if __name__ == '__main__':
    answer = solve()
    print(answer)

Submission status: Accepted

Solution code:
import sys
import bisect
from math import ceil
from itertools import accumulate
n, d, a = [int(i) for i in sys.stdin.readline().split()]
monsters = []
max_x = 0
for i in range(n):
    x, h = [int(i) for i in sys.stdin.readline().split()]
    max_x = max(x, max_x)
    monsters.append([x, h])
monsters.sort(key=lambda x:x[0])
x, h = zip(*monsters)
x_ls = []
for i, (_x, _h) in enumerate(zip(x, h)):
    ind = bisect.bisect_right(x, _x + 2 * d)
    x_ls.append([i, ind, _h])

h = list(h) + [0]
ls = [0 for i in range(n+1)]
cur = 0
res = 0
for i, ind, _h in x_ls:
    if h[i] > 0:
        cur -= ls[i]
    h[i] -= cur
    if h[i] > 0:
        hoge = ceil(h[i] / a)
        res += hoge
        cur += hoge * a
        ls[ind] += hoge * a
print(res)

Submission status: Accepted

Solution code:
from collections import deque
N,D,A = map(int, input().split())
ps = []
def ceil(a,b):
    return -(-a//b)

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

ps.sort()
damage = 0
cnt = 0
q = deque([])
for x,h in ps:
    while len(q) > 0 and q[0][0] < x:
        # 範囲外のものはダメージを与えられない
        _, d = q.popleft()
        damage -= d
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    num = ceil(h_rest, A)
    damage += num * A
    cnt += num
    r = x + 2*D
    q.append((r,num*A))
print(int(cnt))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,d,a = LI()
    xh = sorted([LI() for _ in range(n)])
    r = 0
    k = 0
    t = []
    ti = 0
    for x,h in xh:
        while len(t) > ti and t[ti][0] < x:
            k -= t[ti][1]
            ti += 1
        h -= k
        if h <= 0:
            continue
        u = (h+a-1) // a
        r += u
        k += u * a
        t.append((x+d*2, u*a))

    return r


print(main())

Submission status: Accepted

Solution code:
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def F_symulacja():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()
    wynik = 0
    while len(monstery) > 0:
        x, h = monstery[0]
        if h <= 0:
            monstery.pop(0)
            continue
        bomba_x = x + D
        wynik += 1
        for i in range(len(monstery)):
            x_i, h_i = monstery[i]
            if bomba_x - D <= x_i <= bomba_x + D:
                monstery[i] = (x_i, h_i - A)

    print(wynik)

def zabij(H, A):
    if H % A == 0:
        return H // A
    else:
        return H // A + 1

def F():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()

    wynik = 0
    gdzie_sie_koncza_bomby = []
    skonczone = 0
    ile_tu_spadlo = 0
    for x, h in monstery:
        while len(gdzie_sie_koncza_bomby) > skonczone:
            bomby_do, ile_bomb = gdzie_sie_koncza_bomby[skonczone]
            if bomby_do < x:
                ile_tu_spadlo -= ile_bomb
                skonczone += 1
            else:
                break
        if h - ile_tu_spadlo * A > 0:
            zrzucam_tutaj = zabij(h - ile_tu_spadlo * A, A)
            wynik += zrzucam_tutaj
            ile_tu_spadlo += zrzucam_tutaj
            gdzie_sie_koncza_bomby.append((x + 2 * D, zrzucam_tutaj))
    print(wynik)

F()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

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

#BIT 関数は全て1-indexed
def add(a,w):
    while a<=N:
        bit[a]+=w
        a+=a&-a

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret

#区間[l,r]に一律wを加える
def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)

#a番目のモンスターの体力を取得
def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  #区間に対する更新を行うため、値の差分をBITに持つ
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    #モンスターの体力がゼロ以下だったら何もしない
        pass
    else:
        x=X[i]
        pos=bisect_right(X,x+2*D)-1 #攻撃範囲の一番右側を二分探索で決定
        if h%A==0:   #hがAで割り切れる場合
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   #hをAで割って余りが出る場合は攻撃回数を+１する
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

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

#BIT 関数は全て1-indexed
def add(a,w):
    while a<=N:
        bit[a]+=w
        a+=a&-a

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret

#区間[l,r]に一律wを加える
def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)

#a番目のモンスターの体力を取得
def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  #区間に対する更新ができるBITを作成するために、値の差分をBITに持つ
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    #モンスターの体力がゼロ以下だったら何もしない
        pass
    else:
        x=X[i]
        pos=bisect_right(X,x+2*D)-1 #攻撃範囲の一番右側を二分探索で決定
        if h%A==0:   #hがAで割り切れる場合
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   #hをAで割って余りが出る場合は攻撃回数を+１する
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans

Submission status: Accepted

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

import math

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

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q*A))
        s += q*A
        t += q

print(t)

Submission status: Accepted

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

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #（攻撃が無効となる座標、攻撃によるポイント）
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break  #無効となる攻撃がない場合はwhileを終了
        end_x,end_point=q.popleft()
        attack_point-=end_point #攻撃が無効となる座標<=現在の座標があれば、その攻撃のポイントを引く

    if h<=attack_point: #モンスターの体力よりも攻撃で減らせるポイントの方が大きければ新規攻撃は不要
        pass
    else:   #新規攻撃が必要な場合
        if h%A==0:
            cnt=(h-attack_point)/A  #モンスターの大量をゼロ以下にするために何回攻撃が必要か
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))   #（攻撃が無効となる座標、攻撃によるポイント）をキューに入れる
        ans+=cnt

print ans

Submission status: Accepted

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

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #攻撃が無効となる座標、攻撃から差し引くポイント
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break
        end_x,end_point=q.popleft()
        attack_point-=end_point

    if h<=attack_point:
        pass
    else:
        if h%A==0:
            cnt=(h-attack_point)/A
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))
        ans+=cnt

print ans

Submission status: Accepted

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

data = []
for _ in range(N):
	data.append(tuple(map(int, input().split())))

data.sort()

queue = []
i = 0
j = 0
total = 0
height = 0
while i < N:
	if j >= len(queue) or data[i][0] <= queue[j][0]:
		x, h = data[i]
		i += 1
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			queue.append((x + D * 2, count * A))
	else:
		height -= queue[j][1]
		j += 1

print(total)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, D, A = LI()
    X_H = []
    for _ in range(N):
        x, h = LI()
        X_H.append((x, h))
    X_H = sorted(X_H, key=lambda x:x[0])
    X = [elem[0] for elem in X_H]
    kaihuku = [0 for _ in range(N)]
    cur_damage = 0
    n_attack = 0
    cnt = 0
    for i in range(N):
        x, tairyoku = X_H[i]
        cur_damage = cur_damage - kaihuku[i]
        tairyoku -= cur_damage
        tairyoku = max(tairyoku, 0)
        n_attack = tairyoku // A + (tairyoku % A > 0)

        cur_damage += n_attack * A
        ins_pos = bisect.bisect_right(X, x + 2*D)
        if ins_pos < N:
            kaihuku[ins_pos] += n_attack * A
        cnt += n_attack

    print(cnt)

main()

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
import heapq
def main():
    N,D,A=map(int,input().split())
    xh = [tuple(map(int,input().split())) for _ in range(N)]
    xh = sorted(xh, key = lambda x:x[0])
    x = [elem[0] for elem in xh]
    h = [elem[1] for elem in xh]
    res = 0
    buff = 0
    q = []
    heapq.heapify(q)
    for (X, H) in zip(x, h):
        while len(q)!=0:
            p = heapq.heappop(q)
            if p[0] < X:
                buff -= p[1]
            else:
                heapq.heappush(q,p)
                break
        nowhp = H - buff*A
        if nowhp <= 0:
            continue
        cnt = math.ceil(nowhp/A)
        res += cnt
        buff += cnt
        ins = (X+2*D, cnt)
        heapq.heappush(q,ins)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    d*=2
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d,-t))
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    g=itemgetter(0)
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=g):
        while q and g(g(q))<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d,-t))
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0]//M<x:b-=popleft()%M
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d)*M-t)
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        if h>b:
            t=(b-h)//a
            s-=t
            t*=a
            b-=t
            append((x+d+d,-t))
    print(s)
main()

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()
q = deque()
damage = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        damage -= q.popleft()[1]
    h -= damage
    if h <= 0:
        continue
    c = (h + A - 1) // A
    result += c
    damage += 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())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
q = deque()
t = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.popleft()
    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 math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
imos=[0]*(n+1)
x=[]
for i in range(n):
  x.append(xh[i][0])
ans,cnt=0,0
for i in range(n):
  cnt+=imos[i]
  hp=xh[i][1]-cnt*a
  if hp>0:
    cnt+=ceil(hp/a)
    ans+=ceil(hp/a)
    imos[bisect_right(x,x[i]+2*d)]-=ceil(hp/a)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    q=deque()
    popleft,append=q.popleft,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while q and q[0][0]<x:b-=popleft()[1]
        h-=b
        t=-(-h//a)
        if t>0:
            s+=t
            t*=a
            b+=t
            append((x+d+d,t))
    print(s)
main()