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:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys


mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []

for i in range(N):
    xh.append(LI())
xh.sort()
X = []
for i in range(N):
    X.append(xh[i][0])

bomb = [0 for i in range(N)]
ans = 0
now_dm = 0
for i in range(N):
    x,H = xh[i]
    now_dm += bomb[i]
    if now_dm >= H:
        pass
    else:
        ans += math.ceil((H - now_dm)/A)
        dm = math.ceil((H-now_dm)/A) * A
        ind = bisect.bisect_right(X, x+2*D)
        if i + 1 < N:
            bomb[i+1] += dm
        if ind < N:
            bomb[ind] -= dm

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

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

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

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

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

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
M = []
for i in range(N):
  x, h = map(int, input().split())
  M.append((x, -(-h//A)))
M.sort(key=lambda x: x[0])
X = list(map(lambda x: x[0], M))
H = list(map(lambda x: x[1], M))

dmg = [0] * (N+1)
ans = 0

for i in range(N):
  x, h = M[i]
  h = max(0, h - dmg[i])
  dmg[i] += h
  dmg[bisect_right(X, x + 2*D)] -= h
  dmg[i+1] += dmg[i]
  ans += h
print(ans)

Submission status: Accepted

Solution code:
import bisect
import math
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)

Submission status: Accepted

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

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])

d = []
i = 0

ans = 0
B = 0
for X, H in M:
    while i != len(d) and X > d[i][0]:
        B -= d[i][1]
        i += 1
    if H > B:
        t = math.ceil((H-B)/A)
        ans += t
        B += t*A
        d.append((X+2*D, t*A))


print(ans)

Submission status: Accepted

Solution code:
import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    #print(h)
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            h[i]-=m*a
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)

Submission status: Accepted

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

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    while len(pq) > 0 and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

print(ans)

Submission status: Accepted

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x << 30) + h)
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1] >> 30 <= Q[0][0]:
        xh = X.pop()
        x, h = xh >> 30, xh % (1<<30)
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = itemgetter(0))[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = lambda x: x[0])[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

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

hp = []
for x, h in xh:
    heappush(hp, [x, REAL, h])

bomb_acm = 0
ans = 0
while hp:
    x, r, h = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, UNREAL, hp_dis])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

print(ans)

Submission status: Accepted

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

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

import sys
input = sys.stdin.readline
from math import ceil
from collections import deque
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,H = map(list, zip(*XH))
q = deque()
d = 0
ans = 0

for x,h in XH:
    while q and q[0][0] < x:    #今見ている座標が既にそれまでの爆弾範囲から外れていたら
        d -= q.popleft()[1]
    h -= d
    if h > 0:
        num = ceil(h/A)
        ans += num
        q.append((x+2*D, num*A))    #(末端, そこまででの爆弾の威力)
        d += num*A
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Submission status: Accepted

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

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = itemgetter(0))[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from operator import itemgetter
key = itemgetter(0)

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque

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

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

    xh.sort()

    ans = 0
    q = deque()
    dmg = 0
    for i in range(N):
        # 過去に使った爆弾で、現在地点まで攻撃が届かないものは効果切れにする
        while q and q[0][0] < xh[i][0]:
            _, d = q.popleft()
            dmg -= d

        # それまでの攻撃でその地点の敵が死んでいるので、その敵に対しては新たに爆弾を使わない
        if xh[i][1] - dmg <= 0:
            continue

        remaining = xh[i][1] - dmg

        cnt = math.ceil(remaining / A)
        ans += cnt
        dmg += cnt * A
        # その敵に対して爆弾を使ったので、追加
        q.append((xh[i][0] + 2*D, cnt*A))


    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
Xmax = 10**10
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
XH.append([Xmax,0])
ans = 0
d = 0
i = j = 0
R = []
while True:
    if j >= len(R) or XH[i][0] <= R[j][0]:
        x, h = XH[i]
        i += 1
        if x >= Xmax:
            break
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            R.append((x+2*D, k*A))
            d += k*A
            ans += k
    else:
        x, h = R[j]
        j += 1
        d -= h
print(ans)

Submission status: Accepted

Solution code:
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

tg = sorted(tg, key=lambda x:x[0])
bit = BIT(n+2)
result = 0
ind = 0
for i in range(n):
    c = tg[i][1] - bit.sum(i+1)
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    if ind < i:
        ind = i
    for j in range(ind, n):
        if tg[j][0] <= wd:
            ind = j
        else:
            break
    bit.add(i+1, c)
    bit.add(ind+2, -c)
print(result)

Submission status: Accepted

Solution code:
from sys import stdout
from collections import deque
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
q = deque([])
ad = 0
for i in range(n):
    h = xh[i][1]
    x = xh[i][0]
    while len(q)>0 and q[0][0]<x:
        z = q.popleft()
        ad -= z[1]
    h -= ad
    if h<=0:
        continue
    cnt += h
    ad += h
    q.append((x+2*d,h))
print(cnt)

Submission status: Accepted

Solution code:
N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
if X[-1][0] - X[0][0] < 2 * D:
    ans = 0 
    max = 0
    for i in range(N):
        if X[i][1] > max:
            max = X[i][1]
    if max % A == 0:
        ans = max // A
    else:
        ans = max // A + 1
else:
    ans = 0
    for i in range(N):
        h = int(X[i][1])
        if h != 0:
            x = int(X[i][0])
            if h % A == 0:
                count = h // A
            else:
                count = h // A + 1
            ans += count
            dmg = A * count
    #print(ans,dmg)
            for j in range(i+1,N):
                x2 = int(X[j][0])
                h2 = int(X[j][1])
                if  x + (2 * D) < x2:
                    break
                else:
                    X[j][1] = max(0,h2-dmg)
                    #print(X[j])
print(ans)

Submission status: Accepted

Solution code:
import math
n,d,a=map(int,input().split())
XH=[[int(i)for i in input().split()] for _ in range(n)]
XH.sort(key=lambda x:x[0])
ans=0
l=0
before=0
T=[0]*n
for i,xh in enumerate(XH):
    x,h=xh
    while XH[l][0]+2*d<x:
        before-=T[l]
        l+=1
    h-=before*a
    if h<=0:
        continue
    T[i]=math.ceil(h/a)
    ans+=T[i]
    before+=T[i]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right


def solve(n, d, a, xh_list):
    res = 0
    xh_list_s = sorted(xh_list, key=lambda x: x[0])
    x_list_s = [xh[0] for xh in xh_list_s]
    h_list_s = [xh[1] for xh in xh_list_s]
    dmg = 0
    wait_list = [0] * (n + 1)
    for i in range(n):
        dmg -= wait_list[i]
        v = h_list_s[i] - dmg
        if v > 0:
            t = (v - 1) // a + 1
            res += t
            dmg += t * a
            j = bisect_right(x_list_s, x_list_s[i] + 2 * d)
            wait_list[j] += t * a

    return res


def main():
    n, d, a = map(int, input().split())
    xh_list = []
    for _ in range(n):
        x, h = map(int, input().split())
        xh_list.append((x, h))
    res = solve(n, d, a, xh_list)
    print(res)


def test():
    assert solve(3, 3, 2, [(1, 2), (5, 4), (9, 2)]) == 2
    assert solve(9, 4, 1, [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 2), (7, 3), (8, 4), (9, 5)]) == 5
    assert solve(3, 0, 1, [(300000000, 1000000000), (100000000, 1000000000), (200000000, 1000000000)]) == 3000000000


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

# mod = 998244353
# mod = 1000000007

n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    

deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    
    stop = 1
    while stop == 1 and len(deq) > 0:
        if deq[-1][0] < monster_x[i]:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0
    
    monster_h[i] -= totaldamage
    if monster_h[i] > 0:
        index = monster_x[i] + 2*d
        
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f * a
        deq.appendleft([index, f*a])
        monster_h[i] = 0

print(ans)

Submission status: Accepted

Solution code:
import sys
fastinput = sys.stdin.readline
N,D,A = [int(i) for i in fastinput().split()]
preXH = [[int(i) for i in fastinput().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
X = [x for x,h in XH]+[100000000000000000]
Diff = [X[m+1]-X[m] for m in range(N)]
reach = []
count = 0
l = X[0]
r = X[0]+2*D
for m in range(1,N+1):
    while r<X[m]:#l一個すすめる
        reach.append(m-1)
        r += Diff[count]
        count += 1

damage = 0
ans = 0
DIFF = [0]*N#ダメイジのdiff
for n,d in enumerate(DIFF):
    damage += d
    if damage<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-damage
        damage += bonu
        ans += bonu
        if reach[n]<N-1:DIFF[reach[n]+1] -= bonu
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
 
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size
 
	def Get(self, i):#iを返す
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s
 
	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return
 
	def SegAdd(self, l, r, x):#lからrにxを足す
		self.PointAdd(l, x)
		self.PointAdd(r+1, -x)
		return
 
 
n, d, a = map(int, input().split())
d *= 2
mo = sorted([list(map(int, input().split())) for _ in range(n)])
for i in range(n):
	mo[i][1] = (mo[i][1]-1)//a + 1
reach = []
moo = [x[0] for x in mo]
mooo = [x[1] for x in mo]
for x in moo:
	reach.append(bisect(moo, x+d)-1)
#print(reach)
 
bit = BIT(n)
 
ans = 0
for i, h in enumerate(mooo):
	gap = max(0, h - bit.Get(i+1))
	bit.SegAdd(i+1, reach[i]+1, gap)
	ans += gap
 
print(ans)

Submission status: Accepted

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

from bisect import bisect_right

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

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)


index = 0
pt = XH[index][0] + 2 * D
ht = (-(-XH[index][1] // A)) * A
minus = ht
answer = -(-XH[index][1] // A)
bi = bisect_right(X, pt)
check[bi] += ht

while 1:
  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  minus += ht
  answer += -(-XH[index][1] // A)
  bi = bisect_right(X, pt)
  check[bi] += ht
                 
print(answer)

Submission status: Accepted

Solution code:
N,D,A=map(int,input().split())
XH=[]
inf=float("inf")
for i in range(N):
    X,H=map(int,input().split())
    if H%A==0:
        H//=A
    else:
        H=H//A+1
    XH.append([X,H])
XH.sort()
XH=[[-inf,0]]+XH

L=0
lst=[0]*(N+1)
S=[0]*(N+1)
lst[1]=XH[1][1]
S[1]=lst[1]

for R in range(2,N+1):
    r=XH[R][0]
    l=r-2*D
    while XH[L][0]<l:
        L+=1
    lst[R]=max(0,XH[R][1]-(S[R-1]-S[L-1]))
    S[R]=lst[R]+S[R-1]
    
print(S[-1])

Submission status: Accepted

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

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

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)
index = 0
minus = 0
answer = 0

while 1:
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  bi = bisect_right(X, pt)
  minus += ht
  answer += -(-XH[index][1] // A)
  check[bi] += ht

  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
                 
print(answer)

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline
N, D, A = [int(i) for i in input().split()]
Mons = []
for _ in range(N):
    x, h = map(int, input().split())
    Mons.append([x, h, 0])


Mons.sort(key=lambda x: x[0])
ans = 0
idx = 0
d = 0

for i, M in enumerate(Mons):
    x = M[0]+D*2+1
    d -= M[2]
    ac = math.ceil(max(M[1]-d, 0)/A)
    ans += ac
    d += ac*A
    l = i
    r = N
    while l < r-1:
        m = (l+r)//2
        if m >= N:
            break
        elif Mons[m][0] < x:
            l = m
        else:
            r = m
    else:
        if r < N and Mons[r][0] >= x:
            Mons[r][2] += ac*A
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,d,a = get_nums_l()
lines = sys.stdin.readlines()
monsters = [ tuple(map(int, s.split(" "))) for s in lines ]
monsters.sort(key=lambda m: m[0])

ans = (monsters[0][1] + a - 1)//a
areas = [(monsters[0][0] + 2*d, ans*a)]
sum_ = ans*a
area_cursol = 0
for i in range(1, len(monsters)):
    m = monsters[i]
    x = m[0]
    h = m[1]


    while area_cursol < len(areas) and x > areas[area_cursol][0]:
        sum_ -= areas[area_cursol][1]
        area_cursol += 1

    if sum_ < h:
        # ボムつかう
        nokori = h-sum_
        kaisuu = (nokori+a-1)//a
        sum_ += kaisuu*a
        areas.append((x+2*d, kaisuu*a))
        ans += kaisuu

print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
cum = [0]*N
dam = 0
for i in range(N):
    dam += cum[i]
    H[i] -= dam
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_right(X,x+2*D)
    if i+1 < N:
        cum[i+1] += damage 
    if ind < N:
        cum[ind] -=damage 

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+a-1)//a
    XH.append([x,h])
ans = 0
XH.sort()
p = 0
j = 0
data = []
for i in range(n):
    while XH[i][0] > XH[j][0] + 2*d:
        p -= data[j]
        j += 1
    p_i = max(XH[i][1]-p,0)
    data.append(p_i)
    ans += p_i
    p += p_i

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import ceil
from collections import deque

input = sys.stdin.readline

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
q = deque()
ans = 0
dam = 0
for i in range(n):
    # attack
    while len(q) > 0:
        if q[0][0] < xh[i][0]:
            dam -= q[0][1]
            q.popleft()
        else:
            break
    xh[i][1] -= dam
    if xh[i][1] > 0:
        a_num = ceil(xh[i][1] / a)
        xh[i][1] -= a_num * a
        ans += a_num
        dam += a_num * a
        q.append((xh[i][0] + 2*d, a_num * a))
print(ans)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N, D, A = map(int, input().split())

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

ys = sorted(ys, key=lambda x : x[0])
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, h) in enumerate(ys):
    if y%2:
        d1[y-1-4*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)

Submission status: Accepted

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
L.sort()
X = []
for i in range(N):
    X.append(L[i][0])

import bisect
ans = 0
for i in range(N):
    L[i][1] -= bit.sum(N)-bit.sum(i)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    if j > i:
        bit.add(j, num*A)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

N, D, A = map(int, readline().split())
m = map(int,read().split())
XH = list(zip(m,m))
heapq.heapify(XH)
width = 2*D

ans = 0
while len(XH) != 0:
  xh_min = heapq.heappop(XH)
  # left + D の位置で攻撃する
  left = xh_min[0]
  right = left + width
  nAttack = (xh_min[1] + A - 1) // A
  damage = nAttack * A
    
  target = []
  while len(XH) != 0:
    xh = heapq.heappop(XH)
    if xh[0] <= right:
      if xh[1] > damage:
        target.append(xh)
    else:
      heapq.heappush(XH, xh)
      break
  if len(XH) == 0:
    maxH = xh_min[1]
    if len(target):
      maxH = max(xh_min[1], max([t[1] for t in target]))
    nAttack = (maxH + A - 1) // A
    ans += nAttack
  else:
    ans += nAttack
    for t in target:
      heapq.heappush(XH, (t[0], t[1] - damage))
  
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,D,A = map(int,input().split())
enemy = []
for i in range(N):
    C,B = map(int,input().split())
    enemy.append([C,B])
enemy.sort()
count = 0
chk_deque = deque()
total = 0
for i in range(N):
    if enemy[i][0] < D*2:
        demand =  (enemy[i][1]-1)//A + 1
        if demand > count :
            chk_deque.append([enemy[i][0],demand-count])
            total += demand - count
            count = demand
    else:
        for j in range(len(chk_deque)):
            a = chk_deque.popleft()
            if a[0] +2*D < enemy[i][0] :
                count -= a[1]
            else:
                chk_deque.appendleft(a)
                break
        demand =  (enemy[i][1]-1)//A + 1
        if demand > count :
            chk_deque.append([enemy[i][0],demand-count])
            total += demand - count
            count = demand
print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys, math, bisect
sys.setrecursionlimit(300000)
 
 
def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    p = []
    for i in range(N):
        p.append([X[i], H[i]])
    p.sort()
    ret = 0
    idx = []
    val = []
    cur = 0
    nex = 0
    cum = 0
    minus = 0
    l = 0
    for i in range(N):
        v = cum
        while l < i and idx[l] < i:
            minus = val[l]
            l += 1
        v -= minus
        p[i][1] = max(0, p[i][1] - v * A)
        tmp = math.ceil(p[i][1] / A)
        ret += tmp
        x = p[i][0] + D
        while nex < N and p[nex][0] <= x + D:
            #$print('hogehoge')
            #$print(nex, p[nex][0], x + D)
            nex += 1
        cum += tmp
        idx.append(nex - 1)
        val.append(cum)
        #print(i)
        #print(idx)
        #print(val)
        #print('tmp ', tmp)
        #print(ret)
        #print(cum)
        #print()
    print(ret)
    return
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)
 
if __name__ == '__main__':
    main()