Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

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

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import numpy

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]
        XH.pop(x)
        for x2 in X[i+1:]:
            if x2 <= x+2*D:
                XH[x2] -= d
            else:
                break
    else:
        XH.pop(x)

    if len(XH) == 0:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n, d, a = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n):
    x, h = map(int,input().split())
    e[i] = [x,h]
e.sort()
num = 0

for i in range(n):
    if e[i][1] > 0:
        k = math.ceil(e[i][1]/a)
        num += k
        for j in range(i+1,n):
            if e[j][0] <= e[i][0] + 2*d:
                e[j][1] -= k*a
            else:
                break

print(num)

Submission status: Time Limit Exceeded

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

def main():
  n,d,a = map(int,input().split())
  xx = []
  hh = []
  X = []
  H = []
  for _ in range(n):
    tmp = list(map(int,input().split()))
    xx.append(tmp[0])
    hh.append(tmp[1])

  k = zip(xx,hh)
  q = sorted(k)
  for xxx,hhh in q:
    X.append(xxx)
    H.append(hhh)
  X = tuple(X)
  ans = 0
  if d == 0:
    for i in range(n):
      ans += math.ceil(H[i]/a)
    print(ans)
    sys.exit()
  end = n-1
  while True:
    x = X[end] - d
    start = bisect_left(X,x-d)
    num = math.ceil(H[end] / a)
    ans += num
    H[end] = 0
    e = end
    end = start-1
    A = a * num
    for i in range(start,e):
      if H[i] <= 0:
        continue
      H[i] -= A
      if H[i] > 0:
        end = i
    if end < 0:
      break

  print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

def main():
  n,d,a = map(int,input().split())
  xx = []
  hh = []
  X = []
  H = []
  for _ in range(n):
    tmp = list(map(int,input().split()))
    xx.append(tmp[0])
    hh.append(tmp[1])

  k = zip(xx,hh)
  q = sorted(k)
  for xxx,hhh in q:
    X.append(xxx)
    H.append(hhh)
  X = tuple(X)
  ans = 0
  end = n-1
  while True:
    x = X[end] - d
    start = bisect_left(X,x-d)
    num = math.ceil(H[end] / a)
    ans += num
    H[end] = 0
    e = end
    end = start-1
    A = a * num
    for i in range(start,e):
      if H[i] <= 0:
        continue
      H[i] -= A
      if H[i] > 0:
        end = i
    if end < 0:
      break

  print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

def main():
  n,d,a = map(int,input().split())
  xx = []
  hh = []
  X = []
  H = []
  for _ in range(n):
    tmp = list(map(int,input().split()))
    xx.append(tmp[0])
    hh.append(tmp[1])

  k = zip(xx,hh)
  q = sorted(k)
  for xxx,hhh in q:
    X.append(xxx)
    H.append(hhh)
  X = tuple(X)
  ans = 0
  end = n-1
  while True:
    x = X[end] - d
    start = bisect_left(X,x-d)
    num = math.ceil(H[end] / a)
    ans += num
    H[end] = 0
    e = end
    end = start-1
    for i in range(start,e):
      H[i] -= a * num
      if H[i] > 0:
        end = i
    if end < 0:
      break

  print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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


n,d,a = map(int,input().split())
xx = []
hh = []
X = []
H = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xx.append(tmp[0])
  hh.append(tmp[1])

k = zip(xx,hh)
q = sorted(k)
for xxx,hhh in q:
  X.append(xxx)
  H.append(hhh)
X = tuple(X)
ans = 0
end = n-1
while True:
  x = X[end] - d
  start = bisect_left(X,x-d)
  num = math.ceil(H[end] / a)
  ans += num
  H[end] = 0
  e = end
  end = start-1
  for i in range(start,e):
    H[i] -= a * num
    if H[i] > 0:
      end = i
  if end < 0:
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import math

n,d,a = map(int,input().split())
xx = []
hh = []
X = []
H = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xx.append(tmp[0])
  hh.append(tmp[1])

k = zip(xx,hh)
q = sorted(k)
for xxx,hhh in q:
  X.append(xxx)
  H.append(hhh)
X = tuple(X)
ans = 0
end = n-1
while True:
  x = X[end] - d
  start = bisect_left(X,x-d)
  num = math.ceil(H[end] / a)
  ans += num
  H[end] = 0
  e = end
  end = start-1
  for i in range(start,e):
    H[i] -= a * num
    if H[i] > 0:
      end = i
  if end < 0:
    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import math

n,d,a = map(int,input().split())
xh = []
X = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  xh.append(tmp)
  X.append(tmp[0])

xh.sort()
X.sort()

ans = 0
end = n-1
while True:
  x = X[end] - d
  start = bisect_left(X,x-d)
  num = math.ceil(xh[end][1] / a)
  ans += num
  xh[end][1] = 0
  #print(start,end,ans)
  e = end
  end = start-1
  for i in range(start,e):
    xh[i][1] -= a * num
    if xh[i][1] > 0:
      end = i
  if end < 0:
    break
  #print(xh)

print(ans)

Submission status: Time Limit Exceeded

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

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, -(-h//A)]

S.sort()
print()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1]
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Time Limit Exceeded

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

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    if h % A == 0:
        h //= A
    else:
        h = h//A + 1
    S[i] = [x, h]

S.sort()
print()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1]
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Time Limit Exceeded

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

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    if h % A == 0:
        h //= A
    else:
        h = h//A + 1
    S[i] = [x, h]

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1]
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Time Limit Exceeded

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

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

S.sort()
cnt = 0

for i, item in enumerate(S):
    if item[1] <= 0:
        continue
    if item[1] % A == 0:
        dmg = item[1]
        cnt += item[1] // A
    else:
        dmg = A * (item[1]//A + 1)
        cnt += item[1]//A + 1
    max_X = item[0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Time Limit Exceeded

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

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

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Time Limit Exceeded

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

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

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    j = i + 1
    while j < N:
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg
        j += 1

print(cnt)

Submission status: Time Limit Exceeded

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

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    j = i + 1
    while j < N:
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg
        j += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, dis, dam = map(int, input().split())
    mon = [list(map(int, input().split())) for _ in range(n)]
    mon.sort(key=lambda x: x[0])
    imos = [0]*(n+1)
    dis = 2*dis + 1
    ans = 0
    for i in range(n):
        if 0 < i:
            imos[i] += imos[i-1]
        if imos[i] < mon[i][1]:
            tmp = (mon[i][1] - imos[i] + dam - 1) // dam
            ans += tmp
            tmp *= dam
            imos[i] += tmp
            L, R = i, n
            while L+1 < R:
                P = (L+R)//2
                if mon[P][0] < mon[i][0]+dis:
                    L = P
                else:
                    R = P
            imos[L+1] -= tmp
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, d, a = [int(i) for i in input().split()]
chk = []
for i in range(n):
  x, h = [int(i) for i in input().split()]
  chk.append((x, 0, h))
  
from heapq import heapify, heappop, heappush
heapify(chk)
atk_cnt = 0
ans = 0
while chk:
  x, t, h = heappop(chk)
  if t == 0:
    if atk_cnt * a >= h:
        continue
    remain = h - atk_cnt * a
    new_atk = (remain - 1) // a + 1
    heappush(chk, (x + 2 * d, 1, new_atk))
    ans += new_atk
    atk_cnt += new_atk
  else:
    atk_cnt -= h
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import math
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
X.insert(0,[-1,-1])
def update(m,i,j,a):  #ノード値の更新 i<=x<j
    l,r = T[m][0]
    if r<=i or l>=j:
        return 
    if i<=l and r<=j:
        T[m][1] -= a*(r-l)
    else:
        update(2*m,i,j,a)
        update(2*m+1,i,j,a)
def find(m,i):  #node[i]の評価
    l,r = T[m][0]
    if l==i and r==i+1:
        return T[m][1]
    if l<=i and r>=i+1:
        T[2*m][1] += T[m][1]//2
        T[2*m+1][1] += T[m][1]//2
        T[m][1] = 0
        l1,r1 = T[2*m][0]
        if l1<=i and r1>=i+1:
            return find(2*m,i)
        else:
            return find(2*m+1,i)

k = 0
n = N
while 2**k<N:
    k += 1
N = 2**k  #一番下の層のノード数
T = [[] for _ in range(2*N)]  #木の初期化　意図は1-origin
for i in range(N,2*N):
    T[i] = [[i-(N-1),i-(N-1)+1],X[i-(N-1)][1] if i-(N-1)<n+1 else 0]  #区間の右端は含まない
m = N//2
while m>0:
    for i in range(m,2*m):
        T[i] = [[T[2*i][0][0],T[2*i+1][0][1]],0]  #各ノードは区間とノードの値を持つ．
    m = m//2  #ルートはT[1]
Pos = [X[i][0] for i in range(n+1)]  
cur = 1
cnt = 0
while cur<n+1:
    x = X[cur][0]+D
    k = math.ceil(X[cur][1]/A)
    indr = bisect_right(Pos,x+D)
    cnt += k
    update(1,cur,indr,k*A)
    flag = 0
    for i in range(cur,n+1):
        X[i][1] = find(1,i)
        if X[i][1]>0:
            cur = i
            flag = 1
            break
    if flag==0:break
print(cnt)

Submission status: Time Limit Exceeded

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

# N: 処理する区間の長さ

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)

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

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

for idx in range(N):
    add(idx+1, idx+2, xhl[idx][1])

def ceil(a, b):
   return a // b + (a % b > 0)

import bisect

ans = 0
for i in range(N):
    hp = query(i + 1, i + 2)
    if hp > 0:
        count = 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 math
N,D,A = map(int,input().split(' '))
XHn = [ list(map(int,input().split(' '))) for _ in range(N)]
ans = 0
XHn.sort()
for i  in range(N):
    x = XHn[i][0]
    h = XHn[i][1]
    need_bom = 0
    distance_bom = x + D*2
    if h > 0:
        need_bom = math.ceil(h/A)
        for i2 in range(i,N):
            x2 = XHn[i2][0]
            if x2 <= distance_bom:
                XHn[i2][1] -= A*need_bom
            else:
                break
        ans += need_bom
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import math
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LIR(n):
    return [LI() for i in range(n)]

class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

def solve():
    n,d,a = LI()
    g = LIR(n)
    g.sort()
    X = [i for (i,_) in g]
    s = SegmentTree(n)
    ans = 0
    for i in range(n):
        x = g[i][0]
        j = bisect.bisect_right(X,x+2*d)-1
        h = g[i][1]-s.get(0,i)
        if h <= 0:
            continue
        k = math.ceil(h/a)
        ans += k
        if i == j:
            continue
        p = k*a
        s.update(i,s.get(i)+p)
        s.update(j,s.get(j)+-p)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def solve():
    n,d,a = LI()
    g = LIR(n)
    g.sort()
    X = [i for (i,_) in g]
    s = SegmentTree(n)
    ans = 0
    for i in range(n):
        x = g[i][0]
        j = bisect.bisect_right(X,x+2*d)-1
        h = g[i][1]-s.get(0,i)
        if h <= 0:
            continue
        k = math.ceil(h/a)
        ans += k
        if i == j:
            continue
        p = k*a
        s.update(i,s.get(i)+p)
        s.update(j,s.get(j)+-p)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def get(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def solve():
    n,d,a = LI()
    g = LIR(n)
    g.sort()
    X = [i for (i,j) in g]
    f = []
    for i in range(n):
        x,h = g[i]
        j = bisect.bisect_right(X,x+2*d)-1
        f.append(j)
    s = SegmentTree(n)
    ans = 0
    for i in range(n):
        h = g[i][1]-s.get(0,i)
        if h <= 0:
            continue
        k = math.ceil(h/a)
        j = f[i]
        p = k*a
        s.update(i,s.get(i)+p)
        s.update(j,s.get(j)+-p)
        ans += k
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, D, A = map(int, input().split())
monsters = deque(sorted([list(map(int, input().split())) for _ in range(N)]))
ans = 0
while monsters:
    X, H = monsters.popleft()
    if H < 1:
        continue
    attack = (H + A - 1) // A
    ans += attack
    for i, monster in enumerate(monsters):
        if X + 2 * D >= monster[0]:
            monsters[i][1] -= attack * A
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input=sys.stdin.buffer.readline
def main():
    N,D,A=map(int,input().split())
    monster=[list(map(int,input().split())) for i in range(N)]
    monster.sort(key=lambda x:x[0])
    ans=0
    for i in range(N):
        if(monster[i][1]==0):
            continue
        cnt=math.ceil(monster[i][1]/A)
        ans+=cnt
        for j in range(i+1,N):
            if monster[j][0]-monster[i][0]>2*D:
                break
            monster[j][1]=max(0,monster[j][1]-cnt*A)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    L = LI()
    L.sort()
    if sum(L)<=L[-1]*2:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, M = LI()
    A = [LI()for _ in range(N)]
    A.sort(key=lambda x:x[0])
    ans = 0
    for a,b in A:
        if M<=b:
            ans += a*M
            break
        ans += a*b
        M -= b
    print(ans)
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    D = defaultdict(int)
    for s in S:
        cur = []
        for i,j in Counter(s).items():
            cur.append((i,j))
        #print(cur)
        cur.sort()
        cur = tuple(cur)
        D[cur] += 1
    ans = 0
    for d in D.values():
        ans += (d-1)*d//2
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+A[i]
    ans = 0
    for i in range(N):
        l = i-1; r = N
        if S[-1]-S[i]<K:
            break
        while(r-l>1):
            now = (l+r)//2
            if S[now]-S[i]<K:
                l = now
            else:
                r = now
        #print(i,r)
        ans += (N-r+1)
    print(ans)
    return

def examE():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret

    N, D, A = LI()
    X = [LI()for _ in range(N)]
    X.sort()
    L = [0]*N
    for i in range(N):
        L[i] = X[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i,[x,h] in enumerate(X):
        H = h - S.query(i)
        if H<=0:
            continue
        ne = bisect.bisect_right(L,x+2*D)
        #print(ne)
        need = (H-1)//A + 1
        S.update(i,ne,need*A)
        ans += need
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
import math
N,D,A=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(N)]
monster.sort(key=lambda x:x[0])
ans=0
for i in range(N):
    if(monster[i][1]==0):
        continue
    cnt=math.ceil(monster[i][1]/A)
    ans+=cnt
    for j in range(i+1,N):
        if monster[j][0]-monster[i][0]>2*D:
            break
        monster[j][1]=max(0,monster[j][1]-cnt*A)
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
    else:
        continue

print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
i=0
k=0
while i<=n-1:
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        flag=True
        for j in range(q-i):
            x[i + j][1] -= w
            if x[i+j][1]<=0:
                if flag:
                    k+=1
            else:
                flag=False
    i=i+k
    k=0
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
i=0
k=0
while i<=n-1:
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        flag=True
        for j in range(q-i):
            if x[i+j][1]<=0:
                if flag:
                    k+=1
            else:
                x[i+j][1]-=w
                flag=False
    i=i+k
    k=0
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
k=0
while i<=n-1:
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
    i=i+k
    k=0
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
k=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
    i=i+k
    k=0
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)

Submission status: Time Limit Exceeded

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

n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)

Submission status: Time Limit Exceeded

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

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d)
        for j in range(q-i):
            x[i+j][1]-=w
print(ans)