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:
def main():
  import sys
  from collections import deque
  from operator import itemgetter
  
  b = sys.stdin.buffer
  N,D,A = map(int, b.readline().split())
  m = map(int, b.read().split())
  ans = 0
  Q = deque()
  d = 0
  for x,h in sorted(zip(m,m), key=itemgetter(0)):
    while Q and Q[0][0] < x:
      _,d_ = Q.popleft()
      d += d_
    h = h+d
    if h <= 0: continue
    n = -(-h // A)
    d -= n * A
    ans += n
    Q.append((x+2*D,n * A))

  print(ans)
  
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            pl()
            b-=ql()
        h-=b
        t=-(-h//a)
        if t>0:
            s+=t
            t*=a
            b+=t
            pa(x+d+d)
            qa(t)
    print(s)
main()

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()
que = deque()
ans = 0
atk = 0
for x, h in xh:
    while que and que[0][0] <= x:
        atk -= que.popleft()[1]
    h -= a*atk
    if h <= 0:
        continue
    count = -(-h//a)
    ans += count
    atk += count
    que.append((x+2*d+1, count))
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            pl()
            b-=ql()
        h-=b
        t=0--h//a
        if t>0:
            s+=t
            b+=t*a
            pa(x+d+d)
            qa(t*a)
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    f,g=p.popleft,q.popleft
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            f()
            b-=g()
        h-=b
        t=0--h//a
        if t>0:
            s+=t
            b+=t*a
            p+=x+d+d,
            q+=t*a,
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=b=0
    for i,(x,h)in enumerate(z):
        c[i]+=b
        b=c[i]
        h-=b
        t=-h//a
        if t<0:
            b-=t*a
            c[bisect(y,x+d+d)]+=t*a
            s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
def main():
    def bisect(a,x):
        ok=len(a)
        ng=-1
        while ok-ng>1:
            mid=(ok+ng)//2
            if a[mid]>x:ok=mid
            else:ng=mid
        return ok
    import sys
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(zip(m,m),key=itemgetter(0))
    y=[x for x,_ in z]
    s=b=0
    for i,(x,h)in enumerate(z):
        c[i]+=b
        b=c[i]
        h-=b
        t=-h//a
        if t<0:
            b-=t*a
            c[bisect(y,x+d+d)]+=t*a
            s-=t
    print(s)
main()

Submission status: Accepted

Solution code:
import math
from operator import itemgetter
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=tuple(map(int,input().split()))
  l.append(k)
l.sort(key=itemgetter(0))
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Accepted

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

n,d,a=LI()
for i in range(n):
    x,h=LI()
    m.append((x,h))

m.sort(key=lambda x:x[0])
dm=0
q=deque()

for i in range(n):
    x,h=m[i]
    while q:
        if x>q[0][0]:
            y,c=q.popleft()
            dm-=c*a
        else:
            break

    if h>dm:
        c=(h-dm+a-1)//a
        dm+=c*a
        ans+=c
        q.append((x+2*d,c))

print(ans)

Submission status: Accepted

Solution code:
#テストケース追加と聞いたのでテスト
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:
        #ms[i][1]-=tmp　二回引いてるわ
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

Submission status: Accepted

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

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N+1, int)
answer = 0
power = 0
for i in range(N):
    power -= damage[i]
    J = (H[i]-1+A)//A
    if J <= power:
        continue
    else:
        a = bi.bisect_right(X, X[i]+2*D)
        damage[a] += J - power
        answer += J-power
        power = J
 
print(answer)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
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
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
imos=[0]*(n+1)
x=[]
for i in range(n):
  x.append(xh[i][0])
ans,cnt=0,0
for i in range(n):
  cnt+=imos[i]
  hp=xh[i][1]-cnt*a
  if hp>0:
    cnt+=ceil(hp/a)
    ans+=ceil(hp/a)
    imos[bisect_right(x,x[i]+2*d)]-=ceil(hp/a)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

#BinaryIndexedTree
def bit_add(i,w):
    x = i+1
    while x <= n:
        bit[x-1] += w
        x += x & -x
    return

def bit_sum(i):
    res = 0
    x = i+1
    while x > 0:
        res += bit[x-1]
        x -= x & -x
    return res

n,d,a = LI()
bit = [0]*(n+1)
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,_ in xh]
lst = []
for i in range(n):
    x,h = xh[i]
    r = br(X,x+2*d)
    lst.append((i,h,r))

ans = 0
for i,h,r in lst:
    tmp = max(0,math.ceil((h - bit_sum(i))/a))
    ans += tmp
    bit_add(r,-tmp*a)
    bit_add(i,tmp*a)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def bit_add(i,w):
    x = i+1
    while x <= n:
        bit[x-1] += w
        x += x & -x
    return

def bit_sum(i):
    res = 0
    x = i+1
    while x > 0:
        res += bit[x-1]
        x -= x & -x
    return res

n,d,a = LI()
bit = [0]*(n+1)
xh = [LI() for _ in range(n)]
xh.sort()
X = [x for x,_ in xh]
lst = []
for x,h in xh:
    r = br(X,x+2*d)
    lst.append((x,h,r))

ans = 0
for i in range(n):
    x,h,r = lst[i]
    tmp = max(0,math.ceil((h - bit_sum(i))/a))
    ans += tmp
    bit_add(r,-tmp*a)
    bit_add(i,tmp*a)
print(ans)

Submission status: Accepted

Solution code:
import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)

Submission status: Accepted

Solution code:
from collections import deque

N, D, A, *XH = map(int, open(0).read().split())

ans = 0
Q = deque()
damage = 0
for x, h in sorted(zip(*[iter(XH)] * 2)):

    while Q and Q[0][0] < x:
        v, d = Q.popleft()
        damage -= d

    h -= damage
    if h <= 0:
        continue

    n = -(-h // A)

    damage += A * n
    ans += n

    Q.append((x + 2 * D, A * n))

print(ans)

Submission status: Accepted

Solution code:

from heapq import heappush, heappop

N, D, A, *XH = map(int, open(0).read().split())

XH = sorted(zip(*[iter(XH)] * 2))

ans = 0
Q = []
damage = 0
for x, h in XH:

    while Q:
        v, d = Q[0]
        if v >= x:
            break
        v, d = heappop(Q)
        damage -= d

    h -= damage
    if h <= 0:
        continue

    n = -(-h // A)

    damage += A * n
    ans += n

    heappush(Q, (x + 2 * D, A * n))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

# process
XH.sort()
#print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
#        print("x,h,dam: {},{},{}".format(x,h,dam))
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
#    print("x,h,dam,ans,dq: {},{},{},{},{}".format(x,h,dam,ans,dq))
    
# output
print(ans)

Submission status: Accepted

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

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

def bisect(x):
    i_min=0
    i_max=n
    while i_min<i_max:
        i = (i_min+i_max)//2
        if xh[i][0]<=x:
            i_min = i+1
        else:
            i_max = i
    return i_min

ans = 0
accu = 0
out = [0]*(n+1)
for i, (x, h) in enumerate(xh):
    accu -= out[i]
    hp = h-accu
    if hp<=0:
        continue
    accu += hp
    ans += hp
    out[bisect(x+2*d)] += hp 
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    R = [0] * (N * 2)
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append((x, h))
        XH.append((x + 2 * D + 1, -float("inf")))
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 1))

    ans = 0
    ruiseki = 0

    for i in range(N * 2):
        x, h = XH[i]
        if h != -float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == -float("inf"):
                    R[nx] -= tmpruiseki
                else:
                    R[nx + 1] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += R[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,d,a = map(int,input().split())
monsters = [tuple(map(int,input().split())) for _ in range(n)]
monsters.sort()

# 各モンスターを倒すためにおこなった攻撃回数を記録する
# atk_count[1]が2の場合、x2番目のモンスターに対して2回攻撃をおこなったことを意味する
atk_count = [0]*n
atk_count_sum = 0
l = 0 # 左端
for i in range(n):
    x = monsters[i][0]
    h = monsters[i][1]
    # 尺取り法
    while monsters[l][0] + 2*d < x:
        atk_count_sum -= atk_count[l]
        l += 1
    # 既に受けているダメージ
    al = atk_count_sum * a
    h = h - al
    if h > 0:
        atk_count[i] = -(-h//a)
    atk_count_sum += atk_count[i]
print(sum(atk_count))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import deque

def main():
  n, d, a = map(int, input().strip().split())
  XsHs = [list(map(int, input().strip().split())) for _ in range(n)]
  XsHs.sort(key = lambda x:x[0])

  queue = deque()
  total = 0
  ans = 0
  for x, h in XsHs:
    while queue:
      if queue[0][0] < x:
        total -= queue[0][1]
        queue.popleft()
      else:
        break
    h -= total
    if h > 0:
      num = (h+a-1)//a
      ans += num
      total += (num*a)
      queue.append((x+(2*d), num*a))
  print(ans)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
x = []
for X,h in xh:
  x.append(X)
ans = 0
attack_start = [i for i in range(N)]
now = 0
cumsum = [0] * (N+1)
for L,(X,H) in enumerate(xh):
  R = bisect.bisect_right(x,X+2*d)
  for i in range(now,R):
    attack_start[i] = L
  now = R
  damage = (cumsum[L] - cumsum[attack_start[L]]) * a
  attack_time = max(0,math.ceil((H - damage) / a))
  ans += attack_time
  cumsum[L+1] = ans
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

n, d, a = list(map(int, input().split()))
xh = []
for line in sys.stdin:
    x, h = map(int, line.split())
    xh.append((x, 0, h))
heapify(xh)
atk_cnt = 0
ans = 0
while xh:
    x, t, h = heappop(xh)
    if t == 0:
        if atk_cnt * a >= h:
            continue
        remain = h - atk_cnt * a
        new_atk = (remain - 1) // a + 1
        heappush(xh, (x + 2 * d, 1, new_atk))
        ans += new_atk
        atk_cnt += new_atk
    else:
        atk_cnt -= h
print(ans)

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] # 最後のモンスターの場所
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.buffer.readline
from operator import itemgetter
from collections import deque

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        c = -(-dam//A)
        count += c
        aldam += c*A
        q.append((now+2*D,c*A))

    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import math
import sys
input = sys.stdin.readline
#####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

#####単位元######
ide_ele = 0
#input
data = []
n, d, a = map(int, input().split())
x_point = []
for i in range(n):
    x, h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
x_point.sort()
data.sort()
##初期化
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
ans = 0
for i in range(n):
    x, h = data[i]
    index = bisect.bisect_left(x_point, x - 2*d)
    sum_damage = query(index, i)
    h -= sum_damage
    count = max(((h+a-1)//a), 0)
    ans += count
    update(i, count * a)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Submission status: Accepted

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

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

N,d,a=LI()

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

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

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

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

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

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

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

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

show_flg=False
show_flg=True

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

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

#    show(j,H[j],dm,(j,r),c)
#    show('data',data)
    
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(key=lambda x:x[0])
total=0
q=deque()
ans=0

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 
def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]
 
# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]
 
# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]
 
n,d,a = get_nums_l()
lines = sys.stdin.readlines()
monsters = [ tuple(map(int, s.split(" "))) for s in lines ]
monsters.sort(key=lambda m: m[0])
 
ans = (monsters[0][1] + a - 1)//a
areas = [(monsters[0][0] + 2*d, ans*a)]
sum_ = ans*a
area_cursol = 0
for i in range(1, len(monsters)):
    m = monsters[i]
    x = m[0]
    h = m[1]
 
 
    while area_cursol < len(areas) and x > areas[area_cursol][0]:
        sum_ -= areas[area_cursol][1]
        area_cursol += 1
 
    if sum_ < h:
        # ボムつかう
        nokori = h-sum_
        kaisuu = (nokori+a-1)//a
        sum_ += kaisuu*a
        areas.append((x+2*d, kaisuu*a))
        ans += kaisuu
 
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:
def f_silver_fox_vs_monster():
    # 参考: https://atcoder.jp/contests/abc153/submissions/9773604
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N, D, A = [int(i) for i in input().split()]
    Monsters = sorted([[int(i) for i in input().split()] for j in range(N)])

    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """array[1] から array[index] までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """array[index] に value を加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    position = [row[0] for row in Monsters]
    hit_point = [row[1] for row in Monsters]
    # [k]: 左から k 番目の敵を爆発の左端で攻撃したときに届く右端の敵のインデックス
    pos_right = [bisect_right(position, pos + 2 * D) for pos in position]

    ans = 0
    bomb_damage = BIT(N + 1)  # bomb_damage.sum(k): 左から k 番目の敵に与えた累計ダメージ
    for i in range(N):
        hp, damage, right = hit_point[i], bomb_damage.sum(i + 1), pos_right[i]
        if hp - damage > 0:
            num_defeat = (hp - damage + A - 1) // A  # 注目中の敵を倒すのに必要な爆発回数
            ans += num_defeat
            bomb_damage.add(i + 1, num_defeat * A)
            # ここから右の敵はダメージが通っていないことを反映
            bomb_damage.add(right + 1, -num_defeat * A)
    return ans

print(f_silver_fox_vs_monster())