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: Time Limit Exceeded

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

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

XH.sort()

index = 0
pt = XH[0][0] + 2 * D
ht = (-(-XH[0][1] // A)) * A
answer = -(-XH[0][1] // A)

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

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
l=[[0,0] for _ in range(n)]
for i in range(n):
  x,h=map(int,input().split())
  l[i]=[x,h]
l.sort()
ans=0
for i in range(n):
  [x,h]=l[i]
  if h>=0:
    c=(h+a-1)//a
    for j in range(i+1,n):
      if l[j][0]>x+2*d:
        break
      else:
        l[j][1]-=c*a
    ans+=c
  





print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

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

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    hani=bisect.bisect_right(xlist, pos+d)
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            if xhlist[now+i][1]>0:
                xhlist[now+i][1]-=atk
            if swit==0:
                if xhlist[now+i][1]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect
from operator import itemgetter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key=itemgetter(0))
X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

bit0 = BIT(N)
bit1 = BIT(N)

ans = 0
for i in range(N):
    x = H[i]
    bit0.add(i,-x*i)
    bit1.add(i,x)
    bit0.add(i+1,x*(i+1))
    bit1.add(i+1,-x)
    h = bit1.sum(i)*(i+1)+bit0.sum(i)
    if i != 0:
        h -= bit1.sum(i-1)*i+bit0.sum(i-1)
    if h>0:
        ans += ceil(h/A)
        x = -ceil(h/A)*A
        j = bisect(X,X[i]+2*D)-1
        bit0.add(i,-x*i)
        bit1.add(i,x)
        bit0.add(j+1,x*(j+1))
        bit1.add(j+1,-x)

print(ans)

Submission status: Time Limit Exceeded

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

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

output = 0
s = 0
while s<N:
    if XH[s][1]<0:
        s+=1
        continue
    X = XH[s][0]
    L = X
    H = XH[s][1]
    B = H//A+1*(H%A!=0)
    output += B
    flag = 0
    s+=1
    while (s<N)and(XH[s][0]<=L+2*D):
        XH[s][1]+= -1*B*A
        if (XH[s][1]>0)and(flag==0):
            start=s
            flag = 1
        s+=1
    if flag ==1:
        s=start

print(output)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from math import ceil
N,D,A = map(int,input().split())
X = list()
H = list()
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
XH = np.array(XH)
X = XH[:,0]
H = XH[:,1]
ans = 0
for i in range(N):
    tmp = i
    if H[i] > 0:
        tmp = np.searchsorted(X,X[i]+2*D,side = "right")
        num = ceil(H[i]/A)
        H[i:tmp] -= A*num
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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)]
H = [XH[i][1] for i in range(N)]

bit0 = BIT(N)
bit1 = BIT(N)

ans = 0
for i in range(N):
    x = H[i]
    bit0.add(i,-x*i)
    bit1.add(i,x)
    bit0.add(i+1,x*(i+1))
    bit1.add(i+1,-x)
    h = bit1.sum(i)*(i+1)+bit0.sum(i)
    if i != 0:
        h -= bit1.sum(i-1)*i+bit0.sum(i-1)
    if h>0:
        ans += ceil(h/A)
        x = -ceil(h/A)*A
        j = bisect(X,X[i]+2*D)-1
        bit0.add(i,-x*i)
        bit1.add(i,x)
        bit0.add(j+1,x*(j+1))
        bit1.add(j+1,-x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,d,a = m()

ppp = [0 for i in range(n)]

aaa = []
lll = []
rrr = []
co = 0
for i in range(n):
    p = l()
    aaa.append([p[0],-(-p[1]//a)])
aaa.sort()
for i in range(n):
    lll.append([aaa[i][0],aaa[i][0]+2*d])

for i in range(n):
    on = aaa[i]
    if on[1] <= 0:
        continue
    else:
        co += on[1]
        for j in range(i+1,n):
            if aaa[j][0] <= lll[i][1]:
                aaa[j][1] -= on[1]
            else:
                break
        aaa[i][1] = 0

print(co)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n, d, a = map(int,input().split())
hps=0
bomb=0
xlist=[]
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    xhlist.append([x, h])
    xlist.append(x)
    hps+=h

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    hani=bisect.bisect_right(xlist, pos+d)
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            xhlist[now+i][1]-=atk
            if xhlist[now+i][1]<=0 and swit==0:
                tasu+=1
            elif swit==0:
                swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    tX,tH=map(int,input().split())
    if tX in monster:
        monster[tX]=max(monster[tX],tH)
    else:
        monster[tX]=tH

monster_key=list(monster.keys())
monster_key.sort()

count=0

for x in monster_key:
    if monster[x]<=0:
        continue
    tmp=x+D
    kai=math.ceil(monster[x]/A)
    for k in monster:
        if k<=tmp+D:
            monster[k]-=A*kai
    count+=kai

print(count)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(N):
    x, h = monsters[i]
    if h <= 0:
        continue
    bomb = (h+A-1) // A
    damage = bomb * A
    right = x + 2*D
    for j in range(i+1, N):
        if monsters[j][0] > right:
            break
        monsters[j][1] -= damage
    ans += bomb
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [self.id]*(2*self.N0)
        self.fun = fun
 
    def update(self, l, r, val):#[l, r)をvalで更新
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1 :
                self.data[l] = self.fun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r-1] = self.fun(self.data[r-1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += self.N0
        ret = self.data[i]
        while i > 0 :
            i //= 2
            ret = self.fun(ret, self.data[i])
        return ret
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
S = SegmentTree(N, 0, lambda x, y:x+y)
ans = 0
from bisect import bisect
for i in range(N):
    x, h = XH[i]
    c = S.query(i)
    h-=c
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect(XH, [x+D*2+1, -1])
    S.update(i, j, n*A)
    ans+=n
print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import numpy as np
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x: x[0])
XH = np.array(XH).astype(np.int64)

X = XH[:, 0]
H = XH[:, 1]

ans = 0

for i in range(N):
    if H[i] <= 0:
        continue
    pos = X[i]
    explode = (H[i] + A - 1) // A
    ex_range = (X >= pos) & (X <= pos+2*D)
    H[ex_range] -= explode*A

    ans += explode

print(ans)

Submission status: Time Limit Exceeded

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)

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

    tot = 0
    curr = 0
    while True:
        # Hが正であるうち、xが最も小さいxhを見つける O(N)
        flag = False
        for i in range(curr, N):
            if XH[i][1] > 0:
                flag = True
                break
        if flag:
            curr = i+1
        else:
            break
        # できるだけ多くを巻き込むようにバクダンを使う。 x ~ x+2D
        x, h = XH[i]
        tot += -(-h//A)
        damage = A*(-(-h//A))
        # 巻き込むモンスターは i ~ jまで
        j = bisect_left(XH, (x+2*D+1, 0))
        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: Time Limit Exceeded

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

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

enemys.sort()

bomb_start_index = 0
bomb_last_index = 0

ans = 0

while N > bomb_start_index:

    while N > bomb_last_index and enemys[bomb_last_index][0] <= enemys[bomb_start_index][0] + 2 * D:
        bomb_last_index += 1

    bomb_times = (enemys[bomb_start_index][1] + A - 1) // A
    ans += bomb_times

    for i in range(bomb_start_index, bomb_last_index):
        enemys[i][1] -= A * bomb_times

    while N > bomb_start_index and enemys[bomb_start_index][1] <= 0:
        bomb_start_index += 1
    
    bomb_last_index = bomb_start_index

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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: Time Limit Exceeded

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))

st = LazySegmentTree(size=N, initial_values=H)
ans = 0
for l, r in lr:
    h = st.get(l, l + 1)
    if h > 0:
        cnt = (h + A - 1) // A
        st.add(l, r, -cnt * A)
        ans += cnt
print(ans)

Submission status: Time Limit Exceeded

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])

ans = 0
i = 0
while True:
    alive = True
    for j in range(i, N):
        x, h = XH[j]
        if h <= 0:
            continue
        i = j
        pos = x
        explode = (h + A - 1) // A
        break
    else:
        alive = False
        break

    if not alive:
        break

    for j in range(i, N):
        x, _ = XH[j]
        if x <= pos+2 * D:
            XH[j][1] -= explode * A
        else:
            break
    ans += explode

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
dam_sum = 0
q = deque()
for i, (x, h) in enumerate(xh):
    while q and q[0][0] < x:
        ran, dam = q.popleft()
        dam_sum -= dam
    h -= dam_sum
    if h <= 0:
        continue 
    c = -(-h//a)
    ans += c
    dam_sum += c*a
    q.append((x+d*2, c*a))
print(ans)

Submission status: Accepted

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 ** 10 + 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)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        while len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import math

n, d, a = map(int, input().split())
xh = []

for _ in range(n):
    x, h = map(int, input().split())
    xh.append((x, h))
xh.sort(key=lambda x: x[0])
xs = [x[0] for x in xh]

ranges = []
for x in xs:
    ranges.append(bisect.bisect_right(xs, x + 2 * d))


# N: 処理する区間の長さ
N = 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()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
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


for i, (x, h) in enumerate(xh):
    update(i, i + 1, h)

ans = 0
for i in range(n):
    v = query(i, i + 1)
    if v > 0:
        t = math.ceil(v / a)
        ans += t
        update(i, ranges[i], -t * a)
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
左から見る，モンスターが生きているならそいつが左端ギリギリになる位置に爆弾投下
区間減算，座圧
"""
def main():
    ####################
    import sys
    class Lazysegtree():
        #必ず単位元に注意すること！queryで1点の値のみを抽出するような場合でも，単位元とsegfuncがあってないとダメ！！


        """RAQ
        外から使うのは，query，add,updateくらいか

        """
        def __init__(self, A, intv, initialize = True, segf = min):
            """
            Aが初期配列，intvが単位元,segfが評価関数
            """

            #区間は 1-indexed で管理
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.intv = intv
            self.segf = segf
            self.lazy = [0]*(2*self.N0)
            if initialize:
                self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [intv]*(2*self.N0)

        def _ascend(self, k):
            k = k >> 1
            c = k.bit_length()
            for j in range(c):
                idx = k >> j
                self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
                + self.lazy[idx]

        def _descend(self, k):
            k = k >> 1
            idx = 1
            c = k.bit_length()
            for j in range(1, c+1):
                idx = k >> (c - j)
                ax = self.lazy[idx]
                if not ax:
                    continue
                self.lazy[idx] = 0
                self.data[2*idx] += ax
                self.data[2*idx+1] += ax
                self.lazy[2*idx] += ax
                self.lazy[2*idx+1] += ax

        def update(self, k, x):
            #1点のデータの変更
            k = k + self.N0
            self.data[k] = x
            self._ascend(k)

        def query(self, l, r):
            #クエリ，[l,r)かな
            L = l+self.N0
            R = r+self.N0
            Li = L//(L & -L)
            Ri = R//(R & -R)
            self._descend(Li)
            self._descend(Ri - 1)

            s = self.intv 
            t = self.intv 
            while L < R:
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                if L & 1:
                    s = self.segf(s, self.data[L])
                    L += 1
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        def add(self, l, r, x):
            #区間加算，[l,r)かな
            L = l+self.N0
            R = r+self.N0

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

            while L < R :
                if R & 1:
                    R -= 1
                    self.data[R] += x
                    self.lazy[R] += x
                if L & 1:
                    self.data[L] += x
                    self.lazy[L] += x
                    L += 1
                L >>= 1
                R >>= 1

            self._ascend(Li)
            self._ascend(Ri-1)

        #必ず単位元に注意すること！queryで1点の値のみを抽出するような場合でも，単位元とsegfuncがあってないとダメ！！


    ##########




    import bisect
    
    N,D,A=MI()
    X=[0]*N
    H=[0]*N
    for i in range(N):
        X[i],H[i]=MI()
    
    X,H=zip(*sorted(zip(X,H)))
    
    from collections import defaultdict
    dd = defaultdict(int)

    for i in range(N):
        dd[X[i]]=i
        
    ans=0
    inf=10**10
    seg=Lazysegtree(list(H),inf,segf=min)
    for i in range(N):
        h=seg.query(i,i+1)
        
        if h>0:
            cnt=(h+A-1)//A
            ans+=cnt
            l=i
            t=X[l]+2*D
            r=bisect.bisect_right(X,t)
            
            seg.add(l,r,-1*cnt*A)
            
    print(ans)
        
    
        
    

main()

Submission status: Accepted

Solution code:
"""
lazyseg使う方法とかもあるが、imos法使うのが簡単そう。
座標圧縮は必須。
"""
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()

coordinates = set()
for x,h in XH:
    coordinates.add(x)
    coordinates.add(x+2*D+1)

compress = {x:i for i,x in enumerate(sorted(coordinates))}

imos = [0]*(len(compress))
damage = 0
cur = 0
ans = 0
for x,h in XH:
    compX = compress[x]
    while cur <= compX:
        damage += imos[cur]
        cur += 1
    rest = h-damage
    if rest > 0:
        add = A*ceil(rest/A)
        ans += int(ceil(rest/A))
        imos[cur] += add
        right = compress[x+2*D+1]
        imos[right] -= add
print(ans)