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())
M = []
total_hp = 0
for i in range(n):
  M.append(list(map(int, input().split())))
M.sort(key=lambda pos: pos[0])
X = [x[0] for x in M]

import math
import bisect
counter = 0
for i in range(n):
#  print(M)
  target_hp = M[i][1]
  if target_hp <= 0:
    n += 1
    continue
  else:
    target_x = X[i]
    bom_x = target_x + d
    bom_n = math.ceil(target_hp / a)
    #爆破範囲
    left = bom_x - d
    right = bom_x + d
    #ダメージ範囲
    id_left = bisect.bisect_left(X, left)
    id_right = bisect.bisect_right(X, right)
    for i in range(id_left, id_right):
      M[i][1] -= bom_n * a

    n += 1
    counter += bom_n
#    print(n, target_x, counter)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
import bisect
import math
cnt=0
for i in range(n):
    if h[i]<=0:
        continue
    else:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        for j in range(i,k):
            h[j]-=(m*a)
print(cnt)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    tX,tH=map(int,input().split())
    if tX in monster:
        monster[tX]=max(monster[tX],tH)
    else:
        monster[tX]=tH

monster=sorted(monster.items())

count=0

for i in range(len(monster)):
    if monster[i][1]<=0:
        continue
    tmp=monster[i][0]+D
    kai=math.ceil(monster[i][1]/A)
    t2=A*kai
    for k in range(len(monster)):
        if monster[k][0]<=tmp+D:
            monster[k]=(monster[k][0],monster[k][1]-t2)
        else:
            break
    count+=kai

print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
input = sys.stdin.readline
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
for i in range(n):
  if remain[i] <= 0:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  k = remain[i]
  ans += k
  for j in range(i,br):
    remain[j] -= k
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    import numpy as np
    from math import ceil
    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 = np.array(XH)
    X = XH[:,0]
    H = XH[:,1]
    ans = 0
    for i in range(N):
        if H[i] > 0:
            tmp = np.searchsorted(X,X[i]+2*D,side = "right")
            num = ceil(H[i]/A)
            H[i:tmp] -= A*num
            ans += num
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
length=len(enemies)
for i in range(length):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,length):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A


print(retval)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d,a = map(int,input().split())
e = []
for i in range(n):
  x,h = map(int,input().split())
  e.append([x,math.ceil(h/a)])
e.sort()
ans = 0
for i in range(n):
  at = e[i][1]
  if at > 0:
    ans += at
    hani = e[i][0] + d*2
    for j in range(i,n):
      if e[j][0] <= hani:
        e[j][1] -= at
print(ans)

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline


def main():
    n, d, a = map(int, input().split())
    hp = [list(map(int, input().split())) for _ in range(n)]
    heapify(hp)

    ans = 0

    while hp:
        left = heappop(hp)
        cnt = ceil(left[1] / a)
        li = []
        while hp and hp[0][0] <= left[0] + 2 * d:
            nxt = heappop(hp)
            if nxt[1] - a * cnt > 0:
                li.append([nxt[0], nxt[1] - a * cnt])

        for e in li:
            heappush(hp, e)

        ans += cnt

    print(ans)


if __name__ == "__main__":
    main()

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

ans = 0

for i in range(N):
    if XH[i][1] <= 0:
        continue
    explode = (XH[i][1] + A - 1) // A
    for j in range(i, N):
        if XH[j][0] <= XH[i][0]+2*D:
            XH[j][1] -= explode*A
        else:
            break

    ans += explode

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as bfind

N, D, A = [int(x) for x in input().split()]

XH = [None] * N
for i in range(N):
    x, h = [int(x) for x in input().split()]
    XH[i] = [x, (h-1)//A + 1]
XH = sorted(XH, key=lambda x: x[0])
X = [x[0] for x in XH]


def attack_left(left):
    # 与えるダメージ
    h_left = XH[left][1]
    i_right = bfind(X, X[left]+2*D)

    for i in range(i_right):
        XH[i][1] -= h_left  # 範囲内に同じダメージ
    return h_left  # 攻撃回数

count = 0
for i in range(N):
    if XH[i][1] > 0:
        count += attack_left(left=i)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,D,A = [int(i) for i in input().split()]
preXH = [[int(i) for i in input().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
validdamage = deque()#[xmax,bonu] appendleft,pop
#左端
ans = XH[0][1]
validdamage.appendleft([XH[0][0]+2*D,XH[0][1]])
for m in range(1,N):
    x,h = XH[m]
    for n,(xmax,bonu) in enumerate(validdamage):
        if xmax>=x:
            h =max(0,h-bonu)
        else:
            for i in range(n,len(validdamage)):
                validdamage.pop()
            break
    if h:
        validdamage.appendleft([x+2*D,h])
        ans += h
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
count = 0
import math
import bisect
i = 0
l1 = []

while i < n:
    sn = i
    s = l[i][0]
    mi = math.ceil(l[i][1]/a)
    count += mi
    l1 =[]
    while i < n and l[i][0] <= s+2*d:
        
        l[i][1] -= mi*a
        if l[i][1] > 0:
            l1.append(i)
        i += 1
        
    if len(l1) > 0:
        i = l1[0]
    else:
        if i == n:
            print(count)
            exit()

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int,input().split())
event = []
for i in range(n):
  x,h = map(int,input().split())
  h = (h-1)//a + 1
  event.append([x,0,i,h])
for i in range(n):
  tmp = event[i][0] + 2 * d
  event.append([tmp,1,i,0])
event.sort()
#print(event)
use = [0 for _ in range(n)]
now = 0
ans = 0
for j in range(2*n):
  x,d,i,h = event[j]
  if d == 0:
    if h <= now:
      pass
    else:
      h -= now
      now += h
      use[i] = h
      ans += h
  else:
    now -= use[i]
  #print(x,d,i,ans,now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d,a = map(int,input().split())
e = []
for i in range(n):
  x,h = map(int,input().split())
  e.append([x,math.ceil(h/a)])
e.sort()
ans = 0
for i in range(n):
  at = e[i][1]
  if at > 0:
    ans += at
    hani = e[i][0] + d*2
    for j in range(i,n):
      if e[j][0] <= hani:
        e[j][1] -= at
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
M = []
X = []
total_hp = 0
for i in range(n):
  x, h = map(int, input().split())
  M.append([x, h])
  total_hp += h
  X.append(x)
M.sort(key=lambda pos: pos[0])
X.sort()

import math
import bisect
counter = 0
for i in range(n):
#  print(M)
  target_hp = M[i][1]
  if target_hp <= 0:
    n += 1
    continue
  else:
    target_x = X[i]
    bom_x = target_x + d
    bom_n = math.ceil(target_hp / a)
    #爆破範囲
    left = bom_x - d
    right = bom_x + d
    #ダメージ範囲
    id_left = bisect.bisect_left(X, left)
    id_right = bisect.bisect_right(X, right)
    for i in range(id_left, id_right):
      M[i][1] -= bom_n * a

    n += 1
    counter += bom_n
#    print(n, target_x, counter)
print(counter)

Submission status: Time Limit Exceeded

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

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
ans = 0
for i in range(n):
    if xh[i][1] > 0:
        # attack
        a_num = ceil(xh[i][1] / a)
        xh[i][1] -= a_num * a
        ans += a_num
        base_x = xh[i][0]
        for j in range(i, n):
            if xh[j][0] <= base_x + 2 * d:
                xh[j][1] -= a_num * a
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, D,A = map(int, input().split())
R =[] * N
for i in range(N):
    v, w = map(int, input().split())
    R.append([v,w])
    P = sorted(R)
cnt = 0
k = 0
for i in range(N):
    if P[i][1]>0:
        k = -(-P[i][1]//A)
        cnt += k 
    for j in range(1,N-i):
        if P[i][0]<P[i+j][0]<=P[i][0]+2 * D:
            P[i+j][1] += -k*A
        else:
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

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

heap = [(x, h, True) for x, h in XH]
heapify(heap)

ans = 0
bomb_effect = 0
while heap:
    x, h, monster_flg = heappop(heap)
    if monster_flg:
        tairyoku = h - bomb_effect
        if tairyoku > 0:
            new_bomb = -((-tairyoku) // A)
            ans += new_bomb
            heappush(heap, (x + 2 * D + 0.5, new_bomb, False))
            bomb_effect += new_bomb * A
    else:
        bomb_effect -= h * A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,D,A = map(int,input().split())
X = np.zeros(N,dtype=int)
H = np.zeros(N,dtype=int)
for i in range(N):
    X[i],H[i] = map(int,input().split())
idx = np.argsort(X)
X = X[idx]
H = H[idx]

now = 0
count = 0

while(1):
    while(H[now] <= 0):
        now += 1
        if(now >= len(H)):
            print(count)
            exit()
    
    tx = X[now] + D
    num = H[now] // A
    if(H[now] % A != 0):num += 1
    H[(X >= tx - D) & (X <= tx + D)] -= num * A
    count += num

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
from math import ceil

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
hp = xh
heapify(hp)

ans = 0

while hp:
    left = heappop(hp)
    cnt = ceil(left[1] / a)
    li = []
    while hp and hp[0][0] <= left[0] + 2 * d:
        nxt = heappop(hp)
        if nxt[1] - a * cnt > 0:
            li.append([nxt[0], nxt[1] - a * cnt])

    for e in li:
        heappush(hp, e)

    ans += cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def attack(monster, D, A):
    bomb_pos = monster[0][0] + D
    num = (monster[0][1]-1)//A + 1
    new_monster = []
    for elem in monster:
        if elem[0] > bomb_pos + D:
            new_monster.append(elem)
        elif elem[1] > num*A:
            new_monster.append([elem[0], elem[1] - num*A])
    if len(new_monster) == 0:
        flag=True
    else:
        flag=False
    #print(num, new_monster, flag)
    return num, new_monster, flag



N, D, A = map(int,input().split())
monster = []
for i in range(N):
    x, h = map(int,input().split())
    monster.append([x,h])
    
monster = sorted(monster, key=lambda x: x[0])

total = 0
while True:
    num, monster, flag = attack(monster, D, A)
    total += num
    if flag == True:
        break

print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
def bisect_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

n, d, a = map(int,input().split())
xlist=[]
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    xhlist.append([x, h])
    xlist.append(x)

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0
memory=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    if memory>0:
        hani=bisect_right(xlist, pos+d, lo=memory)
        memory=hani
    else:
        hani=bisect_right(xlist, pos+d)
        memory=hani
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            if xhlist[now+i][1]>0:
                xhlist[now+i][1]-=atk
            if swit==0:
                if xhlist[now+i][1]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int,input().split())
raw = []
event = []
for i in range(n):
  x,h = map(int,input().split())
  event.append([x,0,i,h])
for i in range(n):
  tmp = event[i][0] + 2 * d
  event.append([tmp,1,i])
event.sort()
#print(event)
use = [0 for _ in range(n)]
now = 0
ans = 0
for j in range(2*n):
  x,d,i = event[j][:3]
  if d == 0:
    h = event[j][3]
    if h <= now * a:
      pass
    else:
      h -= now * a
      tmp = (h-1)//a+1
      now += tmp
      use[i] = tmp
      ans += tmp
  else:
    now -= use[i]
  #print(x,d,i,ans,now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, D, A = map(int, input().split())
    B = []
    for i in range(N):
        X, H = map(int, input().split())
        B.append([X,H])

    B.sort()
    ans = 0
    ok = [False] * N
    for i in range(N):
        if ok[i]:
            continue
        cnt = B[i][1] // A if B[i][1] % A == 0 else B[i][1] // A + 1
        ans += cnt
        B[i][1] = 0
        ok[i] = True
        for j in range(min(i+1,N),N):
            if ok[j]:
                continue
            if B[j][0] <= B[i][0] + 2 * D:
                B[j][1] -= cnt * A
                if B[j][1] <= 0:
                    ok[j] = True
            else:
                break
    
    print(ans)



if __name__ == "__main__":
    main()

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

ans = 0
import queue
q=queue.Queue()


kaisuu = (xh[0][1] +a-1) // a
damege = kaisuu*a
ans += kaisuu
iti = xh[0][0] + 2*d
maedame = damege
skip =False
for i in range(1,n):
    while(iti < xh[i][0]):
        if skip:
            skip = False
            iti,damege = q.get()
            continue
        damege -= maedame
        if q.empty():
            skip =True
            break
        iti,maedame = q.get()
    if xh[i][1] - damege <= 0:
        continue
    kaisuu = (xh[i][1] - damege +a-1) // a
    damege += kaisuu*a
    q.put((xh[i][0] + 2*d, kaisuu*a))
    ans += kaisuu
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,d,a=map(int,input().split())
x,h=zip(*sorted(tuple(map(int,input().split())) for _ in range(n)))
x=np.array(x)
h=np.array(h)
alli=[]
maxalli=-1
res=0
for i,xi in enumerate(x):
    if h[i] <= 0:
        continue
    for j,yi in enumerate(x[maxalli+1:],maxalli+1):
        if yi <= xi+2*d:
            maxalli=j
            alli.append(j)
        else:
            break
    r=h[i]%a
    idm = h[i]//a
    if r:
        idm +=1
    res+=idm
    dm=idm*a
    h[alli] -= dm
    alli=alli[1:]
print(res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: tuple(map(int,input().split()))
N, D, A = inpl()
q = []
for _ in range(N):
    x, h = inpl()
    q.append((x, 0, h))
heapify(q)
ans = 0
d = 0
while q:
    x, s, h = heappop(q)
    if s == 0:
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            heappush(q, (x+2*D, 1, k*A))
            d += k*A
            ans += k
    else:
        d -= h
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
bomb = [0 for _ in range(n)]
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    bomb[i] = r - 1
res = 0
for i in range(n):
    if m[i][1] > 0:
        tres = (m[i][1] + a - 1) // a
        res += tres
        dh = tres * a
        for j in range(i, bomb[i] + 1):
            m[j][1] -= dh
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, d, a  = map(int,input().split())
x = []
h = []
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x.append(x_temp)
    h.append(h_temp)

x = np.array(x, dtype=np.int64)
h = np.array(h, dtype=np.int64)
sort_ind = np.argsort(x)
x = x[sort_ind]
h = h[sort_ind]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]):
            h[i] -= at_num * a
        else:
            break

print(ans)

Submission status: Time Limit Exceeded

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

X,H = [],[]
for _ in range(N):
	tx,th = map(int, input().split())
	X.append(tx)
	H.append(th)

import numpy as np
X = np.array(X, np.int64)
H = np.array(H, np.int64)


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

ans = 0
for i in range(N):
	if H[i] <= 0:
		continue
	cp = X[i]
	R = cp + (2*D)
	ind = np.searchsorted(X,R, side='right')
	attack = -(-H[i]//A)
	ans += attack
	H[i:ind] -= attack*A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

retval=0
while len(enemies)>0:
    e=enemies.pop(0)
    if e[1]<=0:
        continue
    bomb=0
    if e[1]%A==0:
        bomb=e[1]//A
    else:
        bomb=e[1]//A+1
    retval+=bomb
    for enemy in enemies:
        if enemy[0]-e[0]<=2*D:
            enemy[1]-=A*bomb
        else:
            break


print(retval)

Submission status: Time Limit Exceeded

Solution code:
import math
def bisect_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

n, d, a = map(int,input().split())
xlist=[]
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    xhlist.append([x, h])
    xlist.append(x)

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    #hani=bisect.bisect_right(xlist[now:], pos+d)
    #hani+=now
    hani=bisect_right(xlist, pos+d, lo=now)
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            if xhlist[now+i][1]>0:
                xhlist[now+i][1]-=atk
            if swit==0:
                if xhlist[now+i][1]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,D,A = map(int,input().split())
C = []
for i in range(N):
    X,H = map(int,input().split())
    C.append([X,(H-0.1)//A+1])
C.sort()
C = np.array(C)
ans = 0
s,t = 0,0
for i in range(N):
    k = C[i][0]
    if C[i][1] <= 0:
        continue
    while(t <= N-1 and C[t][0] <= k+2*D):
        t += 1
    l = C[i][1]
    ans += int(l)
    for m in range(i,t):
        C[m][1] = C[m][1]-l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int, input().strip().split())

M = [list(map(int, input().strip().split())) for _ in range(N)]
M = sorted(M)

ans = 0
while len(M) > 0:
  # 左端から詰めていく
  if M[0][1] <= 0:
    M = M[1:]
    continue
  # M[0]~M[0]+2Dを爆撃する(M[0]+Dに爆弾を落とす)
  n = (M[0][1]+(A-1))//A  # 今爆弾を落とす回数
  ans += n
  # 状態更新
  for i in range(len(M)):
    if M[i][0] > M[0][0]+2*D: break
    M[i][1] -= n*A

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
count = 0
import math
i = 0
while i < n:
    sn = i
    s = l[i][0]
    mi = math.ceil(l[i][1]/a)
    count += mi
    
    while i < n and l[i][0] <= s+2*d:
        
        l[i][1] -= mi*a
        i += 1
        
    for j in range(sn,i+1):
        if j >= n:
            print(count)
            exit()
        if l[j][1] > 0:
            i = j
            
            break

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,D,A = map(int,input().split())
C = []
for i in range(N):
    X,H = map(int,input().split())
    C.append([X,(H-0.1)//A+1])
C.sort()
C = np.array(C)
ans = 0
s,t = 0,0
for i in range(N):
    k = C[i][0]
    if C[i][1] <= 0:
        continue
    while(t <= N-1 and C[t][0] <= k+2*D):
        t += 1
    l = C[i][1]
    ans += int(l)
    for i in range(s,t):
        C[i][1] = C[i][1]-l
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()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = list(map(int, input().split()))
xh_data = []
for _ in range(n):
    xh = list(map(int, input().split()))
    xh_data.append(xh)

xh_data = sorted(xh_data)
sum_bomb = 0

while len(xh_data) > 0:
    xh_head = xh_data[0]
    if xh_head[1] <= 0:
        xh_data = xh_data[1:]
        continue
    else:
        if xh_head[1] % a == 0:
            bomb = xh_head[1] // a
        else:
            bomb = xh_head[1] // a + 1
        sum_bomb += bomb
        for xh in xh_data:
            if xh[0] <= xh_head[0] + 2 * d:
                xh[1] -= bomb * a

print(sum_bomb)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from math import ceil
from bisect import bisect
N,D,A = map(int,input().split())
X = list()
H = list()
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
XH = np.array(XH)
X = XH[:,0]
H = XH[:,1]
ans = 0
for i in range(N):
    tmp = i
    if H[i] > 0:
        tmp = bisect(X,X[i]+2*D)
        num = ceil(H[i]/A)
        H[i:tmp] -= A*num
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


from collections import deque


def main():
    n, d, a = map(int, input().split())
    x, h = [0] * n, [0] * n
    for i in range(n):
        x[i], h[i] = map(int, input().split())

    order = sorted(range(n), key=lambda idx: x[idx])
    res = 0
    bounds = deque()
    for idx in order:
        while bounds and x[idx] > bounds[0][0]:
            bounds.popleft()
        for bound, count in bounds:
            if x[idx] <= bound:
                h[idx] -= count * a
        if h[idx] > 0:
            bound = x[idx] + 2 * d
            count = (h[idx] + a - 1) // a
            bounds.append((bound, count))
            res += count

    print(res)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    tX,tH=map(int,input().split())
    if tX in monster:
        monster[tX]=max(monster[tX],tH)
    else:
        monster[tX]=tH

monster=sorted(monster.items())

count=0

for i in range(len(monster)):
    if monster[i][1]<=0:
        continue
    tmp=monster[i][0]+D
    kai=math.ceil(monster[i][1]/A)
    t2=A*kai
    for k in range(len(monster)):
        if monster[k][0]<=tmp+D:
            monster[k]=(monster[k][0],monster[k][1]-t2)
    count+=kai

print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from numpy import array
from math import ceil

N,D,A = [int(zz) for zz in input().split()]
li = [[int(zz) for zz in input().split()] for _ in range(N)]
li.sort()

X = [i[0] for i in li]
H = array([i[1] for i in li])

ans = 0
for i in range(N):
    if H[i] > 0:
        rind = bisect_right(X,X[i]+2*D)
        dmg = ceil(H[i]/A)*A
        ans += ceil(H[i]/A)
        H[i:rind] -= dmg

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n, d, a = map(int,input().split())
xlist=[]
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    xhlist.append([x, h])
    xlist.append(x)

xhlist=sorted(xhlist)
xlist=sorted(xlist)

now=0
turn=0

while now<n:
    swit=0
    pos=xhlist[now][0]+d
    atk=math.ceil(xhlist[now][1]/a)*a
    hani=bisect.bisect_right(xlist[now:], pos+d)
    hani+=now
    tasu=0
    turn+=atk//a
    for i in range(hani-now):
        if now+i<n:
            if xhlist[now+i][1]>0:
                xhlist[now+i][1]-=atk
            if swit==0:
                if xhlist[now+i][1]<=0:
                    tasu+=1
                else:
                    swit=1
    now+=tasu
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

data = []
for _ in range(N):
	x, h = map(int, input().split())
	heappush(data, (x, 0, h))

total = 0
height = 0
while data:
	x, type, h = heappop(data)
	if type == 0:
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			heappush(data, (x + D * 2, 1, count * A))
	else:
		height -= h

print(total)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
MONSTER = 1
END = 2
q = [ (XH[i][0], MONSTER, XH[i][1]) for i in range(N)]
heapify(q)
ans = 0
d = 0
while q:
    x, s, h = heappop(q)
    if s == MONSTER:
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            ans += k
            heappush(q, (x+2*D,END,k*A))
            d += k*A
    else: # END
        d -= h
print(ans)