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

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

N,d,a=LI()

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

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

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

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

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

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

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

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

show_flg=False
show_flg=True

ans=0
n=N
m=[]
for i in range(n):
    x,h=LI()
    m.append((x,h))
m.append((inf,0))
m.sort(key=lambda x:x[0])
X=[x for x,h in m]
H=[h for x,h in m]

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

print(ans)

Submission status: Accepted

Solution code:
import bisect


def main():
    N, D, A = list(map(int, input().split()))
    monsters = [list(map(int, input().split())) for _ in range(N)]
    monsters.sort()
    X = [m[0] for m in monsters]
    # 端から貪欲に攻撃していく
    ans = 0
    damages = [0] * (N + 1)
    for n, monster in enumerate(monsters):
        x, h = monster
        h = max(0, h - damages[n])
        to_n = bisect.bisect_right(X, x + 2 * D)
        cnt = (h + A - 1) // A  # ceil(h / A)
        ans += cnt
        damages[n] += A * cnt
        damages[to_n] -= A * cnt
        damages[n + 1] += damages[n]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil

# n个怪物，d杀伤半径，a杀伤值
n, d, a = map(int, input().split())

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])

bombs = deque()

ans = 0
valid_bomb = 0
for pos, hp in ms:
    # 查看队列里的bomb是否对当前怪物有效
    while bombs and bombs[0][0] < pos:
        bomb_border, bomb_cnt = bombs.popleft()
        valid_bomb -= bomb_cnt
    
    # 还需新加多少bomb才能灭掉当前怪物
    bomb_cnt = max(0, hp - valid_bomb)
    valid_bomb += bomb_cnt
    ans += bomb_cnt
    
    # 新加的bomb放入队列
    if bomb_cnt > 0:
        bombs.append([pos + d * 2, bomb_cnt])
 
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil

# n个怪物，d杀伤半径，a杀伤值
n, d, a = map(int,input().split())

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])
 
bombs = deque()
 
ans = 0
valid_bomb = 0
for pos, hp in ms:
  # 查看队列里的bomb是否对当前怪物有效
  while bombs and bombs[0][0] < pos:
    bomb_border, bomb_cnt = bombs.popleft()
    valid_bomb -= bomb_cnt
  
  # 还需新加多少bomb才能灭掉当前怪物
  bomb_cnt = max(0, hp - valid_bomb)
  valid_bomb += bomb_cnt
  ans += bomb_cnt
  
  # 新加的bomb放入队列
  if bomb_cnt > 0:
    bombs.append([pos + d * 2, bomb_cnt])
 
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil
 
n,d,a = map(int,input().split())
M = [list(map(int,input().split())) for i in range(n)]
M = sorted([(x,ceil(h/a)) for x,h in M])
 
que = deque()
 
ans = 0
atack = 0
for x,h in M:
  while len(que) > 0 and que[0][0] < x:
    tx,ta = que.popleft()
    atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  if bomb_num > 0:
    que.append([x+d*2,bomb_num])
 
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil

n,d,a = map(int,input().split())
M = [list(map(int,input().split())) for i in range(n)]
M = [[x,ceil(h/a)] for x,h in M]
M = sorted(M)

que = deque()

ans = 0
atack = 0
for x,h in M:
  while len(que) > 0 and que[0][0] < x:
    tx,ta = que.popleft()
    atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  if bomb_num > 0:
    que.append([x+d*2,bomb_num])

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque
N,D,A = map(int,input().split())
monsters = sorted([ list(map(int,input().split())) for _ in range(N) ])
monsters = [ [x, math.ceil(h/A)] for x,h in monsters ]
# print(monsters)
que = deque()
cur = 0
ans = 0
for x,h in monsters:
  while que and x > que[0][0]:
    _,n = que.popleft()
    cur -= n

  need = max(0, h-cur)
  ans += need
  cur += need

  if h:
    # 対象のモンスターを最も左端にいることを想定
    que.append([x+2*D, need])

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
      l, r = l >> 1, r >> 1
      
N,D,A = IL()
data = ILL(N)
data.sort()
PLACE = [d[0] for d in data]
HP = [-(-d[1]//A) for d in data]
MAKIKOMI = []
for i in range(N):
  x = PLACE[i]
  p  = bisect.bisect(PLACE,x+2*D)
  MAKIKOMI.append(p-i)

ST = SegmentTree(N,0)
ST.build(HP)
ans = 0
now = 0
while now < N:
  while ST.get(now) > 0:
    t = ST.get(now)
    ans += t
    ST.add(now,now+MAKIKOMI[now],-t)
  now += 1
print(ans)

Submission status: Accepted

Solution code:
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])
ans = 0

XN = [[x, ceil(h/A)] for x, h in XH]
# 左端のモンスターに攻撃が必要な回数はそこから2*Dだけ右にあるモンスターにまで波及できる
cnum = 0
que = deque()
ans = 0
for x, n in XN:
    while que and x > que[0][0]:
        _, num = que.popleft()
        cnum -= num
    need = max(0, n - cnum)
    ans += need
    cnum += need

    if need:
        que.append([x+2*D, need])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, D, A = NMI()
    M = [NLI() for _ in range(N)]
    M.sort()
    maxj = [0] * N
    j = 0
    for i in range(N):
        while j < N-1:
            if M[j+1][0] <= M[i][0] + D*2:
                j += 1
            else:
                break
        maxj[i] = j
    S = [0]*(N+1)
    ans = 0
    for i in range(N):
        x = M[i][0]
        hp = M[i][1] - S[i]
        need = max((hp-1) // A + 1, 0)
        ans += need
        S[i] += need * A
        S[maxj[i]+1] -= need * A
        S[i+1] += S[i]

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n,d,a = map(int, input().split())
xhl = []
for _ in range(n):
    x,h = map(int, input().split())
    cnt = (h-1)//a + 1
    xhl.append((x,cnt))

xhl.sort()

attack_q = deque([])
attack_sum = 0
ans = 0
for x,h in xhl:
    # print('----',((x,h)))
    # print(attack_q)
    # print(attack_sum)
    while attack_q and attack_q[0][0] < x:
        poped_cnt = attack_q.popleft()[1]
        attack_sum -= poped_cnt
    # print(attack_q)
    # print(attack_sum)
    rem = h-attack_sum
    if rem <= 0:
        continue
    attack_sum += rem
    ans += rem
    attack_q.append((x+2*d, rem))
    # print(rem)

print(ans)
# print(xhl)

Submission status: Accepted

Solution code:
from math import ceil
N,D,A = list(map(int, input().split()))
P = []
for _ in range(N):
  P.append(list(map(int, input().split())))
  # X,H

P.sort()

#for p in P:
#  print(p)
  
# Attack[i] : i番目（Xi）を左端に爆弾を投げたとき、巻き込める最大の番号Xj
Attack = [-1 for _ in range(N)]
leftx, leftj = 0,0
for i in range(N):
  now = P[i][0]
  leftx = now + 2*D
  while leftj < N:
    if P[leftj][0] <= leftx:
      leftj += 1
    else:
      break
  Attack[i] = leftj - 1
  
#print(Attack)
# damage管理
# 範囲攻撃はimosっぽくやる。届いた左端に+Dして、届いた右端の右隣に-Dする
# 今までのダメージ総和をworkとして持ちつつ、imosで回復すればよい
wk_dam = 0
imos = [0] * (N+1)
ans = 0
for i in range(N):
  wk_dam += imos[i]
  #print(i,wk_dam,P[i][1],ans)
  if P[i][1] <= wk_dam:
    # すでに累積ダメージで死んでる
    continue
  cnt = (P[i][1] - wk_dam + A-1) // A # ceil(zanHP / A)
  wk_dam += cnt * A
  imos[i] += cnt * A
  imos[Attack[i]+1] -= cnt * A
  ans += cnt
  
print(ans)
#print(imos)

Submission status: Accepted

Solution code:


class LasySegmentTree:
    def __init__(self, size: int, segfunc, lazy_ide_ele=0):
        self.lazy_ide_ele = lazy_ide_ele
        self.segfunc = segfunc
        self.N0 = 1 << (size - 1).bit_length()
        self.lazy = [self.lazy_ide_ele] * (2 * self.N0)

    def gindex(self, left, right):
        L = left + self.N0
        R = right + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            idx = i - 1
            v = self.lazy[idx]
            if v == self.lazy_ide_ele:
                continue
            self.lazy[2 * idx + 1] = self.segfunc(self.lazy[2 * idx + 1], v)
            self.lazy[2 * idx + 2] = self.segfunc(self.lazy[2 * idx + 2], v)
            self.lazy[idx] = self.lazy_ide_ele

    def update(self, left: int, right: int, x):
        L = self.N0 + left
        R = self.N0 + right

        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] = self.segfunc(self.lazy[R - 1], x)
            if L & 1:
                self.lazy[L - 1] = self.segfunc(self.lazy[L - 1], x)
                L += 1
            L >>= 1
            R >>= 1

    def query(self, k: int):
        self.propagates(*self.gindex(k, k + 1))
        return self.lazy[k + self.N0 - 1]



from operator import add
from bisect import bisect_right
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    X, _ = zip(*AB)


    seg_lazy = LasySegmentTree(N+10, segfunc=add)
    ans = 0
    for i in range(N):
        d = AB[i][1] - seg_lazy.query(i)
        if d <= 0:
            continue
        cnt = -(-d//A)
        ans += cnt
        idx = bisect_right(X, (X[i] + 2*D))
        seg_lazy.update(i, idx, cnt*A)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

import operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size



from bisect import bisect_right
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    X, _ = zip(*AB)
    D = 2*D

    seg = SegmentTree(N+10)
    ans = 0
    for i, (x, h) in enumerate(AB):
        h = -(-h // A)
        damage = seg.get(0, i+1)

        if h < damage:
            continue
        ans += h - damage
        seg.add(i, h-damage)
        seg.add(bisect_right(X, x + D), - h + damage)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()

    # imos
    imos = [0] * (N+1)
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] <= 2 * D + x:
                R += 1
            d = h - imos[l]
            cnt = -(-d//A) # 切り上げ
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()

    # imos
    imos = [0] * (N+1)
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] <= 2 * D + x:
                R += 1
            d = h - imos[l]
            cnt = (d+A-1) // A
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
import bisect
 
n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0

x.sort()
x.append(1145141919810)
h.append(0)

imos = [0]*(n+1)

atk = math.ceil(itv[0][1]/a)
imos[0] += atk * a
b = bisect.bisect(x,itv[0][0] + (2*d))
imos[b] -= atk * a
ans += atk
    
for i in range(1,n):
    atk = 0
    imos[i] += imos[i-1]
    if itv[i][1] > imos[i]:
        atk = math.ceil((itv[i][1]-imos[i])/a)
        imos[i] += atk * a
        b = bisect.bisect(x,itv[i][0] + (2*d))
        imos[b] -= atk * a
    ans += atk

print(ans)

Submission status: Accepted

Solution code:
def binary(N, LIST, num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [(j + a - 1) // a for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bnum = max(h[i] - (bsum[i - 1] + bomb[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bsum[i - 1] + bomb[i]
    ans += bnum
print(ans)

Submission status: Accepted

Solution code:
def binary(N, LIST, num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [(j + a - 1) // a for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(h[i] - bsum[i], 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Submission status: Accepted

Solution code:
def binary(N, LIST, num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


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

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max((h[i] + a - 1) // a - bsum[i], 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Submission status: Accepted

Solution code:
from math import ceil


def binary(N, LIST, num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


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

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i in range(n):
    j = binary(n, x, x[i] + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(ceil(h[i] / a - bsum[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Submission status: Accepted

Solution code:
from math import ceil

def binary(N,LIST,num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


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

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i, xi in enumerate(x):
    j = binary(n, x, xi + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max(ceil(h[i] / a - bsum[i]), 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n , d , a = map(int,input().split())
mon = [tuple(map(int,input().split())) for i in range(n)]
mon.sort()
p = deque(mon)
baku = deque()
cou = 0
ans = 0
while p:
    nowx , nowh = p.popleft()
    while baku:
        bx , bh = baku.popleft()
        if bx >= nowx:
            baku.appendleft((bx,bh))
            break
        elif bx < nowx:
            cou -= bh
    if nowh <= cou:
        continue
    elif nowh > cou:
        k = -((-nowh+cou)//a)
        ans += k
        cou += a*k
        baku.append((nowx+2*d,a*k))
print(ans)

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 = []
h = []
for d, i in sorted(X):
    x.append(d)
    h.append(i)

ans = 0
k = [-(-v // A) for v in h]
y = [0] * (N + 2)
for i in range(N):
    y[i + 1] += y[i]
    s = max(0, k[i] - y[i + 1])
    ans += s
    y[i + 1] += s
    y[bisect_right(x, x[i] + 2 * D) + 1] -= s
    
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))

X = [x for x,h in XH]
H = [h for x,h in XH]

dH = [0]*(N+1)

cnt = 0
acc = 0

cnt = 0
i = 0
j = 0
while i < N:
    while j < N and X[j] <= X[i]+2*D:
        j += 1

    acc -= dH[i]
    H[i] -= acc
    if H[i] > 0:
        c = (H[i]-1)//A + 1
        acc += c*A
        dH[j] += c*A
        cnt += c
    i += 1

print(cnt)

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N, D, A = map(int, input().split())
    monster = [list(map(int, input().split())) for _ in range(N)]

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

    attack = []
    for i in range(N):
        attack.append(math.ceil(monster[i][1] / A))

    acc_damage = 0
    attacked = deque([])
    answer = 0

    for i in range(N):
        x = monster[i][0]
        h = attack[i]

        while attacked and x > attacked[0][0]:
            limit, damage = attacked.popleft()
            acc_damage -= damage

        need = max(0, h - acc_damage)
        answer += need

        acc_damage += need

        if need:
            attacked.append((x + 2 * D, need))

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()

    # x, damage
    q = deque([])

    acc_damage = 0

    ans = 0
    for i in range(N):
        x = X[i]
        h = monster[x]

        while q and q[0][0] < x:
            p, damage = q.popleft()
            acc_damage -= damage

        if h - acc_damage <= 0:
            continue

        cnt = (h - acc_damage + A - 1) // A
        ans += cnt
        acc_damage += cnt * A

        q.append((x + 2 * D, cnt * A))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
from collections import deque
minusd=deque()
nowd=0
ans=0
for x,h in xh:
  while minusd and minusd[0][1]<=x:
    d_,_=minusd.popleft()
    nowd-=d_
  tmp=max(0,(h-nowd+a-1)//a)
  ans+=tmp
  nowd+=tmp*a
  minusd.append([tmp*a,x+2*d+1])
  #print(ans,nowd)
print(ans)