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 as np

def main():
    N,D,A = map(int, input().split())
    enemy = np.zeros((2,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h
    enemy = enemy[:, np.argsort(enemy[0,:])]

    damagemgr = np.zeros((1,2))
    ans = 0
    for i in range(N):
        x,h = map(int, enemy[:,i])
        #print("enm",x,h)
        for dm in damagemgr:
            #print("dm",dm)
            if x > int(dm[1]) : h += int(dm[0])
        #print(h)
        if h > 0:
            atack = int( (h + A - 1)/A )
            ans += atack
            damage = atack * A
            #print("atk",h,atack,damage)
            damagemgr = np.vstack( (damagemgr, [damage,x+2*D] ) )
            enemy[1,:] -= damage
        #print("")

    """
    while sum( (enemy[1,:]>0) )  :
        #print(enemy)
        atack = int( (enemy[1,0] + A - 1)/A )
        ans += atack
        damage = atack * A
        #print("damage",damage)
        for d_range in range(enemy.shape[1]):
            if enemy[0,d_range] > enemy[0,0] + 2*D : break
        if d_range == enemy.shape[1]-1 and enemy[0,-1] <= enemy[0,0] + 2*D : d_range += 1
        #print("d_range",d_range)
        enemy[1,:d_range] -= damage

        for survive in range(enemy.shape[1]):
            if enemy[1,survive] > 0: break
        enemy = enemy[:,survive:]
        #print("survive",survive,ans)
    """

    print(ans)
    return


"""
def old0208():
    N,D,A = map(int, input().split())
    enemy = np.zeros((3,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h, int(h/A) + (h%A>0)

    farest = int(enemy[0].max()+1)
    enemylist = [0]*farest
    for i in range(N):
        enemylist[ int(enemy[0,i]) ] = enemy[2,i]
    
    ans = 0
    while sum(enemylist)>0:
        pos = [0]*farest
        for i in range(farest):
            pos[i] = sum(enemylist[i-D:i+D+1])
        bestpos = pos.index(max(pos))
        for i in range(bestpos-D,bestpos+D+1):
            if enemylist[i]>0: enemylist[i] = enemylist[i]-1
        ans += 1

    print(ans)
    return
"""

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N,D,A = map(int, input().split())
    enemy = np.zeros((2,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h
    enemy = enemy[:, np.argsort(enemy[0,:])]

    ans = 0
    while sum( (enemy[1,:]>0) )  :
        #print(enemy)
        atack = int( (enemy[1,0] + A - 1)/A )
        ans += atack
        damage = atack * A
        #print("damage",damage)
        for d_range in range(enemy.shape[1]):
            if enemy[0,d_range] > enemy[0,0] + 2*D : break
        if d_range == enemy.shape[1]-1 and enemy[0,-1] <= enemy[0,0] + 2*D : d_range += 1
        #print("d_range",d_range)
        enemy[1,:d_range] -= damage

        for survive in range(enemy.shape[1]):
            if enemy[1,survive] > 0: break
        enemy = enemy[:,survive:]
        #print("survive",survive,ans)

    print(ans)
    return


"""
def old0208():
    N,D,A = map(int, input().split())
    enemy = np.zeros((3,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h, int(h/A) + (h%A>0)

    farest = int(enemy[0].max()+1)
    enemylist = [0]*farest
    for i in range(N):
        enemylist[ int(enemy[0,i]) ] = enemy[2,i]
    
    ans = 0
    while sum(enemylist)>0:
        pos = [0]*farest
        for i in range(farest):
            pos[i] = sum(enemylist[i-D:i+D+1])
        bestpos = pos.index(max(pos))
        for i in range(bestpos-D,bestpos+D+1):
            if enemylist[i]>0: enemylist[i] = enemylist[i]-1
        ans += 1

    print(ans)
    return
"""

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,D,A = map(int,input().split())
data = []
for i in range(N):
    X,H = map(int,input().split())
    if H % A == 0:
        data.append([X,H//A])
    else:
        data.append([X,H//A + 1])

data.sort()

X = []
H = []
for i in range(N):
    X.append(data[i][0])
    H.append(data[i][1])

count = 0
for i in range(N):
    if H[i] <= 0:
        continue
    count += H[i]
    p = bisect.bisect_left(X,X[i]+2*D+1)
    for j in range(i+1,min(p,N)):
        H[j] -= H[i]

print(count)

Submission status: Time Limit Exceeded

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


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

XH = []
for _ in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()

X, H = [], []
for x, h in XH:
    X.append(x)
    H.append(h)
H = np.array(H)

answer = 0
for i in range(n):
    if H[i] <= 0:
        continue
    j = bisect.bisect(X, X[i] + 2 * d)
    bomb = math.ceil(H[i] / a)
    H[i:j] -= a * bomb
    answer += bomb

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
mon = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    mon[i][1] = -(-mon[i][1]//a)
mon.sort()
ans = 0
for i in range(n):
    if mon[i][1] <= 0:
        continue
    ans += mon[i][1]
    j = i + 1
    while j < n and mon[j][0] <= mon[i][0] + 2 * d:
        mon[j][1] -= mon[i][1]
        j += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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):
    xh[i][1] = math.ceil(xh[i][1]/a)
    
while xh:
    x, h = xh.pop()
    if h <= 0:continue

    for i in range(len(xh)):
        if  xh[-1-i][0] >= x - 2 * d:
            xh[-1-i][1] -= h
        else:break
    
    ans += h

print(ans)

Submission status: Time Limit Exceeded

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

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = []
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            if 0 < H:
                attack_count = H // -A * -1
                damege = A * attack_count
                ans += attack_count
                XHN[i][1] -= damege

                acc_damege += damege
                q.append((bomb_p, damege))

    print(ans)


main()

Submission status: Time Limit Exceeded

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

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    ans = 0
    for i in range(N):
        while 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]
            attack_count = H // -A * -1
            ans += attack_count
            for j in range(i, N):
                if XHN[j][0] <= bomb_p:
                    XHN[j][1] -= attack_count * A
                else:
                    break

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,d,a = mi()
lis = []
for  i in range(n):
    x,h = mi()
    h = (h + a - 1) // a
    lis.append([x,h])

lis.sort()
dis = []
hp = []
for i in range(n):
    dis.append(lis[i][0])
    hp.append(lis[i][1])
#bit
class BIT():
    """区間加算、区間取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_sum: 区間[l, r)の和を求める
    l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit0 = [0] * (n + 1)
        self.bit1 = [0] * (n + 1)

    def _add(self, bit, i, val):
        i = i + 1
        while i <= self.n:
            bit[i] += val
            i += i & -i

    def _get(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(self.bit0, l, -val * l)
        self._add(self.bit0, r,  val * r)
        self._add(self.bit1, l,  val)
        self._add(self.bit1, r, -val)

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._get(self.bit0, r) + r * self._get(self.bit1, r) \
               - self._get(self.bit0, l) - l * self._get(self.bit1, l)

import bisect
hp_now = 0
dis_now = 0

ans = 0
bit = BIT(n+1)
for i in range(n):
    diff = hp[i] - bit.get_sum(i+1,i+2)
    if diff > 0:
        ans += diff
        migi = bisect.bisect_right(dis,dis[i] + 2 *d)
        bit.add(1,migi+1,diff)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np


def get_min_index(sorted_monsters):
    for index, m in enumerate(sorted_monsters):
        if m[1] > 0:
            return index
    return -1


def attack_monster(x, d, a, sorted_monsters):
    max_x = x + d * 2
    attack_count = math.ceil(sorted_monsters[0][1] / a)
    damage = a * attack_count
    sorted_monsters[sorted_monsters[:, 0] <= max_x, 1] -= damage
    return attack_count


if __name__ == '__main__':
    # a = int(input())
    # a, b = map(int, input().split())

    n, d, a = map(int, input().split())
    # monsters = []
    monsters = np.zeros(shape=(n, 2), dtype=int)
    for i in range(n):
        # x, h = map(int, input().split())
        # monsters.append((x, h))
        monsters[i][0], monsters[i][1] = map(int, input().split())
    sorted_monsters = monsters[np.argsort(monsters[:, 0])]
    attack_count = 0
    while len(sorted_monsters) > 0:
        attack_count += attack_monster(sorted_monsters[0][0], d, a, sorted_monsters)
        sorted_monsters = sorted_monsters[sorted_monsters[:, 1] > 0]

    print(attack_count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
for i, (x, h) in enumerate(xh):
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Time Limit Exceeded

Solution code:
import math


def get_min_index(sorted_monsters):
    for index, m in enumerate(sorted_monsters):
        if m[1] > 0:
            return index
    return -1


def attack_monster(x, d, a, sorted_monsters):
    max_x = x + d * 2
    attack_count = math.ceil(sorted_monsters[0][1] / a)
    damage = a * attack_count
    for index, m in enumerate(sorted_monsters):
        if m[0] > max_x:
            break;
        sorted_monsters[index] = (m[0], m[1] - damage)
    return attack_count


if __name__ == '__main__':
    # a = int(input())
    # a, b = map(int, input().split())

    n, d, a = map(int, input().split())
    monsters = []
    for i in range(n):
        x, h = map(int, input().split())
        monsters.append((x, h))
    sorted_monsters = list(sorted(monsters))
    attack_count = 0
    min_index = get_min_index(sorted_monsters)
    while min_index != -1:
        attack_count += attack_monster(sorted_monsters[0][0], d, a, sorted_monsters)
        min_index = get_min_index(sorted_monsters)
        sorted_monsters = sorted_monsters[min_index:]

    print(attack_count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
for i in range(N):
  x, h = xh[i]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  h -= ds[i]
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = ceil(h / a)
    xh[i][1] -= num * a
    for j in range(i + 1, len(xh)):
        if xh[j][0] > x + 2 * d:
            break
        if xh[j][1] > 0:
            xh[j][1] -= num * a
    cnt += num
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = h // a
    if h % a != 0:
        num += 1
    xh[i][1] -= num * a
    for j in range(i + 1, len(xh)):
        if xh[j][0] > x + 2 * d:
            break
        if xh[j][1] > 0:
            xh[j][1] -= num * a
    cnt += num
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from bisect import bisect_right
n, d, a = map(int, input().split())
l = []
l2 = []
l3 = []
ans = 0
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])
  l2.append(x + 2 * d)
  l3.append(x)
l.sort(key=lambda x: x[0])
l2.sort()
l3.sort()
for i in range(n):
  if l[i][1] == 0:
    continue
  else:  
    cnt = ceil(l[i][1] / a)
    ans += cnt
    ind = bisect_right(l3, l2[i])
    for j in range(i, ind):
      l[j][1] = max(0, l[j][1] - a * cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = h // a
    if h % a != 0:
        num += 1
    xh[i][1] -= num * a
    lis = []
    for j in range(i + 1, len(xh)):
        if xh[j][1] > 0 and xh[j][0] <= x + 2 * d:
            xh[j][1] -= num * a
    cnt += num
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    r = bisect(x, x[i]+2*D)
    for j in range(i+1, r):
      if j>N-1:break
      h[j] = h[j]-h_int*A

print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    r = bisect(x, x[i]+2*D)
    for j in range(i+1, r):
      if j>N-1:break
      h[j] = h[j]-h_int*A

print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]<=0: continue
    cnt+=h_int[i]
    r = bisect(x, x[i]+2*D)
    h_int[i+1:r] = h_int[i+1:r]-h_int[i]

print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, d, a = (int(x) for x in input().split())
xh = np.empty((0, 2))
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh = np.vstack((xh, np.array([x, h])))
xh = xh[np.argsort(xh[:, 0])]
cnt = 0
while True:
    if xh[xh[:, 1] > 0].size == 0:
        break
    xx, hh = xh[(xh[:, 1] > 0)][0]
    num = hh // a
    if hh % a != 0:
        num += 1
    xh[(xh[:, 0] >= xx) & (xh[:, 0] <= xx + 2 * d), 1] -= num * a
    cnt += num
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
while 1:
  if all(xh[:, 1]<=0):
    break
  x, h = xh[0]
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[1:]
  b += times
print(b)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
b = 0
c = 0
while 1:
  if all(xh[:, 1]<=0):
    break
  x, h = xh[c]
  c += 1
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[np.where(xh[:, 0]<=r, True, False)] -= times*A
  b += times
print(b)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect
N, D, A = map(int, input().split())
enemies = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
d_enemy = [enemy[0] for enemy in enemies]
b_left = bisect.bisect_left
logs = []
ans = 0
for i, enemy in enumerate(enemies):
    X, hp = enemy
    count = 0
    for log in logs:
        start, end, log_count = log
        if start <= X <= end:
            count += log_count
    hp -= count * A
    if hp > 0:
        attack_num = (hp + A-1) // A
        logs.append((X, X+2*D, attack_num))
        ans += attack_num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
  print('hoge')

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

X = [monsters[i][0] for i in range(N)]
H = [monsters[i][1] for i in range(N)]

number = 0
for i in range(N):
	if H[i] > 0:
		num = math.ceil(H[i] / A)
		number += num
		H = [H[j]-num*A if X[j] <= X[i]+2*D else H[j] for j in range(N)]
		#print(H)
	else:
		pass

print(number)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

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

monsters = np.array(sorted(monsters))

X = monsters[:, 0]
H = monsters[:, 1]

number = 0
for i in range(N):
	if H[i] > 0:
		num = math.ceil(H[i] / A)
		number += num
		H = [H[j]-num*A if X[j] <= X[i]+2*D else H[j] for j in range(N)]
		#print(H)
	else:
		pass

print(number)

Submission status: Time Limit Exceeded

Solution code:
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]

#print(r,hp)
i,ans=0,0
while i<n:
  #print(i)
  s=hp[i]
  #print(s)
  if s>0:
    cnt=(s+a-1)//a
    #print(cnt)
    ans+=cnt
    damage=cnt*a
    #print(damage)
    for j in range(i,min(bisect(r,r[i]+2*d),n)):
      hp[j]-=damage
  #print(hp)
  i+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, d, a = map(int, input().split())
xh = np.array(sorted(tuple(map(int, input().split())) for _ in range(n)))
x, h = xh[:, 0], xh[:, 1]

b, r = [], 1
for l in range(n):
    while r < n and x[l]+2*d >= x[r]:
        r += 1
    b.append(slice(l,r))

bt = 0
for i in range(n):
    if h[i] > 0:
        t = -(-int(h[i])//a)
        h[b[i]] = np.maximum(h-a*t, 0)[b[i]]
        bt += t

print(bt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, d, a = map(int, input().split())
xh = np.array(sorted(tuple(map(int, input().split())) for _ in range(n)))
x, h = xh[:, 0], xh[:, 1]

b = 0
while any(h):
    l = np.zeros(n)
    for i in range(n):
        s = np.where((x[i] <= x) & (x <= x[i]+2*d))
        l[i] = np.sum(np.minimum(h[s], a))
    if len(set(l)) == 1:
        b += -sum((-h//a).tolist())
        h = np.zeros_like(h)
    else:
        ind = np.argmax(l)
        h = np.where((x[ind] <= x) & (x <= x[ind]+2*d), np.maximum(h-a, 0), h)
        b += 1

print(b)

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    while i <= len(bit):
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


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

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    while i <= len(bit):
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


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

XH.sort()
result = 0
bit = [0] * (N + 1)
for i in range(N):
    x, h = XH[i]
    h -= bit_sum(bit, i)
    if h <= 0:
        continue
    c = (h + A - 1) // A
    result += c
    bit_add(bit, i, c * A)

    ok = i
    ng = N
    while ng - ok != 1:
        m = ok + (ng - ok) // 2
        if XH[m][0] <= x + 2 * D:
            ok = m
        else:
            ng = m
    bit_add(bit, ng, -c * A)
print(result)

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()
q = []
t = 0
result = 0
for x, h in XH:
    while q:
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h <= 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    
    N, D, A = (int(i) for i in input().split())
    XH = [0]*N
    for i in range(N):
        XH[i] = tuple(int(j) for j in input().split())
    XH.sort()

    BOMB = [0]*N
    for i in range(N):
        boundary = XH[i][0]+2*D
        for k in range(i, N):
            if XH[k][0]> boundary:
                k = k-1
                break
        BOMB[i] = k

    count = 0
    for i in range(N):
        local_count = int(math.ceil(XH[i][1]/A))
        if local_count > 0:
            count+=local_count
            damage = local_count*A
            for j in range(i, BOMB[i]+1):
                XH[j] = (XH[j][0],XH[j][1] - damage)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    
    N, D, A = (int(i) for i in input().split())
    XH = [0]*N
    for i in range(N):
        XH[i] = list(int(j) for j in input().split())
    XH.sort()

    BOMB = [0]*N
    for i in range(N):
        boundary = XH[i][0]+2*D
        for k in range(i, N):
            if XH[k][0]> boundary:
                k = k-1
                break
        BOMB[i] = k

    count = 0
    for i in range(N):
        local_count = int(math.ceil(XH[i][1]/A))
        if local_count > 0:
            count+=local_count
            for j in range(i, BOMB[i]+1):
                XH[j][1] -= local_count*A

    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def unzip(li):
    return map(list, zip(*li))

N, D, A = (int(i) for i in input().split())
XH = [0]*N
for i in range(N):
    XH[i] = list(int(j) for j in input().split())
XH.sort()

X, H = unzip(XH)

BOMB = [0]*N
for i in range(N):
    boundary = X[i]+2*D
    for k in range(i, N):
        if X[k]> boundary:
            k = k-1
            break
    BOMB[i] = k
    
count = 0
for i in range(N):
    local_count = int(math.ceil(H[i]/A))
    if local_count > 0:
        count+=local_count
        for j in range(i, BOMB[i]+1):
            H[j] -= local_count*A
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = (int(i) for i in input().split())
XH = [0]*N
for i in range(N):
    XH[i] = list(int(j) for j in input().split())
XH.sort()

BOMB = [0]*N
for i in range(N):
    for k in range(i, N):
        if XH[k][0]>XH[i][0]+2*D:
            k = k-1
            break
    BOMB[i] = k
    
count = 0
for i in range(N):
    while XH[i][1]>0:
        count+=1
        for j in range(i, BOMB[i]+1):
            XH[j][1] -= A
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect, math
N,D,A = map(int,input().split())
enemy = list(list(map(int,input().split()))for i in range(N))
enemy.sort()

damege = [0]*N

ans = 0
p = 0
while p < N:
    if p>=1:
        damege[p] += damege[p-1]
    enemy[p][1] -= damege[p]
    if enemy[p][1] <= 0:
        p += 1 
        continue
    d = math.ceil(enemy[p][1]/A)
    ans += d
    d *= A
    r = bisect.bisect_right(enemy,[enemy[p][0]+D*2,10**9+7])
    if r!=N:
        damege[r]-=d
    damege[p] += d
    p+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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):
    count = math.ceil(xh[i][1] / a)
    if not count:
        continue

    ans += count
    for j in range(i + 1, n):
        if xh[j][0] > xh[i][0] + 2 * d:
            break
        else:
            if xh[j][1] - count * a > 0:
                xh[j][1] -= count * a
            else:
                xh[j][1] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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):
    count = math.ceil(xh[i][1] / a)
    if not count:
        continue

    ans += count
    for j in range(i + 1, n):
        if xh[j][0] <= xh[i][0] + 2 * d:
            if xh[j][1] - count * a > 0:
                xh[j][1] -= count * a
            else:
                xh[j][1] = 0
print(ans)

Submission status: Time Limit Exceeded

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

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N, int)
answer = 0
 
for i in range(N):
    if H[i] <= 0:
        continue
    else:
        J = (H[i]-1+A)//A
        damage[i] = J*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -J*A
    damage = np.cumsum(damage)
    answer += J
    H -= damage
    damage[i:a] = 0
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())

#output
import numpy as np
import bisect as bi

X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]

damage = np.zeros(N, int)
answer = 0

for i in range(N):
    if H[i] <= 0:
        continue
    else:
        J = (H[i]-1+A)//A
        damage[i] = J*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -J*A
    damage = np.cumsum(damage)
    answer += J
    H -= damage
    damage[i:a] = 0

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())

#output
import numpy as np
import bisect as bi

X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]

answer = 0

for i in range(N):
    damage = np.zeros(N, int)
    if H[i] <= 0:
        continue
    else:
        damage[i] = ((H[i]-1+A)//A)*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -((H[i]-1+A)//A)*A
    damage = np.cumsum(damage)
    answer += (H[i]-1+A)//A
    H -= damage

print(answer)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,D,A=map(int,input().split())
XH=[]
for i in range(N):
    XH.append(list(map(int,input().split())))

XH.sort()

bombs=[]
damage=0
ans=0

for i in range(N):
    if bombs:
        while bombs[0][1]<XH[i][0]:
            b=bombs.pop(0)
            damage-=b[0]
            if not(bombs):
                break
    
    hp=XH[i][1]-damage
    num_b=-(-hp//A)
    num_b=max(num_b,0)
    bom_d=A*num_b
    bom_l=XH[i][0]+2*D
    if num_b>0:
        bombs.append([bom_d,bom_l])
        damage+=bom_d
    ans+=num_b

print(ans)