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:
class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r: s.down(r)
    ans = s.inf
    k, kl, kr = 0, 0, s.N - 1
    S = [[k, kl, kr]]
    while S:
      k, kl, kr = S.pop()
      if l <= kl and r >= kr: ans = s.do(ans, s.T[k])
      else:
        t = (kl + kr) // 2
        if l > t: S.append([2 * k + 2, t + 1,kr])
        elif r < t + 1: S.append([2 * k + 1, kl, t])
        else: 
          S.append([2 * k + 2, t + 1,kr])
          S.append([2 * k + 1, kl, t])
    return ans
  def add(s, l, r, v):
    k, kl, kr = 0, 0, s.N - 1
    S = [[k, kl, kr]]
    while S:
      k, kl, kr = S.pop()
      if l <= kl and kr <= r:
        s.D[k] += v
        continue
      if k >= s.N: continue
      if kl <= r and l <= kr:
        t = (kl + kr) // 2
        S.append([2 * k + 1, kl, t])
        S.append([2 * k + 2, t + 1, kr])

  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,d,a = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()

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

def init(init_val): #渡されたリストでsegを初期化
    #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): #segの要素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): #区間[p,q)での、segfuncに準じた値を返す
    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

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

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


#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        if (lst1[i][1]-r)/a%1==0:
            need = (lst1[i][1]-r)//a
        else:
            need = (lst1[i][1]-r)//a+1
        ans += need
        update(i,need*a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

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

Solution code:
import bisect
import math

#####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(math.ceil(h/a), 0)
    ans += count
    update(i, count * a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, d, a = map(int, input().split())
XH = np.array([tuple(map(int,input().split())) for _ in range(n)],dtype="int")
xh = XH[np.argsort(XH[:, 0])]
ans = 0
for i in range(n):
    xi, hi = xh[i, 0], xh[i, 1]
    if hi > 0:
        an = hi // a + int(hi % a != 0)
        xh[i:np.searchsorted(xh[:, 0], xi+2*d, side="right"), 1] -= an * a
        ans += int(an) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, d, a = map(int, input().split())
XH = np.array([tuple(map(int,input().split())) for _ in range(n)],dtype="int")
xh = XH[np.argsort(XH[:, 0])]
from bisect import bisect
def main():
    ans = 0
    for i in range(n):
        xi, hi = xh[i, 0], xh[i, 1]
        if hi > 0:
            an = hi // a + int(hi % a != 0)
            xh[i:bisect(xh[:, 0], xi+2*d), 1] -= an * a
            # xh[:, 1][xh[:, 0] < xi+2*d+1] -= an * a
            ans += int(an) 
    print(ans)
main()

Submission status: Time Limit Exceeded

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

"""

3 3 2
9 2
1 2
5 4
ans 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
ans 5

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000
ans 3000000000
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input
import numpy as np
n, d, a = map(int, input().split())
XH = np.array([tuple(map(int,input().split())) for _ in range(n)],dtype="int")
xh = XH[np.argsort(XH[:, 0])]
from bisect import bisect
ans = 0
for i in range(n):
    xi, hi = xh[i, 0], xh[i, 1]
    if hi > 0:
        an = hi // a + int(hi % a != 0)
        xh[:bisect(xh[:, 0], xi+2*d), 1] -= an * a
        # xh[:, 1][xh[:, 0] < xi+2*d+1] -= an * a
        ans += int(an) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
XH = []
for _ in range(N):
  X,H = map(int,input().split())
  XH.append([X,H])
XH.sort()
counter = 0
for item in XH:
  damage = item[1]
  counter += (item[1]+A-1)//A
  for piece in XH:
    if piece[0] <= item[0]+2*D and piece[1] != 0:
      piece[1] = max(0,piece[1]-damage)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
XH = []
for _ in range(N):
  X,H = map(int,input().split())
  XH.append([X,H])
XH.sort()
counter = 0
for item in XH:
  damage = item[1]
  counter += (item[1]+A-1)//A
  for piece in XH:
    if piece[0] <= item[0]+2*D:
      piece[1] = max(0,piece[1]-damage)
print(counter)

Submission status: Time Limit Exceeded

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

"""

3 3 2
9 2
1 2
5 4
ans 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
ans 5

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000
ans 3000000000
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
n, d, a = map(int, input().split())
XH = np.array([tuple(map(int, input().split())) for _ in range(n)], 
              dtype="int64")
xh = XH[np.argsort(XH[:, 0])]


ans = 0
for i in range(n):
    xi = xh[i, 0]
    hi = xh[i, 1]
    if hi > 0:
        an = hi // a + int(hi % a != 0)
        ai = an * a
        xj = xi + 2 * d
        xh[:, 1][xh[:, 0] < xj+1] -= ai
        ans += an
    
print(int(ans))

Submission status: Time Limit Exceeded

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

"""

3 3 2
9 2
1 2
5 4
ans 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
ans 5

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000
ans 3000000000
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
n, d, a = map(int, input().split())
XH = set([tuple(map(int, input().split())) for _ in range(n)])
xh = np.array(sorted(XH), dtype="int64")


ans = 0
for xi in xh[:, 0]:
    hi = xh[:, 1][xh[:, 0] == xi]
    if hi > 0:
        an = hi // a + int(hi % a != 0)  # roundup(hi, a)
        ai = an * a
        xj = xi + 2 * d
        xh[:, 1][xh[:, 0] < xj+1] -= ai
        ans += an
    
print(int(ans))

Submission status: Time Limit Exceeded

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

"""

3 3 2
9 2
1 2
5 4
ans 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
ans 5

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000
ans 3000000000
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


def roundup(n, d):
    if n % d:
        return n // d + 1
    else:
        return n // d


import numpy as np
n, d, a = map(int, input().split())
XH = set([tuple(map(int, input().split())) for _ in range(n)])
xh = np.array(sorted(XH), dtype="int64")


ans = 0
while np.any(xh[:, 1] > 0):
    xi = np.min(xh[:, 0][xh[:, 1] > 0])
    hi = xh[:, 1][xh[:, 0] == xi]
    an = roundup(hi, a)
    ai = an * a
    xj = xi + 2 * d
    xh[:, 1][xh[:, 0] < xj+1] -= ai
    ans += an

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    N, D, A = map(int, input().split())
    D *= 2
    XH = [(0, 0)] * N
    for i in range(N):
        x, h = map(int, input().split())
        XH[i] = (x, (h + A - 1) // A)
    XH = np.array(XH, dtype=[('a', int), ('b', int)])
    XH = np.sort(XH, order=['a', 'b'])

    ans = 0
    for i in range(N):
        x, h = XH[i]
        if h <= 0:
            continue
        ans += h

        for j in range(i + 1, N):
            nx, nh = XH[j]
            if nx > x + D:
                break
            XH[j] = (nx, nh - h)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, D, A = map(int, input().split())
    D *= 2
    XH = [(0, 0)] * N
    for i in range(N):
        x, h = map(int, input().split())
        XH[i] = (x, (h + A - 1) // A)
    XH.sort()

    ans = 0
    for i in range(N):
        x, h = XH[i]
        if h <= 0:
            continue
        ans += h

        for j in range(i + 1, N):
            nx, nh = XH[j]
            if nx > x + D:
                break
            XH[j] = (nx, nh - h)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
XH=[]
for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]

from bisect import bisect_right
import numpy as np
H=np.array(H)
ans=0
js=[bisect_right(X, 2*D+X[i]) for i in range(N)]
for i in range(N):
  if H[i]<=0:
    continue
  else:
    j=js[i]
    att=H[i]//A
    if H[i]%A!=0:
      att+=1
    H[i:j]-=att*A
    ans+=att
#print(H)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()

damege_sum = 0
ans = 0
q = []
for i in range(N):
    x, h = monsters[i]
    while q:
        if q[0][0] < x:
            damege_sum -= q[0][1]
            q.pop(0)
    h -= damege_sum
    if h > 0:
        hit = -(-h // A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
import bisect
N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[a, ceil(b/A)] for a, b in L]
L = sorted(L, key=lambda x: x[0])
seen = 0
cnt = 0
while seen < N:
    target = L[seen]
    if target[1] <= 0:
        seen += 1
        continue
    ind_right_most = bisect.bisect_right([v[0] for v in L], target[0]+2*D)
    tmp = target[1]
    for i in range(seen, ind_right_most):
        L[i][1] -= tmp
    seen += 1
    cnt += tmp
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np

n, d, a = map(int, input().split())
ml = [list(map(int, input().split())) for _ in range(n)]
ml = np.array(ml)
ml = ml[ml[:, 0].argsort(), :].T
for i in range(n):
    ml[1][i] = (ml[1][i] - 1) // a + 1
count = 0
for i in range(n):
    if ml[1][i] > 0:
        dmg = ml[1][i]
        count += dmg
        for j in range(i, n):
            if ml[0][j] > ml[0][i] + 2 * d:
                break
            ml[1][j] = max(ml[1][j] - dmg, 0)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np

n, d, a = map(int, input().split())
ml = [list(map(int, input().split())) for _ in range(n)]
ml = np.array(ml)
ml = ml[ml[:, 0].argsort(), :].T

for i in range(n):
    ml[1][i] = (ml[1][i] - 1) // a + 1
count = 0
for i in range(n):
    if ml[1][i] > 0:
        dmg = ml[1][i]
        count += dmg
        for j in range(i, n):
            if ml[0][j] <= ml[0][i] + 2 * d:
                ml[1][j] = max(ml[1][j] - dmg, 0)
print(count)

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 = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    v = XH[i][0] + 2 * D
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid

    ans += XH[i][1]
    done += XH[i][1]
    adjust[ok] += XH[i][1]

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 = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

def findi(v):
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid
    return ok

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    ans += XH[i][1]
    index = findi(XH[i][0] + D * 2)
    done += XH[i][1]
    adjust[index] += XH[i][1]

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])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[pos]-1)//A+1
  start, end=pos, bomb_j[pos]+1
  for i in range(start, end):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
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])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[i]-1)//A+1
  for i in range(pos, bomb_j[pos]+1):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect_right

def update(x, v):
  while x <= N:
    fw[x] += v
    x += x & -x

def s(x):
  res = 0
  while x:
    res += fw[x]
    x -= x & -x
  return res

def change(l, r, a):
  update(l, a)
  update(r + 1, -a)


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

fw = [0 for _ in range(N + 1)]

ans = 0
for i in range(N):
  h = s(i + 1) - s(0)
  if monsters[i][1] + h > 0:
    num_bomb = ceil((monsters[i][1] + h) / A)
    ans += num_bomb

    k = bisect_right(monsters, [monsters[i][0] + 2*D, 10**9])
    change(i + 1, k, -(num_bomb * A))
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect_right

def update(x, v):
  while x <= N:
    fw[x] += v
    x += x & -x

def s(x):
  res = 0
  while x:
    res += fw[x]
    x -= x & -x
  return res


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

fw = [0 for _ in range(N + 1)]

nxt = []
j = 0
for i in range(N):
  while j < N and monsters[j][0] <= monsters[i][0] + 2 * D:
    j += 1
  nxt.append(j)

ans = 0
for i in range(N):
  h = s(i + 1) - s(0)
  if monsters[i][1] + h > 0:
    num_bomb = ceil((monsters[i][1] + h) / A)
    ans += num_bomb

    k = nxt[i]
    update(i + 1, -(num_bomb * A))
    update(k + 1, num_bomb * A)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


N, D, A = map(int, input().split())
M = [tuple(map(int, x.split())) for x in sys.stdin.readlines()]
M.sort()

q = deque()
qt = deque()

ans = 0
for x, h in M:
    if len(q) == 0:
        bomb = (h + A - 1) // A
        q.append((x + 2 * D, bomb))
        ans += bomb
    else:
        while h > 0:
            d, bomb = q.popleft()
            if x <= d:
                h -= bomb * A
                qt.append((d, bomb))
            if h > 0 and len(q) == 0:
                bomb = (h + A - 1) // A
                h -= bomb * A
                qt.append((x + 2 * D, bomb))
                ans += bomb
        while len(qt) > 0:
            q.appendleft(qt.pop())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

N,D,A=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
List.sort()
arr = []
Harr = [0] * (N+1)

for i in range(N):
  X = List[i][0]
  H = List[i][1]
  H = math.ceil(H / A)
  arr .append(X)
  Harr[i] = H
  
cnt = 0
for i in range(len(arr)):
  while Harr[i] > 0:
    a = bisect.bisect_right(arr, int(arr[i])+2*D)
    T = int(Harr[i])
    for j in range((a-i)):
      Harr[i+j] -= int(T)
    cnt += int(T)
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

  XH.sort()
  H = [XH[i][1] for i in range(N)]

  T = segTree(N)
  T.set(H)

  p = 0
  ans = 0
  for i in range(N):
    for j in range(p + 1, N):
      if XH[j][0] > XH[i][0] + D * 2:
        p = j - 1
        break
      else:
        p = N - 1
    t = (T.get(i, i) - 1) // A + 1
    if t <= 0: continue
    ans += t
    T.add(i, p, -t * A)

  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = float("inf")
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1
  
N, D, A = list(map(int, input().split()))
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)