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 math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  s=set()
  for j in range(i,N):
    if abs(d-l[j][0])<=D:
      s.add(j)
    else:break
  for k in s:
    l[k][1]-=time*A
  ans+=time
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n, d, a = (int(v) for v in stdin.readline().split())
monsters = [(int(v) for v in stdin.readline().split()) for i in range(n)]

monsters = [[x, (h // a + 1) if h % a > 0 else (h // a)] for x, h in monsters]
monsters = sorted(monsters)
bomb_size = 2 * d + 1
num_bombs = 0

ptr = 0
while ptr < len(monsters):
    while ptr < len(monsters) and monsters[ptr][1] <= 0:
        ptr += 1
    if ptr < len(monsters):
        position = monsters[ptr][0]
        bombs_now = monsters[ptr][1]
        i = ptr
        while i < len(monsters) and monsters[i][0] - position < bomb_size:
            monsters[i][1] -= bombs_now
            i += 1
        num_bombs += bombs_now

print(num_bombs)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

n, d, a = (int(v) for v in stdin.readline().split())
monsters = [(int(v) for v in stdin.readline().split()) for i in range(n)]

monsters = [[x, (h // a + 1) if h % a > 0 else (h // a)] for x, h in monsters]
monsters = deque(sorted(monsters))
bomb_size = 2 * d + 1
num_bombs = 0

while len(monsters) > 0:
    while len(monsters) > 0 and monsters[0][1] <= 0:
        monsters.popleft()
    if len(monsters) > 0:
        position = monsters[0][0]
        bombs_now = monsters[0][1]
        i = 0
        while i < len(monsters) and monsters[i][0] - position < bomb_size:
            monsters[i][1] -= bombs_now
            i += 1
        num_bombs += bombs_now

print(num_bombs)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    #print(l)
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  r=l
  for _ in range(N):
    if l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
      if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
        break
      else:
        r+=1
        if r<N:
          xh[r][1]=max(0,xh[r][1]-la*A)
    else:
      break
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    #print(l)
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  r=l
  while l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    #xh[r][1]=max(0,xh[r][1]-la*A)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
      if r<N:
        xh[r][1]=max(0,xh[r][1]-la*A)
        #print(xh)
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# F - Silver Fox vs Monster

import bisect

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

    # sum[0:i+1]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    # add x to i
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, D, A = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

X = [XH[i][0] for i in range(N)]
X_right = [bisect.bisect_right(X, XH[i][0] + 2*D) for i in range(N)]

ans = 0
bomb_damage = Bit(N+1)
for i in range(N):
    damage = bomb_damage.sum(i+1)
    if XH[i][1] - damage > 0:
        n_bomb = -(-(XH[i][1] - damage)//A)
        ans += n_bomb
        bomb_damage.add(i+1, n_bomb * A)
        bomb_damage.add(X_right[i]+1, -n_bomb * A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  for _ in range(N):
    if  l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
      if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
        break
      else:
        r+=1
  #print(1,l,r)
  la = (xh[l][1]+A-1)//A
  ans +=(xh[l][1]+A-1)//A
  for i in range(l,min(r+1,N)):
    xh[i][1]=max(0,xh[i][1]-la*A)
    #print(xh[i][1],i)
  if r==l:
    r+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

N,D,A = list(map(int,input().split()))
enemies = [list(map(int,input().split())) for i in range(N)]
enemies.sort(key=lambda x: x[0])

#とりあえず左から順番に範囲ギリギリで頃していく。どうせTLE
mochikoshis = deque()
ans = 0
for i in range(N):
    popleftcnt = 0
    for mochikoshi in mochikoshis:
        if enemies[i][0] <= mochikoshi[0]:
            enemies[i][1] -= mochikoshi[1]
        else:
            popleftcnt += 1

    for j in range(popleftcnt):
        mochikoshis.popleft()
    if 1 <= enemies[i][1]:
        tmp = math.ceil(enemies[i][1]/A)
        ans += tmp
        mochikoshis.append((enemies[i][0]+2*D,tmp*A))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  while l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
  #print(1,l,r)
  la = (xh[l][1]+A-1)//A
  ans +=(xh[l][1]+A-1)//A
  for i in range(l,min(r+1,N)):
    xh[i][1]=max(0,xh[i][1]-la*A)
    #print(xh[i][1],i)
  if r==l:
    r+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,D,A = map(int,input().split())
  import numpy as np
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  X = [xh[0] for xh in XH]
  H = np.array([xh[1] for xh in XH])
  ans = 0
  l=[0]*N
  x = X[0]
  j = 0
  h = H[0]
  b = (h+A-1)//A
  ans += b
  while True:
    if j+1>=N:
      break
    if X[j+1]<=x+2*D:
      j+=1
    else:
      break
  H[0:j+1:]-=b*A
  l[0]=j
  for i in range(1,N):
    x = X[i]
    j = max(i,l[i-1])
    h = H[i]
    if h<=0:
      continue
    else:
      b = (h+A-1)//A
      ans += b
      while True:
        if j+1>=N:
          break
        if X[j+1]<=x+2*D:
          j+=1
        else:
          break
      H[i:j+1:]-=b*A
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
ans = 0
import bisect
while E:
    x = E.pop(0)
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = d[x]
    ans += z
    for k in range(y):
        d[E[k]] -= z 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
ans = 0
import bisect
while E:
    x = E.pop(0)
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = d[x]
    ans += z
    for k in range(y):
        d[E[k]] -= z 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    d[x] = n
    E.append(x)
E.sort()
ans = 0
import bisect
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = d[x]
    ans += z
    for k in range(i,y):
        d[E[k]] -= z 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append([x, h])
monster.sort()
monster = np.array(monster)
bomb = 0
j = 1
for i in range(n):
  while j < n and monster[j][0] - monster[i][0] <= 2 * d:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  monster[i+1:j, 1] -= atk
print(bomb)

Submission status: Time Limit Exceeded

Solution code:
def main():
  def syaku(j,x,D):
    while True:
      if j+1>=N:
        break
      if XH[j+1][0]<=x+2*D:
        j+=1
      else:
        break
    return j
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  j = 0
  l[0]=syaku(j,x,D)
  for i in range(1,N):
    x = XH[i][0]
    j = l[i-1]
    l[i]=syaku(j,x,D)
  H = [xh[1] for xh in XH]
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      b = (h+A-1)//A
      ans += b
      y = b*A
      for j in range(i,a+1):
        H[j]-=y
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  def syaku(j,x,D):
    while True:
      if j+1>=N:
        break
      if XH[j+1][0]<=x+2*D:
        j+=1
      else:
        break
    return j
  N,D,A = map(int,input().split())
  import numpy as np
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  j = 0
  l[0]=syaku(j,x,D)
  for i in range(1,N):
    x = XH[i][0]
    j = l[i-1]
    l[i]=syaku(j,x,D)
  H = np.array([xh[1] for xh in XH])
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      b = (h+A-1)//A
      ans += b
      H[i:a+1:]-=b*A
  print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X, H = zip(*XH)

bit = BinaryIndexTree(N)

ans = 0
for i in range(N):
    x = X[i]
    h = H[i]
    h -= bit.sum(i+1)
    if h <= 0:
        continue
    atk = (h + A - 1) // A
    ans += atk
    damage = atk * A
    bit.add(i+1, damage)
    pos = bisect.bisect_right(X, x+2*D)
    pos = min(N + 1, pos)
    bit.add(pos+1, -damage)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = np.array(XH[::2], np.int64)
H = np.array(XH[1::2], np.int64)
D *= 2

arg = np.argsort(X)
X = X[arg]
H = H[arg]

answer = 0
for i in range(N):
    if H[i] <= 0:
        continue
    h = H[i]
    cnt = h // A + min(1, h % A)
    n = np.searchsorted(X, X[i] + D, side='right')
    H[i:n] -= A * cnt
    answer += cnt

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
for i in range(N):
    x,h = map(int,input().split())
    d[x] = h
    E.append(x)
E.sort()
ans = 0
import bisect
while E:
    x = E.pop(0)
    y = bisect.bisect_right(E,x+2*D)
    z = (d[x]+A-1)//A
    ans += z
    for j in range(y):
        d[E[y-j-1]] -= z*A
        if d[E[y-j-1]] <= 0:
            E.pop(y-j-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
for i in range(N):
    x,h = map(int,input().split())
    d[x] = h
    E.append(x)
E.sort()
ans = 0
import bisect
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = (d[x]+A-1)//A
    ans += z
    for j in range(i,y):
        d[E[j]] -= z*A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append([x, h])
monster.sort()
bomb = 0
j = 0
for i in range(n):
  while j < n and monster[j][0] - monster[i][0] <= 2 * d:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  for k in range(i+1, j):
    monster[k][1] -= atk
print(bomb)

Submission status: Time Limit Exceeded

Solution code:
def main():
  def binary_search(left,right,x):
    while left+1!=right:
      mid = (right+left)//2
      if XH[mid][0]<=x+2*D:
        left = mid
      else:
        right = mid
    return left
  
  def cal(h,i,a,ans):
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
    return ans
  
  N,D,A = map(int,input().split())
  import numpy as np
  import math
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  l[0]=binary_search(0,N,x)
  for i in range(1,N):
    x = XH[i][0]
    l[i]=binary_search(l[i-1],N,x)
  H = np.array([xh[1] for xh in XH])
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      ans = cal(h,i,a,ans)
  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N,D,A = map(int,input().split())
  import numpy as np
  import math
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  left = 0
  right = N
  while left+1!=right:
    mid = (right+left)//2
    if XH[mid][0]<=x+2*D:
      left = mid
    else:
      right = mid
  l[0]=left
  for i in range(1,N):
    x = XH[i][0]
    right = N
    left = l[i-1]
    while left+1!=right:
      mid = (right+left)//2
      if XH[mid][0]<=x+2*D:
        left = mid
      else:
        right = mid
    l[i]=left
  H = np.array([xh[1] for xh in XH])
  for i,a in enumerate(l):
    h = H[i]
    if h<=0:
      continue
    else:
      b = math.ceil(h/A)
      ans += b
      H[i:a+1:]-=b*A
  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
for i in range(n):
  l[i][1]=(l[i][1]+a-1)//a
ans=0
L=[]
L=deque(L)
left=l[0][0]
for i in range(n):
  ct=0
  f=0
  for j in range(len(L)):
    if L[j][0]<=l[i][0]<=L[j][1]:
      l[i][1]=max(0,l[i][1]-L[j][2])
      f=1
    else:
      ct+=1
      if f==1:
        break
  for k in range(ct):
    L.popleft()
  ans+=l[i][1]
  L.append([l[i][0],l[i][0]+2*d,l[i][1]])
  l[i][1]=0
  left=l[i][0]+2*d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from functools import lru_cache
input = sys.stdin.readline

sys.setrecursionlimit(1000000)

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

XH.sort(key=lambda xh: xh[0])
XH = np.array(XH)

ans = 0 
while len(XH)>0:
	TRAGET = (XH[:,0] <= XH[0][0]+2*D)
	H = XH[0][1]
	if(0==H%A):
		a = H//A
	else:
		a = H//A+1
	XH[TRAGET] = XH[TRAGET] - [0,a*A]
	ans += a
	TRAGET = (XH[:,1] > 0)
	XH = XH[TRAGET]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from functools import lru_cache
input = sys.stdin.readline

sys.setrecursionlimit(1000000)

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

XH.sort(key=lambda xh: xh[0])
XH = np.array(XH, dtype=np.int64)

ans = 0 
while len(XH)>0:
	TRAGET = (XH[:,0] <= XH[0][0]+2*D)
	H = XH[0][1]
	if(0==H%A):
		a = H//A
	else:
		a = H//A+1
	XH[TRAGET] = XH[TRAGET] - [0,a*A]
	ans += a
	TRAGET = (XH[:,1] > 0)
	XH = XH[TRAGET]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = map(list,zip(*sorted(zip(m,m))))
    count = 0
    for i in range(N):
        if H[i] > 0:
            bomb = (H[i]+A-1)//A
            count += bomb
            damage = bomb * A
            for j in range(i,N):
                if X[j] <= X[i] + 2*D:
                    H[j] -= damage
                else:
                    break

    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
queue = []
s_i = 0
sum_q = 0
for i in range(N):
    for b, last in queue[s_i:]:
        if XH[i][0] > last:
            sum_q -= queue[s_i][0]
            s_i += 1
        else:
            break

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        queue.append([bomb[i], XH[i][0] + 2 * D])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(10 ** 7)

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

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


E = sorted(E, key=lambda x: x[0])

damage = 0
BOMB = {}
x = 0
ans = 0
for i in range(N):
    x, h = E[i]

    dlt = []
    for xd, d in BOMB.items():
        if x > xd:
            damage -= d
            dlt.append(xd)
    for dl in dlt:
        BOMB.pop(dl)

    h -= damage

    if h <= 0:
        continue
    xm = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    BOMB[xm] = cnt * A
    ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop

sys.setrecursionlimit(10 ** 7)

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

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


E = sorted(E, key=lambda x: x[0])

damage = 0
BOMB = defaultdict(int)
x = 0
ans = 0
for i in range(N):
    x, h = E[i]

    dlt = []
    for xd, d in BOMB.items():
        if x > xd:
            damage -= d
            dlt.append(xd)
    for dl in dlt:
        BOMB.pop(dl)

    h -= damage

    if h <= 0:
        continue
    xm = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    BOMB[xm] = cnt * A
    ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0, h0))
    r = h0
    for i, (x, h) in enumerate(XH):
        while Q:
            xx, hh = Q[0]
            if xx < x - D:
                Q.popleft()
            else:
                break
        for xx, hh in Q:
            h -= hh 
            if h <= 0:
                break
        else:
            Q.append((x, h))
            r += h
    print(r)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    x,h = L2[i] 
    if h > 0:
        ans += h
        L2[i][1] = 0
        lim = x + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= h
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    ans = 0
    for i in range(N):
        if H[i] <= 0:
            continue
        x = X[i]
        h = H[i]
        n = -(-h // A)
        ans += n
        r = bisect.bisect_right(X, x+2*D)
        for j in range(i, min(r, N)):
            H[j] -= n*A

    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
left = 0
right = N
while left+1!=right:
  mid = (right+left)//2
  if XH[mid][0]<=x+2*D:
    left = mid
  else:
    right = mid
l[0]=left
for i in range(1,N):
  x = XH[i][0]
  right = N
  left = l[i-1]
  while left+1!=right:
    mid = (right+left)//2
    if XH[mid][0]<=x+2*D:
      left = mid
    else:
      right = mid
  l[i]=left
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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


#bの倍数の中でaを超える最小
def calc(a,b):
    return math.ceil(a/b)*b

ans=0
for i in range(N):
    if XH[i][1]>0:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        ans+=XH[i][1]//A
        if XH[i][1]%A!=0:
            ans+=1
        dam=calc(XH[i][1],A)
        for j in range(Lb,Rb):
            XH[j][1]-=dam
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,d,a=map(int,input().split())
  xh=[tuple(map(int,input().split())) for _ in range(n)]
  xh.sort()
  ans=0
  while xh:
    x,h=xh.pop(-1)
    c=h//a+bool(h%a)
    b=a*c
    ans+=c
    t=x-2*d
    pool=[]
    while True:
      if not xh:
        break
      y,z=xh.pop(-1)
      if y >= t:
        if z>b:
          z-=b
          pool.append((y,z))
      else:
        pool.append((y,z))
        break
    pool=list(reversed(pool))
    xh.extend(pool)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
j = 0
while True:
  if j+1>=N:
    break
  if XH[j+1][0]<=x+2*D:
    j+=1
  else:
    break
l[0]=j
for i in range(1,N):
  x = XH[i][0]
  j = l[i-1]
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  l[i]=j
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:a+1:]-=b*A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
from collections import deque

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

for i in range(N):
  X = List[i][0]
  H = List[i][1]
  H = math.ceil(H / A)
  arr.append(X)
  Harr.append(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:
def main():
  n,d,a=map(int,input().split())
  xh=[tuple(map(int,input().split())) for _ in range(n)]
  xh.sort()
  ans=0
  xhappend=xh.append
  while xh:
    x,h=xh.pop(-1)
    c=h//a+bool(h%a)
    b=a*c
    ans+=c
    t=x-2*d
    pool=[]
    while True:
      if not xh:
        break
      y,z=xh.pop(-1)
      if y >= t:
        if z>b:
          z-=b
          pool.append((y,z))
      else:
        pool.append((y,z))
        break
    for i in range(len(pool)):
      xhappend(pool.pop(-1))
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
xhappend=xh.append
while xh:
  x,h=xh.pop(-1)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x-2*d
  pool=[]
  while True:
    if not xh:
      break
    y,z=xh.pop(-1)
    if y >= t:
      if z>b:
        z-=b
        pool.append((y,z))
    else:
      pool.append((y,z))
      break
  for i in range(len(pool)):
    xhappend(pool.pop(-1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline;
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]
 
N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    if L2[i][1] > 0:
        ans += L2[i][1]
        lim = L2[i][0] + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= L2[i][1]
            else:
                break
        L2[i][1] -= L2[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, di, a = LI()
    xs = []
    d = {}
    q = []
    for i in range(n):
        x, h = LI()
        xs.append(x)
        if h % a == 0:
            d[x] = h // a
        else:
            d[x] = h // a + 1
    sorted_xs = sorted(xs)
    ans = 0
    for i in range(n):
        x = sorted_xs[i]
        if d[x] < 1:
            continue
        else:
            ans += d[x]
            j = 1
            while i + j < n:
                if sorted_xs[i + j] <= x + 2 * di:
                    d[sorted_xs[i + j]] -= d[x]
                else:
                    break
                j += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]
 
N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    if L2[i][1] > 0:
        ans += L2[i][1]
        lim = L2[i][0] + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= L2[i][1]
            else:
                break
        L2[i][1] -= L2[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# TLE
import math
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_list = [0]*N
hp_dict = dict()
for j in range(N):
    monster_place, monster_hp = map(int, input().split())
    place_list[j] = monster_place
    hp_dict[monster_place] = monster_hp
ans = 0
place_list = sorted(place_list)
new_place_dict = dict()
for s in range(N):
    new_place_dict[s] = place_list[s]

# print(place_list)
for i in range(N):
    place = place_list[i]
    if hp_dict[place] <= 0:
        continue
    else:
        bomb = math.ceil(hp_dict[place] / A)
        hp_dict[place] = 0
        # print(bomb)
        ans += bomb
        index = i
        if i == N - 1:
            break
        while(place_list[index] <= place+2*D):
            if hp_dict[new_place_dict[index]] <= 0:
                index += 1
                if index == N:
                    break
                continue
            else:
                hp_dict[new_place_dict[index]] -= bomb * A
                index += 1
                if index == N:
                    break

print(ans)
# print(hp_dict)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = np.array([-(-i//a) for i in H])
ans = 0
for now in range(n):
  l = K[now]
  if l > 0:
    ans += l
    K[now:bisect.bisect_right(X, X[now]+2*d)] -= l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = []
for i in range(N):
    XH.append(list(map(int, input().split())))
XH.sort()
ans = 0
for i, name in enumerate(XH):
    if name[1] > 0:
        p = name[0]
        t = A * math.ceil(name[1] / A)
        ans += math.ceil(name[1] / A)
        for l in XH[i::]:
            if l[0] <= p + 2 * D:
                l[1] -= t
            else:
                break
print(ans)