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:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
INF = float("inf")


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


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):

    bit = Bit(N+1)

    XH = [(x, h) for x, h in zip(X, H)]
    XH.sort()
    for i in range(N):
        if i == 0:
            bit.add(i+1, XH[i][1])
        else:
            bit.add(i+1, XH[i][1]-XH[i-1][1])
    # print(XH)

    tot = 0
    curr = 0
    while True:
        # Hが正であるうち、xが最も小さいxhを見つける すべてでO(N)
        # print([bit.sum(i+1) for i in range(N)])

        flag = False
        for i in range(curr, N):
            if bit.sum(i+1) > 0:
                flag = True
                break
        if flag:
            curr = i+1
        else:
            break
        # できるだけ多くを巻き込むようにバクダンを使う。 x ~ x+2D
        x, h = XH[i]
        h = bit.sum(i+1)
        kaisu = -(-h//A)
        damage = A*kaisu
        tot += kaisu

        # 巻き込むモンスターは i ~ jまで
        j = bisect_left(XH, (x+2*D+1, 0))
        bit.add(i+1, -damage)
        bit.add(j+1, +damage)
        # for k in range(i, j):
        #     x, h = XH[k]
        #     XH[k] = (x, h-damage)
    print(tot)
    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()

Submission status: Accepted

Solution code:
n, d, a = [int(s) for s in input().strip().split()]
X, H = [0] * n, [0] * n
for i in range(n):
    X[i], H[i] = [int(s) for s in input().strip().split()]

result = 0
monsters = sorted(zip(X, H))
q = []
ptr = 0
delta = 0
for x, h in monsters:
    while ptr < len(q) and q[ptr][0] < x:
        delta += q[ptr][1]
        ptr += 1
    h += delta
    if h <= 0:
        continue
    result += (h + a - 1) // a
    delta -= (h + a - 1) // a * a
    q.append((x + 2 * d, (h + a - 1) // a * a))
print(result)

Submission status: Accepted

Solution code:

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(X, x+D*2+1)
    cnt[j]+=n*A
    res += n*A
    ans+=n
print(ans)

Submission status: Accepted

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

XH.sort()

B=0
Bt=[0]*N
Bx=[0]*N
l=0
r=-1

ans=0
for i in range(N):
    x,h = XH[i]
    if h<=0: continue
    #今までの爆弾ダメージを計算
    while l<=r:
        if Bx[l]<x: #もう届かない
            B-=Bt[l]*A
            l+=1
        else: #まだ届く
            break
    h-=B
    if h>0:
        t=(h+A-1)//A #ここで爆弾を使う回数
        ans+=t
        r+=1
        Bt[r]=t
        Bx[r]=x+(2*D)
        B+=A*t

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, D, A = map(int, input().split())
a = []
b = []
res = 0
for _ in range(N):
  x, h = map(int, input().split())
  a.append([x, h])
  b.append(x)
a.sort(key = lambda x: x[0])
b.sort()
imos = [0] * (N + 2)
for i in range(N):
  a[i][1] += imos[i]
  imos[i + 1] += imos[i]
  if a[i][1] <= 0: continue
  l = a[i][0]
  r = a[i][0] + 2 * D
  t = bl(b, r)
  if t < N:
    if b[t] > r: t -= 1
  x = -(-a[i][1] // A)
  imos[i + 1] -= A * x
  imos[t + 1] += A * x
  a[i][1] = 0
  res += x
  #print(i, t)
  #print(a, imos)
#print(imos)
#print(a)
print(res)

"""
AtCoderレートで全ての優劣が決定される異世界ベラルーシ。
ここでは他世界からの転生者は「旅行者 - tourist -」と呼ばれる。

不幸な交通事故から、社長 高橋直小はベラルーシに異世界転生してしまった。
"""

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
monster=[]
for i in range(n):
    x,h=map(int,input().split())
    monster.append((x,h))
monster.sort()
x_list=[]
h_list=[]
for i in monster:
    x_list.append(i[0])
    h_list.append(i[1])
ans=0
import bisect
damage=[0]
for i in range(n):
    p=bisect.bisect_left(x_list,x_list[i]-2*d)
    D=damage[i]-damage[p]
    if h_list[i]<=D:
        damage.append(damage[-1])
        continue
    r=h_list[i]-D
    c=(r+a-1)//a
    ans+=c
    damage.append(damage[-1]+a*c)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1
        return res

def solve():

    n,d,a = LI()
    p = LIR(n)
    ans = 0
    p.sort()
    X = [p[i][0] for i in range(n)]
    s = SegmentTree(n,0)
    for i in range(n):
        x,h = p[i]
        j = bisect.bisect_left(X,x-2*d)
        if i != j:
            su = s.get(j,i)
            h -=  s.get(j,i)
        if h > 0:
            l = x
            k = math.ceil(h/a)
            ans += k
            s.update(i,k*a)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N,D,A=map(int,input().split())
D*=2 # 爆発の長さ
X=[None]*N
for i in range(N):
  X[i]=list(map(int,input().split()))

X=sorted(X,key=lambda x:x[0])
lastX=X[-1][0] # 最後のモンスターの場所
from collections import defaultdict
damage=defaultdict(int)
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1]
  if h>0:
    dele=set()
    for d in damage.items():
      if d[0]<x:
        dele.add(d[0])
      else:
        h-=d[1]
    for p in dele:
      del damage[p]
  if h>0:
    turn=(h+A-1)//A
    if x+D>lastX:
      damage[lastX]+=turn*A
    else:
      damage[x+D]=turn*A
    ans+=turn
print(ans)

Submission status: Accepted

Solution code:
import math
from heapq import heappop, heappush
N, D, A = map(int, input().split())
D *= 2
enemies = []
for _ in range(N):
    x, h = map(int, input().split())
    enemies.append((x, math.ceil(h / A)))
enemies.sort()

t = 0
ans = 0
attacks = []
attacksum = 0
for f in range(N):
    x, h = enemies[f]
    while attacks:
        if x > attacks[0][0]:
            ax, ad = heappop(attacks)
            attacksum -= ad
        else:
            break
    if h <= attacksum:
        continue
    damage = h - attacksum
    attacksum += damage
    ans += damage
    heappush(attacks, (x + D, damage))

print(ans)

Submission status: Accepted

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

bombloc = [-1]
bombdam = [ 0]
nbomb = 1
ibomb = 0 # leftmost active bomb
damage = 0
ans = 0
for x, h in XH:
    while ibomb<nbomb and bombloc[ibomb]+D<x:
        damage -= bombdam[ibomb]
        ibomb+=1
        
    h_remain = h-damage
    if h_remain<=0: continue

    n = (h_remain+A-1)//A
    bombloc.append(x+D)
    bombdam.append(n*A)
    nbomb += 1
    damage += n*A
    ans += n
    
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect
input = sys.stdin.readline
n,d,a = map(int,input().split())

def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


xh = []
dg = 10**10

for i in range(n):
    x,h = map(int,input().split())
    xh.append(x*dg+h)

xh.sort()

res = 0

for i in range(n):
    x,h = xh[i]//dg,xh[i]%dg
    k1 = bisect.bisect_left(xh,(x-2*d)*dg)
    
    r = query(k1,i)

    h -= r*a
    if h <= 0:
        continue

    if h%a == 0:
        res += h//a
        update(i,h//a)
    else:
        res += h//a+1
        update(i,h//a+1)
    
print(res)

Submission status: Accepted

Solution code:
n, d, a = [int(i) for i in input().split()]
xh = [[int(i) for i in input().split()] for _ in range(n)]
xh.sort()
da = [0] * n
r = [0] * n
ru=0

ans = 0
j=0
for i in range(n):
    da[i]+=ru
    if xh[i][1] > da[i]:
        up = (xh[i][1] - da[i]) // a
        if (xh[i][1] - da[i]) % a != 0:
            up += 1
        ans += up
        up *= a
        da[i] += up
        ru+=up
        
        while j!=n-1 and xh[j+1][0] <= xh[i][0] + 2 * d:
            j += 1
        r[j]+=up
    
    ru-=r[i]
print(ans)

Submission status: Accepted

Solution code:
import math
from heapq import heappop, heappush
N, D, A = map(int, input().split())
D *= 2
enemies = []
for _ in range(N):
    x, h = map(int, input().split())
    enemies.append((x, math.ceil(h / A)))
enemies.sort()

t = 0
ans = 0
attacks = []
attacksum = 0
for f in range(N):
    x, h = enemies[f]
    while attacks:
        if x > attacks[0][0]:
            ax, ad = heappop(attacks)
            attacksum -= ad
        else:
            break
    if h <= attacksum:
        continue
    damage = h - attacksum
    attacksum += damage
    ans += damage
    attacks.append((x + D, damage))

print(ans)

Submission status: Accepted

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

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

monsters.sort()

def problem_a(h):
    if h <= 0:return 0
    ans = h // a
    if h % a != 0:
        ans += 1
    return ans

cnt_sum = 0
cnt = [0] * n
l = 0
for i in range(n):
    while monsters[l][0] + 2*d < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
        
    already = cnt_sum * a
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

print(sum(cnt))

Submission status: Accepted

Solution code:
class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() #木の段数
        self.N0 = 1<<self.height #木の横幅 >= N
        self.laz = [self.ID_M]*(2*self.N0) #作用素の木
        self.val = None #値の配列

    #初期値の配列を作る
    def build(self,initial):
        self.val = initial[:]

    #laz[k] を子に伝える、k が一番下の場合は laz[k] を val に反映する
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    # 遅延をすべて解消する
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        self.thrust(L)
        self.thrust(R-1)
        #登りながら関数 f を合成
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    # values[k] を取得。
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    # values[k] = x 代入する
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,d,a = [int(i) for i in readline().split()]
xh = [tuple(int(i) for i in readline().split()) for _ in range(n)]
xh.sort()

from operator import add
ID_M = 0


seg = segment_tree_dual(n, add, add, ID_M)
X = [i[0] for i in xh]
H = [i[1] for i in xh]
seg.build(H)


from bisect import bisect_right

d *= 2
ans = 0
for i in range(n):
    h = seg.point_get(i)
    if h < 0: continue
    ans += (h+a-1)//a
    dam = (h+a-1)//a*a 
    
    #print(d,X,X[i]+d)
    idx = bisect_right(X,X[i]+d)-1
    #print(idx)
    seg.update(i,idx,-dam)



print(ans)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

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

    def get(self, i):
        return self.sum_range(i, i)

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

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

n,d,a = map(int, input().split())
d *= 2
data = []
s = set()
for i in range(n):
    x,h = map(int, input().split())
    s.add(x)
    s.add(x+d)
    data.append([x,h])
data.sort()
dd = sorted(s)
ddd = {j:i for i,j in enumerate(dd)}
m = len(dd)

BIT = Binary_Indexed_Tree(m+1)
ans = 0
for x,h in data:
    i = ddd[x]
    rem = BIT.sum_range(i+1 , m+1)
    h = max(h-rem, 0)
    cnt = -(-h//a)
    ans += cnt
    BIT.add(ddd[x+d]+1, cnt*a)
print(ans)

Submission status: Accepted

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

N,D,A=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]
M.sort()

PLACE=[M[i][0] for i in range(N)]
HP=[M[i][1] for i in range(N)]

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N):
    SEG[i+seg_el]=HP[i]
    

def indexes(L,R): # 遅延伝搬すべきノードのリストを下から上の順に返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def adds(l,r,x): # 区間[l,r)を +x 更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬. 上から更新していく. （ただし, 今回はうまくやるとこの部分を省ける. addはクエリの順番によらないので. addではなく, updateの場合必要）
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
    
    while L!=R:
        if L > R:
            SEG[L]+=x
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]+=x
            LAZY[R]+=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=min(SEG[ind<<1],SEG[1+(ind<<1)])  # 最初の遅延伝搬を省いた場合, ここを変える
        
def getvalues(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

plind=0
ANS=0
import bisect

while plind<N:
    RHP=getvalues(plind,plind+1)
    if RHP>0:
        MAX=PLACE[plind]+2*D
        x=bisect.bisect_right(PLACE,MAX)
        adds(0,x,(-RHP//A)*A)
        ANS+=-(-RHP//A)

    else:
        plind+=1

print(ANS)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)
imos=[0]*(n+1)
mi=0
ans=0
for i in range(n):
  mi-=imos[i]
  h[i]=max(h[i]-mi*a,0)
  atk=0--h[i]//a
  ans+=atk
  mi+=atk
  point=x[i]+d*2
  index=bisect_right(x,point)
  imos[index]+=atk
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from operator import itemgetter
    from bisect import bisect_right
    input = sys.stdin.readline

    N, D, A = map(int, input().split())
    info = []
    for _ in range(N):
        x, h = map(int, input().split())
        info.append((x, h))
    info.sort(key=itemgetter(0))

    imos = [0] * N
    X = [info[i][0] for i in range(N)]
    H = [info[i][1] for i in range(N)]
    ans = 0
    i = 0
    dam = 0
    while True:
        dam += imos[i] * A
        assert dam >= 0
        bomb = (max(H[i] - dam, 0) - 1) // A + 1
        ans += bomb
        #print(i, ans, imos)
        if H[i] > dam:
            j = bisect_right(X, X[i] + 2*D)
        else:
            j = 0
        if j == i:
            i += 1
        else:
            if i == N-1:
                break
            imos[i+1] += bomb
            if j != N:
                imos[j] -= bomb
            i += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import operator
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353


class LazySegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    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 とする
        self._size = 1 << (size - 1).bit_length()
        self._fn = fn

        self._lazy = [0] * (self._size * 2 - 1)
        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 add(self, from_i, to_i, value, k=0, L=None, r=None):
        """
        [from_i, to_i) を、それぞれの値と value に fn を適用した値で更新する
        :param int from_i:
        :param int to_i:
        :param int value:
        :param int k: self._tree のインデックス
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        self._eval(k, L, r)

        # 範囲外
        if to_i <= L or r <= from_i:
            return

        if from_i <= L and r <= to_i:
            # 完全に被覆してる
            self._lazy[k] += (r - L) * value
            self._eval(k, L, r)
        else:
            # 中途半端
            self.add(from_i, to_i, value, k * 2 + 1, L, (L + r) // 2)
            self.add(from_i, to_i, value, k * 2 + 2, (L + r) // 2, r)
            self._tree[k] = self._fn(self._tree[k * 2 + 1], self._tree[k * 2 + 2])

    def _eval(self, k, L, r):
        """
        遅延配列の値を評価する
        :param k:
        :param L:
        :param r:
        """
        if self._lazy[k] != 0:
            # 本体を更新
            self._tree[k] += self._lazy[k]
            # 一番下じゃなければ伝播させる
            if r - L > 1:
                self._lazy[k * 2 + 1] += self._lazy[k] >> 1
                self._lazy[k * 2 + 2] += self._lazy[k] >> 1
            self._lazy[k] = 0

    def get(self, from_i, to_i, 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:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        self._eval(k, L, 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


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

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

lr = []
r = 0
for l in range(N):
    while r < N and X[r] <= X[l] + D * 2:
        r += 1
    lr.append((l, r))

imos = [0] * (N + 1)
cum = 0
ans = 0
for l, r in lr:
    cum += imos[l]
    h = H[l] - cum
    if h > 0:
        cnt = (h + A - 1) // A
        cum += cnt * A
        imos[r] -= cnt * A
        ans += cnt
print(ans)

Submission status: Accepted

Solution code:
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:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,d,a = nm()
l = [tuple(nm()) for _ in range(n)]
l.sort()
l += [(10**20,10**20)]
r = [0]*(n+3)
rind = 0
ans = 0
for i in range(n):
    x,h = l[i]
    r[i] += r[i-1]
    h -= r[i]
    # print(i,"x,h",x,h)
    if h <= 0: continue
    curd = x + 2*d
    while l[rind+1][0] <= curd:
        rind += 1
    # print(i,"cued,rind",curd,rind)
    cnt = (h-1)//a + 1
    dam = cnt*a
    r[i] += dam
    r[rind+1] -= dam
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from operator import itemgetter
n, d, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

info = sorted(info, key = itemgetter(0))
bit = BIT(n)

for i in range(n):
    bit.add(i, i+1, info[i][1])

info.append([10**18, 0])
ans = 0 
r = 0
for i in range(n):
    num = bit.get_val(i)
    if num <= 0:
        continue
    while True:
        if info[r][0] - info[i][0] > 2*d:
            break
        else:
            r += 1
    ans += -((-num) // a)
    bit.add(i, r, -(-((-num) // a)) * a)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

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

X = [x for x, _ in XH]

ans = 0
ims = [0] * (N + 1)
cnt = 0

for now, (x, h) in enumerate(XH):
    cnt += ims[now]
    if cnt * A >= h:
        continue
    ness = -(-(h - cnt * A) // A)
    cnt += ness

    i = bisect_right(X, x + D * 2)
    ims[now] += ness
    ims[i] -= ness
    ans += ness

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
def input():
	return sys.stdin.buffer.readline()[:-1]

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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,D,A = map(int,readline().split())
m = map(int,read().split())
X, H = zip(*sorted(zip(m,m)))

Xs = sorted(set(X) | set(x + D + D for x in X))
x_to_i = {x:i for i,x in enumerate(Xs)}

L = len(Xs)
d_atk = [0] * L

HP = [0] * L
for x,h in zip(X,H):
    i = x_to_i[x]
    HP[i] = h

d_atk = [0] * L

atk = 0 # 予約済の値を管理
answer = 0
for i in range(L):
    x = Xs[i]
    h = HP[i]
    if h > atk:
        rest = h - atk
        n = (rest + A - 1) // A
        atk += n * A
        answer += n
        d_atk[x_to_i[x+D+D]] = -n * A
    atk += d_atk[i]

print(answer)

Submission status: Accepted

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

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, d, a = na()
ms = []
for i in range(n):
    ms.append(na())

ms.sort(key=itemgetter(0))
pq = deque()
dmg = 0
ans = 0
for i in range(n):
    while len(pq) > 0 and pq[0][0] <= ms[i][0]:
        dmg -= pq[0][1]
        pq.popleft()

    h = ms[i][1]
    x = ms[i][0]
    h -= dmg
    if h > 0:
        nu = (h+a-1)//a
        ans += nu
        dmg += a*nu
        pq.append((x+2*d+1, a*nu))

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [0] * (n + 1)
h = [0] * (n + 1)
s = [0] * (n + 1)

for i, (f, g) in enumerate(xh):
    x[i], h[i] = f, g
x[n] = 10 ** 9 + 1
ans = 0
for i in range(n):
    if i > 0:
        s[i] += s[i - 1]
    h[i] -= s[i]
    if h[i] > 0:
        num = 0 - - h[i] // a
        ans += num
        s[i] += num * a

        j = bisect_right(x, x[i] + d * 2)
        s[j] -= num * a
print(ans)