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, heapq
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = [[int(_) for _ in input().split()] for _ in range(N)]
He = [[2 * x, h, 0] for x, h in XH]
heapq.heapify(He)
now = 0
ans = 0
while He:
    x, h, t = heapq.heappop(He)
    if t:
        now -= h
    else:
        if h - A * now > 0:
            diff = (h - A * now - 1) // A + 1
            now += diff
            ans += diff
            heapq.heappush(He, [x + 4 * D + 1, diff, 1])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from bisect import bisect_right
from operator import add
def resolve():
    n, d, a = map(int, input().split())
    X = [None] * n
    XH = [None] * n
    for i in range(n):
        x, h = map(int, input().split())
        X[i] = x
        XH[i] = x, (h - 1) // a + 1

    X.sort()
    XH.sort()

    tree = SegmentTree([0] * (n + 1), add, 0)
    res = 0
    for i in range(n):
        x, h = XH[i]
        damage = tree.sum(0, i + 1)
        if h < damage:
            continue
        res += h - damage
        tree.add(i, h - damage)
        tree.add(bisect_right(X, x + 2 * d), - h + damage)

    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        # self._descend(l)
        # self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    # calculate product of A[l:r]
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, d, a = map(int, input().split())
    XH = [None] * n
    coordinates = set() # for coordinates compression
    for i in range(n):
        x, h = map(int, input().split())
        XH[i] = [x, (h - 1) // a + 1] # 初めから何回減らすかだけ持てばよい
        coordinates.add(x)
        coordinates.add(x + 2 * d + 1) # [x, x + 2d + 1) に減らす
    XH.sort()
    compress = {v : i for i, v in enumerate(sorted(coordinates))}

    n = len(compress)
    A = [0] * n
    for i in range(len(XH)):
        A[compress[XH[i][0]]] = XH[i][1]

    res = 0
    tree = LazySegmentTree(A, max, 0, add, 0, add) # 区間 add, 1点取得ができればよいので、区間拡張しなくてよい max にしておく
    for x, h in XH:
        # もし x が生き残っていたら、[x, x + 2d + 1) から hp を引く
        hp = tree.sum(compress[x], compress[x] + 1)
        if hp <= 0:
            continue
        res += hp
        tree.range_act(compress[x], compress[x + 2 * d + 1], -hp)

    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    # calculate product of A[l:r]
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, d, a = map(int, input().split())
    XH = [None] * n
    coordinates = set() # for coordinates compression
    for i in range(n):
        x, h = map(int, input().split())
        XH[i] = [x, (h - 1) // a + 1] # 初めから何回減らすかだけ持てばよい
        coordinates.add(x)
        coordinates.add(x + 2 * d + 1) # [x, x + 2d + 1) に減らす
    XH.sort()
    compress = {v : i for i, v in enumerate(sorted(coordinates))}

    n = len(compress)
    A = [0] * n
    for i in range(len(XH)):
        A[compress[XH[i][0]]] = XH[i][1]

    res = 0
    tree = LazySegmentTree(A, max, 0, add, 0, add) # 区間 add, 1点取得ができればよいので、区間拡張しなくてよい max にしておく
    for x, h in XH:
        # もし x が生き残っていたら、x, x + 2d + 1 にHPの回数分だけ引く
        hp = tree.sum(compress[x], compress[x] + 1)
        if hp <= 0:
            continue
        res += hp
        tree.range_act(compress[x], compress[x + 2 * d + 1], -hp)

    print(res)
resolve()

Submission status: Accepted

Solution code:
import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
tree = make_tree(n)
l = len(tree)
for i in range(n):
    tree[i + l // 2] = s[i][1]
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if s[i][0] + 2 * d >= s[j][0]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    l=lambda: list(map(int,input().split()))
    n,d,a=l()
    xh=[]
    for i in range(n):
        xi,hi=l()
        xh.append([xi,hi])
    xh.sort()
    
    
    right_index=[]
    
    #尺取り法
    tmp=0
    for i in range(n):
        j=tmp
        while xh[j][0]<=xh[i][0]+2*d:
            j+=1
            if j==n: break
        j-=1
        right_index.append(j)
        tmp=j

    
    ans=0
    cnt=0
    damage=[0]*(n+1)
    for i in range(n):
    	xh[i][1]-=(ans-cnt)*a
    	damage_cnt=max(0,(xh[i][1]-1)//a + 1)
    	ans+=damage_cnt
    	damage[right_index[i]]+=damage_cnt
    	cnt+=damage[i]
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        self.sub = [0 for i in range(size + 1)]
        self.r = 0
        self.v = 0
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        self.sub[a] += value
        self.sub[b] -= value

    def get(self, key):
        """値の取得"""
        if key < self.r - 1:
            self.r = 0
            self.v = 0
        for i in range(self.r, key):
            self.v += self.sub[i]
        self.r = key
        return self.v + self.sub[key]


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        ans += c
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        m = -1
        i += 1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
import bisect
import operator
import collections


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        self.sub = [0 for i in range(size + 1)]
        self.r = 0
        self.v = 0
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        self.sub[a] += value
        self.sub[b] -= value

    def get(self, key):
        """値の取得"""
        if key < self.r - 1:
            self.r = 0
            self.v = 0
        for i in range(self.r, key):
            self.v += self.sub[i]
        self.r = key
        return self.v + self.sub[key]


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        ans += c
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        m = -1
        i += 1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
import math

I = lambda: list(map(int, input().split()))
n, d, a = I()
l = []
for _ in range(n):
	x, y = I()
	l.append([x,y])
l.sort()

j = 0
limit = []
for i in range(n):
	while l[j][0] - l[i][0] <= 2*d:
		j+=1
		if j == n: break
	j-=1
	limit.append(j)

ans = 0
num=[0]*(n+1)
cnt=0
for i in range(n):
	l[i][1]-=(ans-cnt)*a
	damage_cnt=max(0,(l[i][1]-1)//a + 1)
	ans+=damage_cnt
	num[limit[i]]+=damage_cnt
	cnt+=num[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math

N, D, A = map(int, input().split())
monster = [list(map(int, input().split())) for _ in range(N)]
monster.sort(key=lambda x:x[0])

bomb = deque()
s = 0
ans = 0
for i in range(N):
    x, h = monster[i]
    while len(bomb) > 0 and bomb[0][1] < x:
        s -= bomb.popleft()[2]
    h -= s
    if h > 0:
        cnt = math.ceil(h/A)
        damage = cnt*A
        bomb.append([x, x+2*D, damage])
        s += damage
        ans += cnt
print(ans)

Submission status: Accepted

Solution code:
from math import * 
from collections import *

N, D, A = list(map(int, input().split()))
ans = 0
t = 0
q = deque()

XH = sorted([list(map(int, input().split())) for i in range(N)])

for x, h in XH:
    if q:
        while q and q[0][0] < (x-D):
            _, c = q.popleft()
            t -= c
    
    h = h - t * A
    if h <= 0: continue
    
    x += D
    c = ceil(h/A)
    t += c
    ans += c
    q.append((x, c))
    
print(ans)

Submission status: Accepted

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    while len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
            break
    Monster[i][1] -= damage
    count = -(-max(Monster[i][1],0)//A)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)

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 = 0, 0, [0] * (N + 2)
for L in range(N):
    while R < N and XH[R][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] -= bomb * A
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, -(h // a + (1 if (h % a) else 0))))
    bomb = 0
    res = 0
    while q:
        x, h = heapq.heappop(q)
        if h < 0:
            h *= -1
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, -ceil(h / a)))
    bomb = 0
    res = 0
    while q:
        x, h = heapq.heappop(q)
        if h < 0:
            h *= -1
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from math import ceil
import heapq

def main():
    n, d, a = map(int, input().split())
    q = []
    for i in range(n):
        x, h = map(int, input().split())
        heapq.heappush(q, (x, 0, ceil(h / a)))
    bomb = 0
    res = 0
    while q:
        x, ty, h = heapq.heappop(q)
        if ty == 0:
            if h > bomb:
                heapq.heappush(q, (x + 2 * d, 1, h - bomb))
                res += h - bomb
                bomb = h
        else:
            bomb -= h
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
xh=[]
n,d,a=map(int,input().split())
for _ in range(n):
	x,h=map(int,input().split())
	xh.append([x,h])
xh.sort()
ans=0
cnt=[0]*n
j=0
limit=[]
for i in range(n):
	while xh[j][0]-xh[i][0]<=2*d:
		j+=1
		if j==n:
			break
	j-=1
	limit.append(j)
num=[0]*(n+1)
cnt=0
for i in range(n):
	xh[i][1]-=(ans-cnt)*a
	damage_cnt=max(0,(xh[i][1]-1)//a+1)
	ans+=damage_cnt
	num[limit[i]]+=damage_cnt
	cnt+=num[i]
print(ans)

Submission status: Accepted

Solution code:
import math
n, d, a = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n):
    x, h = map(int,input().split())
    e[i] = [x,h]
num = 0

e.sort()
sd = [0 for i in range(n)]
l = [i for i in range(n)]
for i in range(n):
    for j in range(l[i-1],i):
        if e[i][0]-e[j][0] <= 2*d:
            l[i] = j
            break

for i in range(n):
    res = e[i][1] - sd[i-1] + sd[l[i]-1]
    if res < 0:
        sd[i] = sd[i-1]
    else:
        k = math.ceil(res/a)
        sd[i] = sd[i-1]+k*a
        num += k

print(num)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,d,a = map(int, input().split())
    xh = [list(map(int, input().split())) for _ in range(n)]
    xh.sort(key=lambda a: a[0])
    x = []
    for i in range(n):
        x.append(xh[i][0])
    res = 0
    hp = [0]*n
    for i in range(n):
        if i != 0:
            hp[i] += hp[i-1]
        if hp[i]>=xh[i][1]:
            continue
        res += (xh[i][1]-hp[i]-1) // a + 1
        attack = ((xh[i][1]-hp[i]-1) // a + 1) * a
        hp[i] += attack
        genkai = x[i] + 2 * d
        migi = bisect_right(x, genkai)
        if migi <= n - 1:
            hp[migi] -= attack

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
n,d,a = map(int, input().split())

monster = [list(map(int,input().split())) for i in range(n)]

monster.sort()

damage = 0

finish = deque()

ans = 0

for i in range(n):
    x,h = monster[i]
    while finish:
        if finish[0][0]<x:
            damage -= finish.popleft()[1]
        else:
            break
    if h<=damage:
        continue
    else:
        b = ceil((h-damage)/a)
        ans += b
        damage += b*a
        finish.append([x+2*d,b*a])

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    n, dis, dam = map(int, input().split())
    mon = [list(map(int, input().split())) for _ in range(n)]
    mon.sort(key=lambda x: x[0])
    p = [v[0] for v in mon]
    imos = [0]*(n+1)
    dis = 2*dis + 1
    ans = 0
    for i in range(n):
        if 0 < i:
            imos[i] += imos[i-1]
        if imos[i] < mon[i][1]:
            tmp = (mon[i][1] - imos[i] + dam - 1) // dam
            ans += tmp
            tmp *= dam
            imos[i] += tmp
            idx = bisect_left(p, p[i]+dis)
            imos[idx] -= tmp
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,d,a=f()
lt=sorted(tuple(f()) for _ in range(n))
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x: s+=q.popleft()[1]
  h-=s
  if h>0: t=-h//a; c-=t; s-=t*a; q.append((x+d*2,t*a))
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,d,a=f()
lt=sorted(tuple(f()) for _ in range(n))
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x: s+=q.popleft()[1]
  h-=s
  if h<1: continue 
  t=-h//a; c-=t; s-=t*a; q.append((x+d*2,t*a))
print(c)

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,d,a=f()
lt=sorted(tuple(f()) for _ in range(n))
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x: s+=q.popleft()[1]
  h-=s
  if h<1: continue 
  t=-h//a; c-=t; s-=t*a; q.append((x+d*2,t*a))
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,d,a=f()
lt=sorted([tuple(f()) for _ in range(n)])
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x: s+=q.popleft()[1]
  h-=s
  if h<1: continue 
  t=-h//a; c-=t; s-=t*a; q.append((x+d*2,t*a))
print(c)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,d,a=f()
lt=sorted([tuple(f()) for _ in range(n)])
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x:
    s+=q.popleft()[1]
  h-=s
  if h<1: continue 
  t=-h//a
  c-=t
  s-=t*a
  q.append((x+d*2,t*a))
print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class RangeBIT:
        def __init__(self,n):
            self.p=self.BIT(n+1)
            self.q=self.BIT(n+1)
        
        def add(self,s,t,x):
            self.p.add(s,-x*s)
            self.p.add(t,x*t)
            self.q.add(s,x)
            self.q.add(t,-x)
        
        def sum(self,s,t):
            return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
        
        class BIT:
            def __init__(self,n):
                self.num=n
                self.dat=[0]*(self.num+1)
            
            def add(self,i,x):
                i+=1
                while i<=self.num:
                    self.dat[i]+=x
                    i+=i&-i
            
            def sum(self,i):
                i+=1
                s=0
                while i>0:
                    s+=self.dat[i]
                    i-=i&-i
                return s

    N,D,A=map(int,input().split())
    X=[0]*N
    XH=[]
    for i in range(N):
        X[i],H=map(int,input().split())
        XH.append((X[i]-1,H))
    XH.sort()
    X.sort()
    l=[0]*N
    for i in range(N):
        l[i]=bisect_right(X,X[i]+D*2)-i
    
    b=RangeBIT(N)
    index=0
    ans=0
    while index<N:
        h=XH[index][1]-b.sum(index,index+1)
        if h<=0:
            index+=1
            continue
        d=-(-h//A)
        ans+=d
        b.add(index,index+l[index],d*A)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

N, D, A = map(int, input().split(" "))
proc_que = []

for _ in range(N):
    x, h = map(int, input().split(" "))
    heapq.heappush(proc_que, (x, h))

damaged = 0
ans = 0

while len(proc_que) > 0:
    x, h = heapq.heappop(proc_que)
    if h > 0:
        # monster
        num_bomb_use = max(0, (h - damaged + A - 1) // A)
        ans += num_bomb_use
        damaged += num_bomb_use * A
        heapq.heappush(proc_que, (x + 2 * D + 1, -num_bomb_use * A))
    else:
        # damaged end
        damaged += h

print(ans)

Submission status: Accepted

Solution code:
n, d, a = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# 二分木
import bisect


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

xh.sort()
x = [ tmp[0] for tmp in xh]
damage = [0] * (n+1)

ans = 0
for i in range(n):
    damage[i+1] += damage[i]
    if( damage[i+1] >= xh[i][1] ):
        continue
    atk_num = (xh[i][1] - damage[i+1] - 1)//a +1
    ans += atk_num
    damage[i+1] += atk_num * a
    right = bisect.bisect_right(x, xh[i][0] + 2*d)
    if( right < n):
        damage[right+1] -= atk_num * a

print(ans)