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:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    while j < len(X) and X[j] < x + 2 * D + 1:
        j += 1
    damege[j] -= atk  # 効果切れを予約

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
# j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    damege[bisect_left(X, x + 2 * D + 1, lo=i)] -= atk  # 効果切れを予約

print(ans)

Submission status: Accepted

Solution code:
import bisect
from math import ceil
n,d,a=map(int,input().split())
XH=[list(map(int,input().split())) for i in range(n)]
X=[XH[i][0] for i in range(n)]
XH.sort(key=lambda y:y[0])
X.sort()
damage=[0]*(n+1)
ans=0
for i,(x,h) in enumerate(XH):
  damage[i]+=damage[i-1]
  h-=damage[i]
  if h<=0:
    continue
  cnt=ceil(h/a)
  ans+=cnt
  damage[i]+=a*cnt
  br=bisect.bisect_right(X,x+d*2)
  damage[br]-=a*cnt
print(ans)

Submission status: Accepted

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

xh.sort()
xs = [x for x, h in xh]

memo = [0 for _ in range(n)]

ans = 0

for j, (x, h) in enumerate(xh):
    memo[j] +=  memo[j-1]
    b = h - memo[j]
    if b > 0:
        c = (b + a - 1) // a
        memo[j] += c * a
        ans += c
        i = bisect.bisect_right(xs, x + 2 * d)
        if i < n:
            memo[i] -= c * a

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from queue import Queue
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
#%%
bound = [0]*N
idx = 0
right = 0
while idx<N:
    while right < N and (XH[right][0]-XH[idx][0])<=2*D:
        right += 1
    bound[idx] = right  
    idx += 1
def kiriage(n,m):
    return (n+(m-1))//m

heru = [0]*(N+1)
ans = 0
damage = 0
for i in range(N):
    damage -= heru[i]
    
    if XH[i][1]<=damage:
        continue
    cnt = kiriage(XH[i][1]-damage,A)
    ans += cnt
    damage += cnt*A
    heru[bound[i]] += cnt*A
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
damage = [0] * (N+2)
ans = 0
for i, [x, hp] in enumerate(monsters, 1):
    damage[i] += damage[i-1]
    if damage[i] >= hp: continue
    hp -= damage[i]
    j = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
    dam = attack * A
    # imos's method
    damage[i] += dam
    damage[j] -= dam
print(ans)

Submission status: Accepted

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

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

X=sorted(X,key=lambda x:x[0])
# lastX=X[-1][0] # 最後のモンスターの場所
damage=0 # 現在の爆発が与えられるダメージ
from collections import deque
bombs=deque() # 爆弾が切れるタイミング
# [位置、効力]
ans=0
for i in range(len(X)):
  x=X[i][0]
  h=X[i][1] # モンスターの体力
  # 爆発が途切れていないかを確認
  while bombs:
    b=bombs.popleft()
    if b[0]<x:
      damage-=b[1]
    else:
      bombs.appendleft(b)
      break
  h-=damage
  if h>0:
    turn=((h+A-1)//A)
    damage+=turn*A
    ans+=turn
    bombs.append([x+D,turn*A])
print(ans)

Submission status: Accepted

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

N, D, a = [int(x) for x in input().split()]
XH = []
for _ in range(N):
    XH.append([int(x) for x in input().split()])
XH.sort()

#####segfunc######
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

#入力
n = N
A = [0] * N

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

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

#init
init(A)

import bisect

X = []
H = []
for i in XH:
    X.append(i[0])
    H.append(i[1])
ans = 0
for i in range(N):
    x, h = X[i], H[i]
    idx_left = bisect.bisect_left(X, x - 2 * D)
    idx_right = i
    tmp = query(idx_left, idx_right)
    if tmp < h:
        h -= tmp
        cnt = h // a + int(h % a != 0)
        ans += cnt
        update(i, a * cnt)
print(ans)

Submission status: Accepted

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

N, D, a = [int(x) for x in input().split()]
XH = []
for _ in range(N):
    XH.append([int(x) for x in input().split()])
XH.sort()

#####segfunc######
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

#入力
n = N
A = [0] * N

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

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

#init
init(A)

import bisect

X = []
H = []
for i in XH:
    X.append(i[0])
    H.append(i[1])
ans = 0
for i in range(N):
    x, h = X[i], H[i]
    idx_left = bisect.bisect_left(X, x - 2 * D)
    idx_right = bisect.bisect_right(X, x + 2 * D)
    tmp = query(idx_left, idx_right)
    if tmp < h:
        h -= tmp
        cnt = h // a + int(h % a != 0)
        ans += cnt
        update(i, a * cnt)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
N,D,A=map(int,input().split())
X,H=[None]*N,{}
for i in range(N):
  X[i],H[X[i]]=map(int,input().split())
X.sort()
f=[0]*N
ans=i=0
while i<N:
  if i>0:
    f[i]+=f[i-1]
  if f[i]*A<H[X[i]]:
    k=-((f[i]*A-H[X[i]])//A)
    f[i]+=k
    ans+=k
    j=bisect_right(X,X[i]+(D<<1))
    if j<N:
      f[j]-=k
  i+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil

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

q = deque()
ans = 0
count = 0
total = 0
for x,h in xh:
    while q:
        if q[0][0] < x:
            total -= q.popleft()[1]
        else:
            break
    
    if total < ceil(h/a):
        count = ceil(h/a)-total
        ans += count
        total += count
        q.append((x+2*d,count))

print(ans)

Submission status: Accepted

Solution code:
import math
import collections
N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q):
        if q[0][0] < x:
            t = q.popleft()
            c -= t[1]
        else:
            break
    h -= c*A
    k = math.ceil(max(h, 0) / A)
    ans += k
    c += k
    if k > 0:
        q.append((x+(2*D), k))
print(ans)

Submission status: Accepted

Solution code:
n,d,a=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
lim=[0]*n
pos=0
for i in range(n):
  while pos!=n-1:
    if arr[i][0]+2*d>=arr[pos+1][0]:
      pos+=1
    else:
      break
  lim[i]=pos
ans=0
damage=[0]*n
acum=0
pos=0
for i in range(n):
  while i>lim[pos]:
    acum-=damage[pos]
    pos+=1
    if pos==n:
      break
  ans+=max(0,(arr[i][1]-acum+(a-1))//a)
  damage[i]=a*max(0,(arr[i][1]-acum+(a-1))//a)
  acum+=damage[i]
print(ans)

Submission status: Accepted

Solution code:
#silver fox
n,d,a=map(int,input().split())
from collections import deque
import math
data=[]
for i in range(n):
    x,h=map(int,input().split())
    data.append((x,h))
data=sorted(data,key=lambda x:x[0])
#data を位置の順番にソートしておく
add=0
damage_sum=0
damage_map=deque([])
for i in range(n):
    if damage_map:
        while damage_map and damage_map[0][0]<data[i][0]:
            k=damage_map.popleft()
            damage_sum-=k[1]
            
    if damage_sum<data[i][1]:
        p=math.ceil((data[i][1]-damage_sum)/a)
        damage_sum+=p*a
        add+=p
        #少なくともp回の攻撃を加えなくてはならない
        damage_map.append((data[i][0]+2*d,p*a))
        #data[i][0]+2*dのところまではp*aのダメージがプラスとして加算される
print(add)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[float('inf')]*n,[0]*(n+1)

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[i]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama[i+1]=tmp
    tama[i+1]+=tama[i]
    r[i]=x+2*d

print(tama[-1])
# print(r)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[float('inf')]*n,[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r[i]=x+2*d

print(tama[-1])
# print(r)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[],[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r.append(x+2*d)

print(tama[-1])
# print(r)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
# xh=[list(map(int,input().split())) for i in range(n)]
xh=[]
for i in range(n):
    xh.append(list(map(int,input().split())))
xh.sort()
r,tama=[],[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r.append(x+2*d)

print(tama[-1])
# print(r)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[],[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r.append(x+2*d)

print(tama[-1])
# print(r)

Submission status: Accepted

Solution code:
# F - Silver Fox vs Monster

from math import ceil

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

# X座標の昇順に整列
xh.sort(key=lambda x: x[0])

bomb = 0
head = 0
accum = 0  # 破壊済みの体力
for i in range(n):
    while xh[head][0] < xh[i][0] - d - d:
        accum -= ceil(xh[head][1] / a) * a
        head += 1
    xh[i] = (xh[i][0], max(0, xh[i][1] - accum))
    b = ceil(xh[i][1] / a)
    bomb += b
    accum += b * a

print(bomb)

Submission status: Accepted

Solution code:
from math import * 
import sys
from collections import *
input = sys.stdin.readline

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

    t = 0
    q = deque([])
    
    ans = 0
    for X, H in XH:
        while q and q[0][0] < X-D:
            x, c = q.popleft()
            
            t -= c
        H -= A * t
        
        if H <= 0: continue 

        c = ceil(H/A)
        ans += c
        q.append((X+D, c))
        t += c   
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import * 
import sys
input = sys.stdin.readline

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

    t = 0
    q = []
    ans = 0
    for X, H in XH:
        while q and q[0][0] < X-D:
            x, c = q.pop(0)
            t -= c
        H -= A * t
        
        if H <= 0: continue 

        c = ceil(H/A)
        ans += c
        q.append((X+D, c))
        t += c   
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    # 期限切れの蓄積ダメージを削除
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

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

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

print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
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])

monster_x = []
monster_hp = []
for i in range(n):
    monster_x.append(xh[i][0])
    monster_hp.append(xh[i][1])

dist = 2 * d
ans = 0
damage = 0
cum_damage = [0] * (n + 1)
for i in range(n):
    cum_damage[i + 1] += cum_damage[i]
    damage = cum_damage[i + 1] * A
    if damage < monster_hp[i]:
        min_attack_num = math.ceil((monster_hp[i] - damage) / A) 
        index = bisect.bisect_right(monster_x, monster_x[i] + dist)
        cum_damage[i + 1] += min_attack_num
        if index < n:
            t = min(index + 1, n)
            cum_damage[t] -= min_attack_num
        ans += min_attack_num

print(ans)

Submission status: Accepted

Solution code:
import bisect
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
monster_hp = []
monster_x = []
for i in range(n):
    monster_hp.append(data[i][1])
    monster_x.append(data[i][0])
ans = 0
damage_range = [0 for i in range(n+1)]
for i in range(n):
    #step1 i体目のモンスターに入ってるダメージを計算。
    damage_range[i+1] += damage_range[i]
    damage = damage_range[i+1] * a
    if damage < monster_hp[i]:
        #もしこのモンスターが既に致死量でないなら,魔法を打つ必要がある
        min_requaired = (monster_hp[i] - damage + a - 1) // a
        index = bisect.bisect_right(monster_x, monster_x[i] + 2 * d)
        damage_range[i+1] += min_requaired
        if index < n:
            damage_range[min(index+1, n)] -= min_requaired
        ans += min_requaired
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,d,a = map(int,input().split())
attack = [0 for _ in range(n)]
event = []
for i in range(n):
  x,h = map(int,input().split())
  h = (h-1)//a+1
  event.append([x-d,0,h,i])
  event.append([x+d,1,h,i])
event.sort()
#print(event)
ans = 0
now = 0
for j in range(2*n):
  x,m,h,i = event[j]
  if m == 0:
    if h > now:
      attack[i] += h-now
      ans += h-now
      now = h
  else:
    now -= attack[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, d, a = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(n)]
XH.sort()
# X:座標、 C:倒すための必要爆発回数
XC = [[x, (h - 1) // a + 1] for x, h in XH]
      
q = deque([])
accum_dmg = 0
ans = 0

for x, c in XC:
  # q[-][0]は爆発が届く右端の座標
  # 爆発が届いていない地点に来たら累積ダメージを減らす
  while q and x > q[0][0]:
    _, dmg = q.popleft()
    accum_dmg -= dmg
    
  cnt = max(0, c - accum_dmg)
  ans += cnt
  accum_dmg += cnt
  
  if cnt:
    q.append([x + 2 * d, cnt])
print(ans)

Submission status: Accepted

Solution code:
import sys
import socket
from collections import deque


if socket.gethostname() in ['N551J', 'F551C']:
    in_file = 'f1.in'
    in_file = 'after_contest_01.in'
    sys.stdin = open(in_file)


def read_int_list():
    return list(map(int, input().split()))


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


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = map(list, zip(*pairs))

    res = 0
    damage = 0
    q = deque()
    for i in range(n):
        # print(i, damage, file=sys.stderr)
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.popleft()
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

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

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    if hp < 0:
        return 0
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)









"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

n, d, a = map(int, input().split())
mon = [list(map(int, input().split())) for _ in range(n)]
mon.sort(key=lambda x: x[0])
ref = [x for x, h in mon]
rem = [0] * (n + 1)
ans = 0
cur = 0
for i, (x, h) in enumerate(mon):
	cur -= rem[i]
	h = max(0, h - cur)
	t = a * (0 - -h // a)
	ans += 0 - -h // a
	cur += t
	rem[bisect_left(ref, x + 2 * d + 1)] += t
print(ans)

Submission status: Accepted

Solution code:
import math
from bisect import bisect_right  # クエリより真に大きい値が初めて現れるインデックスを教えてくれる
# 初めて爆弾が届かない範囲を記録しながら前から順に倒していく
N, D, A = map(int, input().split())  # N体のモンスター, 爆弾の範囲D, 爆弾の威力A
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, math.ceil(h/A)))
    X.append(x)
# 座標で昇順ソート
XH.sort()
X.sort()
# 前から倒していく
now = 0
ans = 0
T = [0]*(N+1)  # 爆弾の範囲が切れる場所を記録しておく
for i in range(N):
    x, h = XH[i]  # 今見ているモンスターの座標, 体力
    now -= T[i]  # そのモンスターに届いていない爆弾があるなら引く
    if now >= h:  # 今残っている爆弾だけで倒せるならcontinue
        continue
    else:
        ans += h - now  # 足りない分(h-now個)の爆弾を使う
        T[bisect_right(X, x+2*D)] += h - now  # 爆弾の範囲が切れる場所を記録しておく
        now = h  # 今影響が残っている爆弾の威力
print(ans)

Submission status: Accepted

Solution code:
n,d,a=[int(j) for j in input().split()]
xh=[[int(j) for j in input().split()] for i in range(n)]
xh.sort()
from collections import deque
q=deque()
ans=0
dmg=0
for x,h in xh:
    while q and q[0][0]<x:
        i,j=q.popleft()
        dmg-=j
    r=h-dmg
    if r<=0:
        continue
    p=-(-r//a)
    dmg+=p*a
    ans+=p
    q.append((x+2*d,p*a))
print(ans)

Submission status: Accepted

Solution code:
import math
from bisect import bisect_right
N, D, A = map(int, input().split())  # N体のモンスター, 爆弾の範囲D, 爆弾の威力A
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, math.ceil(h/A)))  # 座標と必要な爆弾の個数を格納する
    X.append(x)  # こっちは座標のみ, あとで座標を二分探索するときに使う
# 座標でソートする
XH.sort()
X.sort()
T = [0]*(N+1)
now = 0
ans = 0
for i in range(N):
    x, h = XH[i]
    now -= T[i]
    if now >= h:
        continue
    else:
        T[bisect_right(X, x+D*2)] += h - now
        ans += h - now
        now = h
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

monsters.sort()
d = deque()
ans = 0
damage = 0
for x, h in monsters:
    while d:
        if d[0][0] >= x - D:
            break
        _, power = d.popleft()
        damage -= power
    h -= damage
    if h <= 0:
        continue
    attack = (h - 1) // A + 1
    
    ans += attack
    d.append((x + D, attack * A))
    damage += attack * A
print(ans)

Submission status: Accepted

Solution code:
import math

n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
q = []
index = 0
ans = 0
dmg = 0
for i in range(n):
    while index < len(q) and q[index][0] < l[i][0]:
        dmg -= q[index][1]
        index += 1
    if l[i][1] > dmg:
        times = (l[i][1]-dmg)//a if (l[i][1]-dmg)%a == 0 else (l[i][1]-dmg)//a+1
        ans += times
        q.append((l[i][0]+2*d, a*times))
        dmg += a*times
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

q = deque()

s = 0
ans = 0

for i in range(N):
  x = XH[i][0]
  h = XH[i][1]
  while len(q) > 0:
    elm = q.popleft()
    if x <= elm[0]:
      q.appendleft(elm)
      break
    else:
      s -= elm[1]
  h -= s
  c = max(0, (h + A - 1) // A)
  ans += c
  s += c * A
  q.append((x + 2*D, c*A))
  
print(ans)

Submission status: Accepted

Solution code:
class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        """
        N:要素数
        func:計算式(maxなど)
        intv:単位元
        """
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + 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):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小(大)値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

#####

import bisect
import sys
input = sys.stdin.readline




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

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

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]


sst=StarrySkyTree(N+1, max, 0)

for i in range(N):
    sst.update(i,i+1,XH[i][1])
    
cnt=0
for i in range(N):
    h=sst.query(i,i+1)
    if h>0:
        r=bisect.bisect_right(X,X[i]+2*D)
        bomb=(h+A-1)//A#切り上げ
        sst.update(i,r,-1*bomb*A)
        cnt+=bomb
        
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
n, d, a = map(int, input().split())
dat = [list(map(int, input().split())) for _ in range(n)]
dat.sort()
use = deque()
give = 0
cnt = 0
for i in range(n):
    # dat[i][0]未満のuse消費
    while len(use) > 0 and use[0][0] < dat[i][0]:
        give -= use.popleft()[1]
    # dat[i][1] - giveが残HPなので、[dat[i][0], dat[i][0]+2d]に爆撃して殺す
    if dat[i][1] - give > 0:
        add = (dat[i][1] - give + a - 1) // a   # add回爆撃
        cnt += add
        use.append([dat[i][0] + 2 * d, add * a])
        give += add * a
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import *
from heapq import *

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda k: k[0])
pq = []
ans = 0
S = 0

for i in range(N):
    X, H = XH[i]
    
    while len(pq)>0:
        if pq[0][0]<X:
            t = heappop(pq)
            S -= t[1]
        else:
            break
        
    H -= S
    
    if H<=0:
        continue
    
    cnt = (H+A-1)//A
    ans += cnt
    heappush(pq, (X+2*D, cnt*A))
    S += cnt*A

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,d,a = map(int, input().split())
ls = [list(map(int, input().split())) for i in range(n)]
ls.sort(key=lambda x:x[0])

q=deque()
ans=0
tot=0
for i in range(n):
    x=ls[i][0]
    h=ls[i][1]
    while q and q[0][0]<x:
        tot-=q[0][1]
        q.popleft()
    h-=tot
    if h>0:
        num = (h+a-1)//a
        ans+=num
        tot+=num*a
        q.append([x+2*d,num*a])

print(ans)