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:
from random import random
class Node:
        def __init__(self, key, value:int=-1):
            self.left = None
            self.right = None
            self.key = key
            self.value = value
            self.priority = int(random()*10**7)
            # self.count_partial = 1
            self.sum_partial = value

 

class Treap:
    
    #Node [left, right, key, value, priority, num_partial, sum_partial]
    def __init__(self):
        self.root = None

    def update(self, node) -> Node:
        if node.left is None:
            # left_count = 0
            left_sum = 0
        else:
            # left_count = node.left.count_partial
            left_sum = node.left.sum_partial
        if node.right is None:
            # right_count = 0
            right_sum = 0
        else:
            # right_count = node.right.count_partial
            right_sum = node.right.sum_partial

        # node.count_partial = left_count + right_count + 1
        node.sum_partial = left_sum  + node.value + right_sum
        return node

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            return self.update(left)
        else:
            right.left = self.merge(left,right.left)
            return self.update(right)


    # def node_size(self, node:Node) -> int:
    #     return 0 if node is None else node.count_partial
    
    def node_key(self, node: Node) -> int:
        return -1 if node is None or node.key is None else node.key
    
    def node_sum(self, node: Node) -> int:
        return 0 if node is None else node.sum_partial

    #指定された場所のノードは右の木に含まれる
    def split(self, node:None, key:int) -> (Node, Node):
        if node is None:
            return None,None
        if key <= self.node_key(node):
            left,right = self.split(node.left, key)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, key)
            node.right = left
            return self.update(node),right

    
    def insert(self, key:int, value:int =-1):
        value = value if value > 0 else key
        left, right = self.split(self.root, key)
        new_node = Node(key,value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, key:int):
        # print('erase pos=',pos,'num=',self.search(pos),'num_nodes=',self.root.count_partial)
        middle,right = self.split(self.root, key+1)
        # print(middle.value if middle is not None else -1,middle.count_partial if middle is not None else -1,right.value if right is not None else -1,right.count_partial if right is not None else -1)
        left,middle = self.split(middle, key)
        # print(left.value if left is not None else -1,left.count_partial if left is not None else -1, middle.value if middle is not None else -1,middle.count_partial if middle is not None else -1,)
        self.root = self.merge(left,right)


    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'k=',node.key,'v=',node.value, 'p=',node.priority)
        if node.left is not None:
            print('left')
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            print('right')
            self.printTree(node.right,level+1)
        
    

    def find(self, key):
        #return self.search_recursively(pos,self.root)
        v = self.root
        while v:
            v_key = self.node_key(v)
            if key == v_key:
                return v.value
            elif key < v_key:
                v = v.left
            else:
                v = v.right
        return -1
    def interval_sum(self, left_key, right_key):
        lt_left, ge_left = self.split(self.root,left_key)
        left_to_right, gt_right = self.split(ge_left, right_key + 1)
        res = self.node_sum(left_to_right)
        self.root = self.merge(lt_left, self.merge(left_to_right, gt_right))
        return res



def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,D,A = LMIIS()
    enemies = []
    for i in range(N):
        x, h = LMIIS()
        enemies.append((x, ceil(h/A)))
    enemies.sort()
    bomb = Treap()
    ans = 0
    for i, (x, h) in enumerate(enemies):
        left = x - D
        right = x + D
        remain_h = h - bomb.interval_sum(left, right)
        if remain_h <= 0:
            continue

        ans += remain_h
        bomb.insert(x + D, remain_h)
    print(ans)
        





    
main()

Submission status: Accepted

Solution code:
from collections import deque
# end,cnt
dq = deque()

(n,d,a),*xh = [list(map(int, s.split())) for s in open(0)]
xh.sort()

total_bomb = 0
eff_bomb = 0

for x,h in xh:
    while dq and dq[0][0] < x:
        end, cnt = dq.popleft()
        eff_bomb -= cnt
    resid = h - eff_bomb * a
    if resid > 0:
        cnt = 0--resid//a
        end = x + 2 * d
        dq.append((end,cnt))
        eff_bomb += cnt
        total_bomb += cnt

print(total_bomb)

Submission status: Accepted

Solution code:
import bisect
from math import ceil
class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            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
 
    def find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1

n,d,a = map(int,input().split())
monster = sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:x[0])
x_list = [0]+[monster[i][0] for i in range(n)]+[float("inf")]
h_list = [0]+[monster[i][1] for i in range(n)]+[float("inf")]

bit = BinaryIndexedTree(n+2)
ans = 0
for i in range(1,n+1):
    hp = h_list[i] - bit.get_sum(i)
    if hp < 0:
        continue
    atk_time = ceil(hp/a)
    ans += atk_time
    top = bisect.bisect_right(x_list, x_list[i]+2*d)
    bit.add(i, atk_time*a)
    bit.add(top, -atk_time*a)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, D, A = MAP()
XH = [LIST() for _ in range(N)]

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

X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

ans = 0
imos = [0]*(N+1)
tmp = 0
for i in range(N):
	x, h = XH[i]
	tmp += imos[i]
	left = h-tmp
	if 0 < left:
		cnt = -(-left//A)
		damage = A*cnt
		idx = bisect(X, x+2*D)
		tmp += damage
		imos[idx] -= damage
		ans += cnt

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, D, A = MAP()
XH = [LIST() for _ in range(N)]

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

X, H = zip(*XH)
right = [0]*N
for i, x in enumerate(X):
	right[i] = bisect(X, x+2*D)

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

for i, (X, H) in enumerate(XH):
	if i != 0:
		damage[i] += damage[i-1]
	H -= damage[i]
	if 0 < H:
		n = -(-H//A)
		ans += n
		d = A*n
		damage[i] += d
		damage[right[i]] -= d
print(ans)

Submission status: Accepted

Solution code:
from collections import deque 
import math
n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key = lambda x:x[0])
cnt = 0
queue = deque()
sum_bomb = 0
for i in range(n):
    while len(queue) != 0 and queue[0][0]<l[i][0]:
        sum_bomb -= queue[0][1] * a
        queue.popleft()
    l[i][1] -= sum_bomb
    if l[i][1] <= 0 :
        continue
    num = math.ceil(l[i][1]/a)
    right = l[i][0] + 2 * d
    queue.append([right, num])
    cnt += num
    sum_bomb += num * a
print(cnt)

Submission status: Accepted

Solution code:

from bisect import bisect_right

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

X.sort()
place = []
hps = []
for x, h in X:
    place.append(x)
    hps.append(h)

buf = [0] * (N + 2)
ans = 0
for i in range(N):
    # Update
    buf[i + 1] += buf[i]

    # Calc count
    tmp = -(-max(0, hps[i] - buf[i + 1] * A) // A)
    ans += tmp

    # Calc range
    j = bisect_right(place, place[i] + D * 2)
    buf[i + 1] += tmp
    buf[min(j + 1, N + 1)] -= tmp

print(ans)

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
X = [0] * N
for i in range(N):
    x, h = map(int, input().split())
    X[i] = (x, h)
X = sorted(X)

from collections import deque

q = deque()

ans = 0
total = 0
for i in range(N):
    x, h = X[i]
    while (len(q) > 0 and q[0][0] < x):
        total -= q[0][1] 
        q.popleft()
    h -= total
    if h > 0:
        num = (h + A - 1) // A
        ans += num
        damage = num * A
        total += damage
        q.append((x + 2 * D, damage))
print(ans)

Submission status: Accepted

Solution code:
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind
#print(killingrange)
cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
        monstershp[i]=monstershp[i]-A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    #print(monstershp,imos)
print(cnt)

Submission status: Accepted

Solution code:
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind
#print(killingrange)
cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    #print(monstershp,imos)
print(cnt)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = 2**31 - 1
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    add(l, r, x): 区間[l, r)にxを加算 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [0] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if not v:
                continue
            self.lazy[2 * i] += v
            self.lazy[2 * i + 1] += v
            self.data[2 * i] += v
            self.data[2 * i + 1] += v
            self.lazy[i] = 0

    def add(self, l, r, x):
        """
        区間[l, r)の値にxを加算
        l, r: index(0-index)
        x: additional value
        """
        *ids, = self.gindex(l, r)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] += x
                self.data[l] += x
                l += 1
            if r & 1:
                self.lazy[r - 1] += x
                self.data[r - 1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1]) + self.lazy[i]


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

def or_less(array, x):
    # arrayの中のx以下のもののインデックス
    # arrayの中のx以下のもののうちの最大値
    index = bisect_right(array, x)
    if index == 0:
        or_less_int = -float('inf')
    else:
        or_less_int = array[index - 1]
    return index - 1

N, D, A = getNM()
que = [getList() for i in range(N)]
que.sort()

HP = [i[1] for i in que]
dis = [i[0] for i in que]

seg = LazySegmentTree([0] * (N + 1), segfunc, ide_ele)
# 現在のインデックス
now = 0
# 現在の場所
now_dis = dis[now]

ans = 0
while now < N:
    # 爆発範囲
    range = or_less(dis, now_dis + 2 * D)
    left_hp = HP[now] - seg.query(now, now + 1)
    # 爆発回数
    explo = (left_hp + A - 1) // A
    seg.add(now, range + 1, explo * A)
    ans += explo

    while True:
        if now >= N or seg.query(now, now + 1) < HP[now]:
            break
        now += 1
    if now < N:
        now_dis = dis[now]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
monster = deque(monster)
final = monster[-1][0]
ruiseki = 0
minuslist = deque()

while len(monster) > 0:
  while len(minuslist) > 0:
    if monster[0][0] >= minuslist[0][0]:
      ruiseki -= minuslist[0][1]
      minuslist.popleft()
    else:
      break
  if ruiseki < monster[0][1]:
    ans += monster[0][1] - ruiseki
    if monster[0][0] + 2*D +1 <= final:
      minuslist.append([monster[0][0]+2*D+1, monster[0][1] - ruiseki])
    ruiseki = monster[0][1]
  monster.popleft()

print(ans)

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0

final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


print(ans)

Submission status: Accepted

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
"""
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = monster[k][1]
    ans += monster[k][1]
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk
"""
final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


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

    res = 0
    tt_dmg = 0
    que = deque()
    for x, h in XH:
        while que and que[0][1] < x:
            dmg, rng = que.popleft()
            tt_dmg -= dmg

        if tt_dmg < h:
            h -= tt_dmg
            cnt = (h + a - 1) // a
            res += cnt
            dmg = cnt * a
            tt_dmg += dmg
            que.append((dmg, x + d * 2))

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if j<n:
      sd[j]+=e[i][1]+s-mx
      mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, D, A = map(int, input().split())
    XH = [None] * N
    X = [None] * N

    for i in range(N):
        XH[i] = tuple(map(int, input().split()))
        X[i] = XH[i][0]

    XH.sort()
    X.sort()
    
    ans = 0
    S = [0] * (N+1)# 与えたダメージ
    for i in range(N):
        if S[i] < XH[i][1]:
            # あと何回攻撃する？
            need = (XH[i][1]-S[i]+A-1)//A
            # 爆弾が届く範囲
            j = bisect_right(X,X[i]+2*D)
            # imos法
            S[i] += need*A
            S[j] -= need*A
            ans += need
        S[i+1] += S[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    explosion = FIFO deque and damage, range
    """
    N, D, A = read_ints()
    XH = []
    for _ in range(N):
        XH.append(read_ints())
    XH.sort()
    explosion = deque([])
    current_damage = 0
    count = 0
    for i in range(N):
        while len(explosion) != 0 and explosion[0][1] < XH[i][0]:
            current_damage -= explosion.popleft()[0]
        if current_damage < XH[i][1]: # damage is not enough
            left_health = XH[i][1]-current_damage
            more_bombs = (left_health//A+(1 if left_health%A != 0 else 0))
            count += more_bombs
            more_damage = more_bombs*A
            current_damage += more_damage
            explosion.append((more_damage, XH[i][0]+2*D))
    return count


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

Submission status: Accepted

Solution code:
import sys
import bisect

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()  # le を超える最小の 2 冪
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  # (0, i]
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res

    def bisect_left(self, v):  # self.sum(i) が v 以上になる最小の i
        n, values = self.n, self.values
        if v > values[n]:
            return None
        i, step = 0, n >> 1
        while step:
            if values[i + step] < v:
                i += step
                v -= values[i]
            step >>= 1
        return i + 1


def main():

    N, D, A = in_nn()
    XH = sorted(in_nl2(N))
    X = [0] * N
    H = [0] * N

    for i in range(N):
        x, h = XH[i]
        X[i] = x
        H[i] = h

    bit = Bit(N)

    ans = 0
    for i in range(N):

        x, h = X[i], H[i]
        j = bisect.bisect_right(X, x + 2 * D)
        cnt_bomb = bit.sum(i + 1)

        h -= A * cnt_bomb
        if h <= 0:
            continue

        cnt = -(-h // A)
        ans += cnt
        bit.add(i + 1, cnt)
        bit.add(j + 1, -cnt)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import *

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

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

X = []
H = []
for x, h in data:
    X.append(x)
    H.append(h)

Imos = [0]*(N+1)
cnt = 0
damage = 0
res = 0
for i in range(N):
    damage -= Imos[i]*A
    h = H[i] - damage
    x = X[i]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = min(bisect_right(X, x+2*D)-1, N-1)
        Imos[p+1] += cnt
        damage = damage + cnt * A
        res += cnt
print(res)

Submission status: Accepted

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

hit = []

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

que = []
ans = 0
bomb = 0
for i in range(n):
  while True:
    if len(que) == 0:
      break
    if hit[i][0] <= que[0][0]:
      break
    bomb -= que[0][1]
    que.pop(0)
  r = hit[i][1] - bomb
  if r < 0:
    continue
  c = (r + a - 1)//a
  ans += c
  bomb += c*a
  que.append((hit[i][0]+2*d,c*a))
print (ans)