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:
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)
import math

c=0
while B:
    x,h=heappop(B)
    sup=x+2*D
    bomb=math.ceil(h/A)
    temp=[]
    c+=bomb
    while B:
        X,H=heappop(B)
        if X<=sup:
            H=max(0,H-A*bomb)
            if H>0:
                temp.append((X,H))
        else:
            temp.append((X,H))
            break
    for t in temp:
        heappush(B,t)
print(c)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import bisect
  N, D, A = map(int, input().split())
  d = list()
  X = list()
  for i in range(N):
    d.append(list(map(int, input().split())))
  d.sort()
  for i in range(N):
    X.append(d[i][0])

  ans = 0
  i = 0
  while(i < N):
    if(d[i][1] <= 0):
      i += 1
    else:
      s = X[i]
      j = bisect.bisect_right(X, s+2*D)
      t = (d[i][1]-1)//A + 1
      ans += t
      for k in range(i, j):
        d[k][1] -= t*A
      i += 1
  print(ans)

if __name__ == '__main__': 
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import bisect
  N, D, A = map(int, input().split())
  d = list()
  X = list()
  H = list()
  for i in range(N):
    d.append(list(map(int, input().split())))
  d.sort()
  for i in range(N):
    X.append(d[i][0])
    H.append(d[i][1])

  ans = 0
  i = 0
  while(i < N):
    if(H[i] <= 0):
      i += 1
    else:
      s = X[i]
      j = bisect.bisect_right(X, s+2*D)
      t = (H[i]-1)//A + 1
      ans += t
      for k in range(i, j):
        H[k] -= t*A
      i += 1
  print(ans)

if __name__ == '__main__': 
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import bisect
  N, D, A = map(int, input().split())
  d = list()
  X = list()
  H = list()
  for i in range(N):
    d.append(list(map(int, input().split())))
  d.sort(key=lambda x: x[0])
  for i in range(N):
    X.append(d[i][0])
    H.append(d[i][1])

  ans = 0
  i = 0
  while(i < N):
    if(H[i] <= 0):
      i += 1
    else:
      s = X[i]
      j = bisect.bisect_right(X, s+2*D)
      t = (H[i]-1)//A + 1
      ans += t
      for k in range(i, j):
        H[k] -= t*A
      i += 1
  print(ans)

if __name__ == '__main__': 
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
  N, D, A = map(int, input().split())
  d = list()
  X = list()
  H = list()
  for i in range(N):
    d.append(list(map(int, input().split())))
  d.sort(key=lambda x: x[0])
  for i in range(N):
    X.append(d[i][0])
    H.append(d[i][1])

  ans = 0
  i = 0
  while(i < N):
    if(H[i] <= 0):
      i += 1
    else:
      s = X[i]
      j = bisect.bisect_right(X, s+2*D)
      t = (H[i]-1)//A + 1
      ans += t
      for k in range(i, j):
        H[k] -= t*A
      i += 1
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, D, A = map(int, input().split())
d = list()
X = list()
H = list()
for i in range(N):
  d.append(list(map(int, input().split())))
d.sort(key=lambda x: x[0])
for i in range(N):
  X.append(d[i][0])
  H.append(d[i][1])

ans = 0
i = 0
while(i < N):
  if(H[i] <= 0):
    i += 1
  else:
    s = X[i]
    
    j = bisect.bisect_right(X, s+2*D)
    
    t = (H[i]-1)//A + 1
    ans += t
    for k in range(i, j):
      H[k] -= t*A
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
d = list()
for i in range(N):
  d.append(list(map(int, input().split())))
d.sort(key=lambda x: x[0])
#print(d)

ans = 0
i = 0
while(i < N):
  if(d[i][1] <= 0):
    i += 1
  else:
    s = d[i][0]
    L = list()
    j = i
    while(j < N):
      if(d[j][0] > s + 2*D):
        break
      L.append(j)
      j += 1
    #print(L)
    t = (d[i][1]-1)//A + 1
    ans += t
    for j in L:
      d[j][1] -= t*A
    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])

target = 0
cnt = 0
while target < n:
    x, h = xh[target]
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    atk_dmg = a * atk_cnt
    cnt += atk_cnt
    for i in range(target, n):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= atk_dmg
    while xh[target][1] < 1:
        target += 1
        if target >= n:
            break

print(cnt)

Submission status: Time Limit Exceeded

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])
xh = deque(xh)

cnt = 0
while xh:
    x, h = xh.popleft()
    if h < 1:
        continue
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(len(xh)):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt

print(cnt)

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

target = 0
cnt = 0
while target < n:
    x, h = xh[target]
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(target, n):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt
        if xh[i][1] < 1 and i == target+1:
            target += 1
    # while xh[target][1] < 1:
    #     target += 1
    #     if target >= n:
    #         break

print(cnt)

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

target = 0
cnt = 0
while target < n:
    x, h = xh[target]
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(target, n):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt
    while xh[target][1] < 1:
        target += 1
        if target >= n:
            break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

monsters = []
for i in range(N):
    X, H =map(int,input().split())
    monsters.append([X,H])

monsters = sorted(monsters)

id = 0
ans = 0

damage = [0 for i in range(N)]

while id < N:
    if id > 0: damage[id] += damage[id-1]
    nowX, nowH = monsters[id][0], monsters[id][1]
    nowH -= damage[id]

    if nowH > 0:
        damage[id] += A * ((nowH + A - 1) // A)

        right = bisect.bisect_left(monsters, [nowX+2*D+1,0])
        if right < N:
            damage[right] -= A * ((nowH + A - 1) // A)

        ans += (nowH + A -1) // A

    id += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    N,D,A=map(int,input().split())
    XH=[list(map(int,input().split())) for _ in range(N)]
    XH.sort()
    for i in range(N):
        XH[i][1]=-(-XH[i][1]//A)
    X=[x for x,a in XH]
    far=[0]*N
    for i in range(N):
        far[i]=bisect.bisect_right(X,X[i]+2*D)-1

    ans=0
    for i in range(N):
        x=XH[i][0]
        hp=XH[i][1]
        if hp<=0:
            continue
        #XH=[[xx,hh-hp] for xx,hh in XH[:far[i]+1]]+XH[far[i]+1:]
        for j in range(i,far[i]+1):
            XH[j][1]-=hp
        ans+=hp
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,D,A=map(int,input().split())
XH=[list(map(int,input().split())) for _ in range(N)]
XH.sort()
for i in range(N):
    XH[i][1]=-(-XH[i][1]//A)
X=[x for x,a in XH]
far=[0]*N
for i in range(N):
    far[i]=bisect.bisect_right(X,X[i]+2*D)-1

ans=0
for i in range(N):
    x=XH[i][0]
    hp=XH[i][1]
    if hp<=0:
        continue
    XH=[[xx,hh-hp] for xx,hh in XH[:far[i]+1]]+XH[far[i]+1:]
    #for j in range(i,far[i]+1):
    #    XH[j][1]-=hp
    ans+=hp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,D,A=map(int,input().split())
XH=[list(map(int,input().split())) for _ in range(N)]
XH.sort()
for i in range(N):
    XH[i][1]=-(-XH[i][1]//A)
X=[x for x,a in XH]
far=[0]*N
for i in range(N):
    far[i]=bisect.bisect_right(X,X[i]+2*D)-1

ans=0
for i in range(N):
    x=XH[i][0]
    hp=XH[i][1]
    if hp<=0:
        continue
    for j in range(i,far[i]+1):
        XH[j][1]-=hp
    ans+=hp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
N,d,a = map(int,readline().split())

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
  return get(data1,r-1)*(r-1)+get(data0,r-1)-get(data1,l-1)*(l-1)-get(data0,l-1)

xh = []
for _ in range(N):
    x,h = map(int,readline().split())
    xh.append((x,h))

xh = sorted(xh)
xl = [x for x,h in xh]

for i in range(N):
    add(i+1, i+2, xh[i][1])

import bisect,math

ans = 0
for i in range(N):
    hp = query(i + 1, i + 2)
    #print(data0,data1,hp)    
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect_right(xl, xl[i] + 2*d)
        add(i+1, idx+1, -damage)
print(ans)

Submission status: Time Limit Exceeded

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

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
  return get(data1,r-1)*(r-1)+get(data0,r-1)-get(data1,l-1)*(l-1)-get(data0,l-1)

xh = []
for _ in range(N):
    x,h = map(int,input().split())
    xh.append((x,h))

xh = sorted(xh)
xl = [x for x,h in xh]

for i in range(N):
    add(i+1, i+2, xh[i][1])

import bisect,math

ans = 0
for i in range(N):
    hp = query(i + 1, i + 2)
    #print(data0,data1,hp)    
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect_right(xl, xl[i] + 2*d)
        add(i+1, idx+1, -damage)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, collections
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = sorted([[int(_) for _ in input().split()] for _ in range(N)])
R = collections.deque([])
bombs_ = {}
for i, xh in enumerate(XH):
    R += [xh[0] + 2 * D + 1]
    while R[0] <= xh[0]:
        bombs_[R.popleft() - 2 * D - 1] = i
while R:
    bombs_[R.popleft() - 2 * D - 1] = i + 1
bombs = {}
for i, xh in enumerate(XH):
    bombs[i] = bombs_[XH[i][0]]


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def get_val(self, a):
        a += self.n
        res = self.dat[a]
        while a:
            if self.laz[a] != self.ei:
                res = self.g(res, self.laz[a])
            a //= 2
        return res

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#RMQ and RAQ
array = [(xh[1], 1) for xh in XH]
f = max
g = lambda a, b: (a[0] + a[1] * b, a[1])
h = lambda a, b: a + b
ti = (-float('inf'), 0)
ei = 0

LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
ans = 0
for i in range(N):
    this = LST.query(i, i + 1)[0]
    if this > 0:
        c = (this - 1) // A + 1
        ans += c
        LST.update(i, bombs[i], -A * c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = [int(_) for _ in input().split()]
XH = sorted([[int(_) for _ in input().split()] + [0] for _ in range(N)])
XH2 = [[xh[0] + 2 * D + 1, i, 1] for i, xh in enumerate(XH)]
XH3 = sorted(XH + XH2)
bombs = [-1] * N
for i, xh in enumerate(XH3):
    if xh[2]:
        bombs[xh[1]] = i - xh[1]


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def get_val(self, a):
        a += self.n
        res = self.dat[a]
        while a:
            if self.laz[a] != self.ei:
                res = self.g(res, self.laz[a])
            a //= 2
        return res

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#RMQ and RAQ
array = [(xh[1], 1) for xh in XH]
f = max
g = lambda a, b: (a[0] + a[1] * b, a[1])
h = lambda a, b: a + b
ti = (-float('inf'), 0)
ei = 0

LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
ans = 0
for i in range(N):
    this = LST.query(i, i + 1)[0]
    if this > 0:
        c = (this - 1) // A + 1
        ans += c
        LST.update(i, bombs[i], -A * c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
tree = make_tree(n)
for i in range(n):
    update(i, i, s[i][1])
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if s[i][0] + 2 * d >= s[j][0]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
x = [s[i][0] for i in range(n)]
tree = make_tree(n)
for i in range(n):
    update(i, i, s[i][1])
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if x[i] + 2 * d >= x[j]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import operator
import collections


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        k = 1
        l = 0
        r = n
        s = collections.deque()
        s.append((k, l, r))
        while s:
            k, l, r = s.pop()
            if r <= a or b <= l:
                continue
            if l == r - 1:
                self.st[k] += value
                continue
            if a <= l and r <= b:
                self.st[k] += value
                continue
            mid = (l + r) // 2
            s.append((k * 2, l, mid))
            s.append((k * 2 + 1, mid, r))

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import operator


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        k = 1
        l = 0
        r = n
        s = [(k, l, r)]
        while s:
            k, l, r = s.pop()
            if r <= a or b <= l:
                continue
            if l == r - 1:
                self.st[k] += value
                continue
            if a <= l and r <= b:
                self.st[k] += value
                continue
            mid = (l + r) // 2
            s.append((k * 2, l, mid))
            s.append((k * 2 + 1, mid, r))

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import operator


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st
    
    def _add(self, a, b, value, k, l, r):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return
        if l == r - 1:
            self.st[k] += value
            return
        if a <= l and r <= b:
            self.st[k] += value
            return
        mid = (l + r) // 2
        self._add(a, b, value, k * 2, l, mid)
        self._add(a, b, value, k * 2 + 1, mid, r)

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._add(a, b, value, k=1, l=0, r=n)

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = RAQ.from_array(H)

    ans = 0
    i = 0
    while i < N:
        x = XH[i][0]
        h = st.get(i)
        c = h // A + (h % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, x)
        ridx = bisect.bisect_left(X, x + 2 * D + 1)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        while i < N:
            h = st.get(i)
            if h > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

xh = [list(map(int,input().split())) for i in range(n)]
xh = sorted(xh, key=lambda x: x[0])

ans=0
for i in range(n):
    j=i
    tmp = max(-(-xh[i][1]//a),0)
    xh[i][1]=0
    for j in range(i+1,n):
        if xh[j][0]<=xh[i][0]+2*d:
            xh[j][1]-=a*tmp

    ans+=tmp

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])
count = 0
for i in range(n):
    while xh[i][1] > 0:
        r = xh[i][0] + d*2
        atack = -(-xh[i][1]//a)
        xh[i][1] = 0
        count += atack
        if i > n-1: continue
        j = i
        while True:
            j += 1
            if j<n and r>=xh[j][0]: xh[j][1] -= atack*a
            else: break
print(count)

Submission status: Time Limit Exceeded

Solution code:
N ,D, A = map(int,input().split())
XH = dict()
for _ in range(N):
    x, h = map(int,input().split())
    XH[x] = -(-h//A)
 
X = list(sorted(XH.keys()))
 
ans = 0
for i,x in enumerate(X):
    if XH[x] >0:
        d = XH[x]
        ans += XH[x]
 
        for x2 in X[i+1:i+2*D+1]:
            if x2 <= x+2*D:
                XH[x2] -= d
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N ,D, A = map(int,input().split())
XH = dict()
for _ in range(N):
    x, h = map(int,input().split())
    XH[x] = -(-h//A)

X = list(sorted(XH.keys()))

ans = 0
for i,x in enumerate(X):
    if XH[x] >0:
        d = XH[x]
        ans += XH[x]

        for x2 in X[i+1:i+2*D+1]:
            if x2 <= x+2*D:
                XH[x2] -= d
            else:
                break
print(ans)