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: Runtime Error

Solution code:
import math


def get_inputs():
    inputs = input().split(" ")
    monsters_num, diff, attack = int(inputs[0]), int(inputs[1]), int(inputs[2])
    monsters = []
    for monster in range(monsters_num):
        inputs = input().split(" ")
        coordinate, health = int(inputs[0]), int(inputs[1])
        monsters.append({"coordinate": coordinate, "health": health})
    return monsters, diff, attack, monsters_num


def between_coordinates(monster, coordinate, diff):
    if (coordinate - diff <= monster["coordinate"] <= coordinate) or (
            coordinate <= monster["coordinate"] <= coordinate + diff):
        return True
    return False


def sort_monsters_coordinates(monsters):
    return sorted(monsters, key=lambda k: k['coordinate'])


def get_alive_monsters(monsters):
    return [monster for monster in monsters if monster["health"] > 0]


def attack_leftmost_monster(coordinate, monsters, attack, diff):
    bombs_num = 0
    if len(monsters) == 0:
        return 0
    leftmost_monster = monsters.pop(0)
    needed_attacks = math.ceil(leftmost_monster["health"] / attack)
    bombs_num += needed_attacks
    for monster in monsters:
        if between_coordinates(monster, coordinate, diff):
            monster["health"] -= (needed_attacks * attack)
    monsters = get_alive_monsters(monsters)
    return monsters, bombs_num


def get_max_health(monsters):
    if len(monsters) == 0:
        return 0

    max_health = - math.inf
    for monster in monsters:
        if monster["health"] >= max_health:
            max_health = monster["health"]
    return max_health


monsters, diff, attack, monsters_num = get_inputs()
if len(monsters) > 0:
    monsters = sort_monsters_coordinates(monsters)
else:
    print(0)

coordinate = monsters[0]["coordinate"] + diff
total_bombs_num = 0

while len(monsters) > 0 and coordinate < monsters[-1]["coordinate"]:
    monsters, bombs_num = attack_leftmost_monster(coordinate, monsters, attack, diff)
    total_bombs_num += bombs_num
    if monsters and monsters[0]["coordinate"] + diff <= monsters[-1]["coordinate"]:
        coordinate = monsters[0]["coordinate"] + diff
    else:
        break
        
print(total_bombs_num + math.ceil(get_max_health(monsters) / attack))

Submission status: Runtime Error

Solution code:
import math


def get_inputs():
    inputs = input().split(" ")
    monsters_num, diff, attack = int(inputs[0]), int(inputs[1]), int(inputs[2])
    monsters = []
    for monster in range(monsters_num):
        inputs = input().split(" ")
        coordinate, health = int(inputs[0]), int(inputs[1])
        monsters.append({"coordinate": coordinate, "health": health})
    return monsters, diff, attack, monsters_num


def between_coordinates(monster, coordinate, diff):
    if (coordinate - diff <= monster["coordinate"] <= coordinate) or (
            coordinate <= monster["coordinate"] <= coordinate + diff):
        return True
    return False


def sort_monsters_coordinates(monsters):
    return sorted(monsters, key=lambda k: k['coordinate'])


def get_alive_monsters(monsters):
    return [monster for monster in monsters if monster["health"] > 0]


def attack_leftmost_monster(coordinate, monsters, attack, diff):
    bombs_num = 0
    if len(monsters) == 0:
        return 0
    leftmost_monster = monsters.pop(0)
    needed_attacks = math.ceil(leftmost_monster["health"] / attack)
    bombs_num += needed_attacks
    for monster in monsters:
        if between_coordinates(monster, coordinate, diff):
            monster["health"] -= (needed_attacks * attack)
    monsters = get_alive_monsters(monsters)
    return monsters, bombs_num


def get_max_health(monsters):
    if len(monsters) == 0:
        return 0

    max_health = - math.inf
    for monster in monsters:
        if monster["health"] >= max_health:
            max_health = monster["health"]
    return max_health


monsters, diff, attack, monsters_num = get_inputs()
if len(monsters) > 0:
    monsters = sort_monsters_coordinates(monsters)
else:
    print(0)

coordinate = monsters[0]["coordinate"] + diff
total_bombs_num = 0

while len(monsters) > 0 and coordinate < monsters[-1]["coordinate"]:
    monsters, bombs_num = attack_leftmost_monster(coordinate, monsters, attack, diff)
    total_bombs_num += bombs_num
    if monsters and monsters[0]["coordinate"] + diff <= monsters[-1]["coordinate"]:
        coordinate = monsters[0]["coordinate"] + diff
print(total_bombs_num + math.ceil(get_max_health(monsters) / attack))

Submission status: Runtime Error

Solution code:
import math


def get_inputs():
    inputs = input().split(" ")
    monsters_num, diff, attack = int(inputs[0]), int(inputs[1]), int(inputs[2])
    monsters = []
    for monster in range(monsters_num):
        inputs = input().split(" ")
        coordinate, health = int(inputs[0]), int(inputs[1])
        monsters.append({"coordinate": coordinate, "health": health})
    return monsters, diff, attack, monsters_num


def between_coordinates(monster, coordinate, diff):
    if (coordinate - diff <= monster["coordinate"] <= coordinate) or (coordinate <= monster["coordinate"] <= coordinate + diff):
        return True
    return False


def sort_monsters_coordinates(monsters):
    return sorted(monsters, key=lambda k: k['coordinate']) 


def get_alive_monsters(monsters):
    return [monster for monster in monsters if monster["health"] > 0]


def attack_leftmost_monster(coordinate, monsters, attack, diff):
    bombs_num = 0
    if len(monsters) == 0:
        return 0
    leftmost_monster = monsters.pop(0)
    needed_attacks = math.ceil(leftmost_monster["health"] / attack)
    bombs_num += needed_attacks
    for monster in monsters:
        if between_coordinates(monster, coordinate, diff):
            monster["health"] -= (needed_attacks * attack)
    monsters = get_alive_monsters(monsters)
    return monsters, bombs_num


def get_max_health(monsters):
    if len(monsters) == 0:
        return 0
    
    max_health = - math.inf
    for monster in monsters:
        if monster["health"] >= max_health:
            max_health = monster["health"]
    return max_health


monsters, diff, attack, monsters_num = get_inputs()
if len(monsters) > 0:
    monsters = sort_monsters_coordinates(monsters)
else:
    print(0)

coordinate = monsters[0]["coordinate"] + diff
total_bombs_num = 0

while len(monsters) > 0 and coordinate + diff < monsters[-1]["coordinate"]:
    monsters, bombs_num = attack_leftmost_monster(coordinate, monsters, attack, diff)
    total_bombs_num += bombs_num
    if monsters and monsters[0]["coordinate"] + diff <= monsters[-1]["coordinate"]:
        coordinate = monsters[0]["coordinate"] + diff
print(total_bombs_num + math.ceil(get_max_health(monsters) / attack))

Submission status: Runtime Error

Solution code:
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D

# これより手前までを減らす
end = bisect.bisect_right(X, last)

while True:
    need = counting(XH[begin][1])
    ans += need
    

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break
                elif j == N-1:
                    end = N
                    break
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    breake
                elif j == N-1:
                    end = N
                    break







"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Runtime Error

Solution code:
import math
from bisect import bisect_right
N, D, A = map(int, input().split())  # N体のモンスター, 爆弾の範囲D, 爆弾の威力A
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append(x, math.ceil(x/A))  # 座標と必要な爆弾の個数を格納する
    X.append(x)  # こっちは座標のみ, あとで座標を二分探索するときに使う
# 座標でソートする
XH.sort()
X.sort()
T = [0]*(N+1)
j = 0
now = 0
ans = 0
for i in range(N):
    x, h = XH[i]
    now -= T[i]
    if now >= h:
        continue
    else:
        T[bisect_right(X, x+D*2)] += h - now
        ans += h - now
        now = h
print(ans)

Submission status: Runtime Error

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

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

XH.sort()
print(XH)


for i in range(N):
    bit_add_sec(bit1, bit2, i, i, XH[i][1])


bit1 = [0] * (N + 1)
bit2 = [0] * (N + 1)

def bit_add(b, i, v):
    while i <= N:
        b[i] += v
        i += i & - i
        
def bit_sum(b, i):
    s = 0
    while i:
        s += b[i]
        i -= i & -i
    return s

def bit_add_sec(b1, b2, l, r, x):
    bit_add(b1, l, -x * (l - 1))
    bit_add(b2, l, x)
    bit_add(b1, r + 1, x * r)
    bit_add(b2, r + 1, -x)

def bit_sum_sec(b1, b2, l, r, x):
    res = 0
    res += bit_sum(b1, r) + bit_sum(b2, r) * r
    res -= bit_sum(b1, l - 1) + bit_sum(b2, l - 1) * (l - 1)
    return res

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
li = [N-1] * N
for i in range(N):
    u = N
    l = i
    while u - l > 1:
        m = (u+l)//2
        if X[m] - i > 2*D:
            u = m
        else:
            l = m
    li[i] = m
ans = 0
for i in range(N):
    x = X[i]
    if d[x] > 0:
        m = -(-d[x]//A)
        ans += m
        for j in range(i+1, li[i]+1):
            d[X[j]] -= m*A
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
ans = 0
for x in X:
    if d[x] > 0:
        m = -(-d[x]//A)
        ans += m
        for i in X:
            if x < xx <= x + 2*D:
                d[xx] -= m*A
            else:
                break
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import besect_left

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_left(X,X[i]+2*D+1)
    for j in range(i+1,min(p,N)):
        H[j] -= H[i]

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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())
    
T = np.zeros(max(X)+1)
for x, h in zip(X, H):
    T[x] = h

X.sort()
ans = 0

for i in X:
    if T[i] > 0:
        d = int((T[i]+A-1) // A)
        T[i:i+2*D+1] = T[i:i+2*D+1] - A*d
        ans += d

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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())
    
T = np.zeros(max(X)+2*D+1)
for x, h in zip(X, H):
    T[x] = h

X.sort()
ans = 0

for i in X:
    if T[i] > 0:
        d = int((T[i]+A-1) // A)
        T[i:i+2*D+1] = T[i:i+2*D+1] - A*d
        ans += d

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
def main():
    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: Runtime Error

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

monsters = []
for _ in range(n):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort(key=lambda x: x[0])
attack = 0

left_m, left_hp = monsters[0]
MAX_HP = left_hp
attacked = [False] * len(monsters)
for i in range(len(monsters)):
    cur_m, cur_hp = monsters[i]
    if cur_m - left_m <= d:
        MAX_HP = max(MAX_HP, cur_hp)
    else:
        attacked[:i + d] = [True] * (i + d)
        if MAX_HP % a == 0:
            attack += MAX_HP // a
        else:
            attack += MAX_HP // a + 1
        left_m, left_hp = monsters[i]

if not attacked[-1]:
    hp = monsters[-1][1]
    if hp % a == 0:
        attack += hp // a
    else:
        attack += hp // a + 1
print(attack)

Submission status: Runtime Error

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

import numpy as np

def main():
    N, D, A = map(int, input().split())
    x = [list(map(int, input().split())) for n in range(N)]
    x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]

    X = np.array(x[0])
    H = np.array(x[1])
    length = np.ptp(X) + 1
    hp = np.zeros(length, dtype='int')
    hp[X - min(X)] = H

    num_bomb = 0
    while True:
        num_attacks = -(-hp[0] // A)
        hp[0:2*D+1] -= num_attacks * A
        num_bomb += num_attacks
        if hp[0] <= 0:
            if hp[-1] <= 0:
                break
            l = np.argmax(hp > 0)
            hp = hp[l:]

    print(num_bomb)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, D, A = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]

import numpy as np
X = np.array(x[0])
H = np.array(x[1])
length = np.ptp(X) + 1
hp = np.zeros(length, dtype='int')
hp[X - min(X)] = H

num_bomb = 0
while True:
    hp[0:2*D+1] -= A
    num_bomb += 1
    if hp[0] == 0:
        if hp[-1] == 0:
            break
        l = np.argmax(hp > 0)
        hp = hp[l:]

print(num_bomb)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=int32)
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = h//A if h%A==0 else h//A+1
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Runtime Error

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
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[xh[:, 0]<=r] -= times*A
  b += times
print(b)

Submission status: Runtime Error

Solution code:
import math, deque
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())

x, h = zip(*sorted(list(zip(x, h))))
x, h = list(x), list(h)

l, r = 0, 1
m = [0] * n

while r < n:
    if x[r] - x[l] <= 2*d:
        r += 1
    else:
        m[l] = r-1
        l += 1
m[l:r] = [r-1]*(r-l)
m = deque(m)

l = 0
attcnt = deque([])
dam = 0
for i in range(n):
    if h[i] - dam < 1: 
        ac = 0
    else:
        if a == 1:
            ac = h[i] - dam
        else :
            ac = math.ceil(math.log(h[i]-dam, a))
        
    dam += ac * a
    attcnt.append(ac)
    
    while m and i == m[0]:
        m.popleft()
        dam -= attcnt[l]*a
        l += 1

print(sum(attcnt))

Submission status: Runtime Error

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] / D)
		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: Runtime Error

Solution code:
#include <iostream>
#include <map>
typedef int64_t int64;
using namespace std;



int main() {
	int64 n, d, a;
	cin >> n;
	cin >> d;
	cin >> a;
	map<int64, pair<int64, int64>> m;
	for (int64 i=0; i<n; i++) {
		int64 b, c;
		cin >> b;
		cin >> c;
		m[b] = {c, 0};
	}
	int64 destroy = 0;
	int64 bombs = 0;

	for (auto [x, values]: m) {
		auto [health, update] = values;
		health -= destroy;
		if (health > 0) {
			int64 times = (health-1) / a + 1;
			bombs += times;
			if (d==0) continue;
			destroy += times*a;
			if (m.count(x+2*d)) m[x+2*d] = {m[x+2*d].first, times};
			else m[x+2*d] = {0, times};	
		}
		destroy -= update*a;
	}
	cout << bombs;
	return 0;
			
}

Submission status: Runtime Error

Solution code:
n,d,a = map(int,input().split())
L = []
T = []
U = []
hitpoint = []
for i in range(n):
  p,q = map(int,input().split())
  L.append([p,q,0])
  T.append(p)
  U.append(p)
  hitpoint.append(q)
U.sort()
for i in range(n):
  k = bisect.bisect_right(U,T[i]+2*d)
  L[i][2] = k
L.sort()
start = 0
ans = 0
while start != n:
  t = hitpoint[start]//a
  if hitpoint[start]%a == 0:
    attack = t
  else:
    attack = t+1
  ans += attack
  cur = attack*a
  look = L[start][2]
  flag = False
  ne = 0
  for i in range(look-start):
    if start+i <= n-1:
      if (hitpoint[start+i] - cur <= 0):
        hitpoint[start+i] = 0
      else:
        if not flag:
          ne = i
          flag = True
        hitpoint[start+i] -= cur
  if ne == 0:
    start += 1
  else:
    start += ne
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #（攻撃が無効となる座標、攻撃によるポイント）
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break  #無効となる攻撃がない場合はwhileを終了
        end_x,end_point=q.popleft()
        attack_point-=end_point 　#攻撃が無効となる座標<=現在の座標があれば、その攻撃のポイントを引く

    if h<=attack_point: #モンスターの体力よりも攻撃で減らせるポイントの方が大きければ新規攻撃は不要
        pass
    else:   #新規攻撃が必要な場合
        if h%A==0:
            cnt=(h-attack_point)/A  #モンスターの大量をゼロ以下にするために何回攻撃が必要か
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))   #（攻撃が無効となる座標、攻撃によるポイント）をキューに入れる
        ans+=cnt

print ans

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque
    from operator import itemgetter
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    p,q=deque(),deque()
    pl,ql=p.popleft,q.popleft
    pa,qa=p.append,q.append
    s=b=0
    for x,h in sorted(zip(m,m),key=itemgetter(0)):
        while p and p[0]<x:
            f()
            b-=g()
        h-=b
        t=0--h//a
        if t>0:
            s+=t
            b+=t*a
            pa(x+d+d)
            qa(t*a)
    print(s)
main()

Submission status: Runtime Error

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=tuple(map(int,input().split()))
  l.append(k)
l.sort(key=itemgetter(0))
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i][0]
  for j in reversed(range(0,tmp)):
    if abs(l[j][0]-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0][1]/A)
for i in range(1,N):
  h=l[i][1]
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Runtime Error

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  x,h=map(int,input().split())
  l.append((x<<30)+h)
l.sort()
S=[0]*N
ma=[0]*N
tmp=N-1
for i in reversed(range(N)):
  x=l[i]>>30
  for j in reversed(range(0,tmp)):
    if abs(l[j]>>30-(x-D))>D:
      ma[i]=j+1
      tmp=j+1
      break
  else:
    ma[i]=0
    tmp=0
ans=0
S[0]=math.ceil(l[0]&(2**30-1)/A)
for i in range(1,N):
  h=l[i]&(2**30-1)
  left=S[ma[i]-1] if ma[i]>0 else 0
  right=S[i-1]
  sum_=(right-left)*A
  if h<=sum_:
    S[i]=S[i-1]
    continue
  time=math.ceil((h-sum_)/A)
  S[i]=time+S[i-1]
print(S[N-1])

Submission status: Runtime Error

Solution code:
from math import ceil
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
imos=[0]*(n+1)
x=[]
for i in range(n):
  x.append(xh[i][0])
ans,cnt=0,0
for i in range(n):
  cnt+=imos[i]
  hp=xh[i][1]-cnt*a
  if hp>0:
    cnt+=ceil(hp/a)
    ans+=ceil(hp/a)
  imos[bisect_right(x,x[i]+2*d)]-=ceil(hp/a)
print(ans)

Submission status: Runtime Error

Solution code:
import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [0 for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]
    rang[i] = x

num = 0
xh.sort(key=lambda xh:xh[0])]

dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        for j in range(i+1,n):
            if rang[j] <= pos + 2d:
                dam[j] += a*nat
            else:
                break
print(num)

Submission status: Runtime Error

Solution code:
import math

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

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(n):
            if math.fabs(xh[j][0]-pos) <= d:
                ###dam[j] += a*nat

print(num)

Submission status: Runtime Error

Solution code:
from math import *

n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max-1:n_max+n-1] = (h for _, h in p)

def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l and r <= b:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]
 
def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)
 

init2()
#for i, (_, h) in enumerate(p):
#  init(i, i+1, h)
c = 0
j = 0
import pdb; pdb.set_trace()
for i in range(n):
  
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j < n and p[j][0] - x <= 2 * d + 1:
    j += 1
  add(i, j, -m)
print(c)

Submission status: Runtime Error

Solution code:
from math import *

n, d, a = map(int, input().split())
n_max = 2**(ceil(log(n)/log(2)))
health = [0]*(n_max * 2 - 1)
lazy = [0]*(n_max * 2 -1)
p = sorted(tuple(map(int, input().split())) for _ in range(n))

health[n_max:n_max+n] = p
def init2(k=0, l=0, r=n_max):
  if r-l <= 1:
    return health[k]
  s = init2(2*k+1, l, (l+r)//2)
  s += init2(2*k+2, (l+r)//2, r)
  health[k] = s
  return s

def evalue(k, l, r):
  if not lazy[k]:
    return
  health[k] = max(health[k] + lazy[k], 0)
  if r - l > 1:
    lazy[2 * k + 1] = lazy[k] // 2
    lazy[2 * k + 2] = lazy[k] // 2
  lazy[k] = 0
 
def init(a, b, h, k=0, l=0, r=n_max):
  if b <= l or r <= a:
    return health[k]
  health[k] = health[k] + h
  if r - l <= 1:
    return health[k]
  vl = init(a, b, h, 2 * k + 1, l, (l + r) // 2)
  vr = init(a, b, h, 2 * k + 2, (l + r) // 2, r)
  health[k] = vl + vr
  return health[k]
  
def add(a, b, v, k=0, l=0, r=n_max):
  evalue(k, l, r)
  if b <= l or r <= a:
    return health[k]
  if a <= l and r <= b:
    lazy[k] += v * (r - l)
    evalue(k, l, r)
  else:
    vl = add(a, b, v, 2 * k + 1, l, (l + r) // 2)
    vr = add(a, b, v, 2 * k + 2, (l + r) // 2, r)
    health[k] = vl + vr
  return health[k]
 
def get(a, b, k=0, l=0, r=n_max):
  if (b <= l or r <=a):
    return 0
  evalue(k, l, r)
  if a <= l and r <= b: return health[k]
  vl = get(a, b, 2 * k + 1, l, (l + r) // 2)
  vr = get(a, b, 2 * k + 2, (l + r) // 2, r)
  return max(vl, vr)
 

init2()
#for i, (_, h) in enumerate(p):
#  init(i, i+1, h)
 
c = 0
j = 0
for i in range(n):
  x, _ = p[i]
  h = get(i, i+1)
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j >= n or p[j][0] - x > 2 * d + 1:
    j += 1
  add(i, j, -m)
print(c)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
import math
n,d,a=map(int,input().split())
X, H=[], []; ans=0; L=[]
for i in range(n):
  x,h=map(int,input().split())
  L.append((x,h))
L.sort()
for x,h in L:
  X.append(x); H.append(h)
X.append(10**9); H.append(10**9)
imos=[0]*(n+1)
de=0 # decrease count
for i in range(n):
  de+=imos[i]
  HP=H[i]-de*a
  # 右から貪欲にダメージを減らす
  # 敵の体力が残ってるとき
  # print("HP is",HP)
  if HP>0:
    atk_cnt=math.ceil(HP/a) # 何回殴る必要があるか
    de+=atk_cnt
    ans+=atk_cnt
    index=upper_bound(X,X[i]+2*d)
    # print(X,X[i]+2*d)
    # print(index, atk_cnt)
    imos[index]-=atk_cnt
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort(key=lambda x:x[0])

over = [N] * (N+1) # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur <= N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # 対象のモンスターの影響しなかったダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h = h - damage
    time = (h+A-1)//A
    answer += time
    damage += A * time
    reset[over[i]] += A * time

print(answer)
# 00