TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt
		S[i+1] += tmp
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= tmp

print(ans)

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

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

atack = np.zeros(N+1)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

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

atack = np.zeros(N+1, np.int64)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque
n,d,a=map(int,input().split())
xh=[map(int,input().split()) for _ in range(n)]
xh.sort()
D=2*D
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-h%a)//a
    damage=a*nim
    ans+=num
    total+=damage
    q.append([x+D,damage])
print(ans)

from collections import deque
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-1//a)+1
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)


from collections import deque
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-1)//a+1
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)


Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque
n, d, a = map(int, input().split())

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

print(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    while dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
        else:
            break
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)


from collections import deque
n, d, a = map(int, input().split())

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    while dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
        else:
            break
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#include <bits/stdc++.h>
using namespace std;

int main() {
long long ans = 0;
long long N,D,A;
cin >> N >> D >> A;
vector<vector<long long>> enemies(N, vector<long long> (2));
for (int i = 0; i < N; i++)
{
    cin >> enemies.at(i).at(0) >> enemies.at(i).at(1);
}
sort(enemies.begin(),enemies.end(),[](const vector<long long> &alpha,const vector<long long> &beta){return alpha[0] < beta[0];});

queue<vector<long long>> damage;
long long dmg = 0;
for (int i = 0; i < N; i++){
    long long x = enemies.at(i).at(0);
    long long h = enemies.at(i).at(1);
    if (damage.empty()){
        long long bomb = (h+A-1)/A;
        ans += bomb;
        dmg += bomb*A;
        damage.push({x+2*D,bomb});
    }
    else{
        while (!damage.empty()){
            vector<long long> vec;
            vec = damage.front();
            long long d = vec.at(0);
            long long bomb = vec.at(1);
            if (d < x){
                dmg -= bomb*A;
                damage.pop();
            }
            else{
                break;
            }
        }
        if (h > dmg){
            long long bomb = (h-dmg+A-1)/A;
            dmg += bomb*A;
            damage.push({x+2*D,bomb});
            ans += bomb;
        }
        
    }
}

cout << ans << endl;
}

N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
from collections import deque
damage = deque()
dmg = 0
for x,h in enemies:
    if len(damage) == 0:
        bomb = -(-h//A)
        damage.append([x+2*D,bomb])
        dmg += bomb*A
        ans += bomb
    else:
        while len(damage) > 0:
            d,bomb = damage.popleft()
            if x > d:
                dmg -= bomb*A
            else:
                damage.appendleft([d,bomb])
                break
        if h > dmg:
            bomb = -(-(h-dmg)//A)
            dmg += bomb*A
            damage.append([x+2*D,bomb])
            ans += bomb

print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
ans = 0
i = 0
while i < N:
    x, hp = monsters[i]
    if hp <= 0: continue
    i = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
print(ans)

from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
damage = [0] * (N+2)
ans = 0
for i, [x, hp] in enumerate(monsters, 1):
    damage[i] += damage[i-1]
    if damage[i] >= hp: continue
    hp -= damage[i]
    j = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
    dam = attack * A
    # imos's method
    damage[i] += dam
    damage[j] -= dam
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

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

N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

def calc(x,h):
    if 2*d >= x[-1]-x[0]:
        b = np.max(h)
        ans = b//a + min(1,b%a)
    else:
        ans1 = h[0]//a + min(1,h[0]%a)
        ans2 = h[-1]//a + min(1,h[-1]%a)
        ans = ans1 + ans2
        h[:np.searchsorted(x,x+2*d,side='right')] -= ans1*a
        h[np.searchsorted(x,x[-1]-2*d,side='left'):] -= ans2*a
        c = np.where(h > 0)[0]
        if len(c) > 0:
            x_ = x[c[0]:c[-1]+1]
            h_ = h[c[0]:c[-1]+1]
            ans += calc(x_,h_)
    
    return ans

print(int(calc(x,h)))

from collections import deque
from math import ceil

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

q = deque()
ans = 0
count = 0
total = 0
for x,h in xh:
    while q:
        if q[0][0] < x:
            total -= q.popleft()[1]
        else:
            break
    
    if total < ceil(h/a):
        count = ceil(h/a)-total
        ans += count
        total += count
        q.append((x+2*d,count))

print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque

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

# process
XH.sort()
print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
    
# output
print(ans)


import math

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

# process
XH.sort()
print(XH)

ans = 0
for i in range(N):
    x, h = XH[i]
    if h <= 0:
        continue

    XH[i][1] = 0
    ans += math.ceil(h/A)

    for j in range(i, N):
        xhj = XH[j]
        if xhj[0] <= x+D*2:
            if xhj[1] > 0:
                xhj[1] -= h
        else:
            break
    
    print(XH)

# output
print(ans)


from collections import deque

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

# process
XH.sort()
#print(XH)

ans = 0
dq = deque()
dam = 0
for x, h in XH:
    while dq:
        x2, h2 = dq[0]
        if x > x2:
            dam -= h2
            dq.popleft()
        else:
            break

    h -= dam
    if h <= 0:
#        print("x,h,dam: {},{},{}".format(x,h,dam))
        continue

    c = -(-h//A)
    ans += c
    d = A*c
    dam += d
    dq.append((x+D*2, d))
#    print("x,h,dam,ans,dq: {},{},{},{},{}".format(x,h,dam,ans,dq))
    
# output
print(ans)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque
N, D, A = list(map(int, input().split()))
D *= 2
pair_xh = [[-1, -1] for _ in range(N)]
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))

q_lim_d = deque() 
total = 0 
count = 0 
for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    while len(q_lim_d) and q_lim_d[0][0] < x: 
        total -= q[0][1]
        q_lim_d.pop()
    h -= total
    
    if h > 0: 
        times = int((h + A - 1) / A) 
        count += times
        damage = A * times
        total += damage
        q_lim_d.append([x+D, damage])
print(count)

from collections import deque
N, D, A = list(map(int, input().split()))
pair_xh = [[-1, -1] for _ in range(N)] 
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))
pair_xh.sort(key = lambda x: x[0]) 

q_lim_d = deque() 
total = 0 
count = 0 
for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    while len(q_lim_d) and q_lim_d[-1][0] < x: 
        total -= q_lim_d[-1][1]
        q_lim_d.pop()
    h -= total
    if h > 0: 
        times = (h + A - 1) // A 
        count += times
        damage = A * times
        total += damage
        q_lim_d.appendleft([x + 2 * D, damage])
print(count)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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) 
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


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = zip(*sorted(zip(m,m)))
    
    over = [-1]*N
    tmp=0
    for i in range(N):
      while(tmp<N and X[i]+D*2>=X[tmp]):
        tmp += 1
      over[i] = tmp
    reset = [0]*N
    
    ans = 0
    dam = 0
    for i in range(N):
      if i>0:
        reset[i] += reset[i-1]
      hp = H[i]-dam+reset[i]
      if hp > 0:
        bomb = (hp+A-1)//A
        ans += bomb
        dam += bomb * A
        if(over[i]<N):
          reset[over[i]] += bomb * A

    print(ans)

if __name__ == "__main__":
    main()


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
from math import ceil
from collections import deque

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

q = deque([])
s = 0

ans = 0
for i in range(N):
  print(q)
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)


from math import ceil
from collections import deque

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

q = deque([])
s = 0

ans = 0
for i in range(N):
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

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

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

import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  if h <= 0:
    continue
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
n, d, a = map(int, input().split())
x = []
h = []
for i in range(n):
    x_, h_ = map(int, input().split())
    x.append(x_)
    h.append(h_)
n_list = range(max(x))

count = 0
j = 0

for i in range(n):
    if x[i] > 0:
        print(h)
        s = x[i]
        bakuha = (h[i]//a)
        h[i] = 0
        count += bakuha
        if i < n-1:
            j = i+1
            while x[j] <= s+(2*d):
                h[j] -= bakuha*a
                if j < n-1:
                    j += 1
                    if h[j] <= 0:
                        h[j] = 0
                        break
                else:
                    break
print(count)



from collections import deque
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for i in range(n)]
xh.sort()
que = deque()
ans = 0
atk = 0
for x, h in xh:
    while que and que[0][0] <= x:
        atk -= que.popleft()[1]
    h -= a*atk
    if h <= 0:
        continue
    count = -(-h//a)
    ans += count
    atk += count
    que.append((x+2*d+1, count))
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N, D, A = map(int, input().split())
monster = []
for _ in range(N):
    x, h = map(int, input().split())
    h = h // A
    if h % A != 0:
        h += 1
    monster.append((x, h))

monster = sorted(monster, key=lambda x: [x[0], -x[1]])
rightest = monster[0][0] + D  
now_bakudan = monster[0][1]
ans = monster[0][1]

for x, h in monster:
    if x > rightest+D:  
        now_bakudan = 0
    if h > now_bakudan:
        ans += h-now_bakudan
        now_bakudan += h
        rightest = x+D

print(ans)


import math
from bisect import bisect_right
N, D, A = map(int, input().split())  
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)

import math
from bisect import bisect_right  

N, D, A = map(int, input().split())  
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, math.ceil(h/A)))
    X.append(x)

XH.sort()
X.sort()

now = 0
ans = 0
T = [0]*(N+1)  
for i in range(N):
    x, h = XH[i]  
    now -= T[i]  
    if now >= h:  
        continue
    else:
        ans += h - now  
        T[bisect_right(X, x+2*D)] += h - now  
        now = h  
print(ans)


Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def main():
    import sys
    from bisect import bisect
    M=10**12
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d+d)]+=t*a
        s-=t
    print(s)
main()

def main():
    import sys
    from bisect import bisect
    M=10**10
    b=sys.stdin.buffer
    n,d,a=map(int,b.readline().split())
    m=map(int,b.read().split())
    c=[0]*(n+1)
    z=sorted(x*M+h for x,h in zip(m,m))
    s=0
    for i,x in enumerate(z):
        h=x%M
        c[i]+=c[i-1]
        h-=c[i]
        t=-h//a
        if t>0:t=0
        c[i]-=t*a
        c[bisect(z,x+d+d)]+=t*a
        s-=t
    print(s)
main()

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

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

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
#  --*-coding:utf-8-*--

import math

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

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q))
        s += q
        t += q

print(t)
        
        


#  --*-coding:utf-8-*--

import math

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

Q = []
qIdx = 0
s = 0
t = 0

for (x, h) in XH:
    while qIdx < len(Q) and  Q[qIdx][0] < x:
        s -= Q[qIdx][1]
        qIdx += 1

    if s < h:
        q = int(math.ceil((h-s)/A))
        Q.append((x+2*D, q*A))
        s += q*A
        t += q

print(t)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from collections import deque
from math import ceil


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

ms = sorted([(pos, ceil(hp / a)) for pos, hp in [map(int, input().split()) for i in range(n)])
 
bombs = deque()
 
ans = 0
valid_bomb = 0
for pos, hp in ms:
  
  while que and que[0][0] < pos:
    bomb_border, bomb_cnt = bombs.popleft()
    valid_bomb -= bomb_cnt
  
  
  bomb_cnt = max(0, hp - valid_bomb)
  valid_bomb += bomb_cnt
  ans += bomb_cnt
  
  
  if bomb_cnt > 0:
    que.append([pos + d * 2, bomb_cnt])
 
print(ans)  


from collections import deque
from math import ceil


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

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])

bombs = deque()

ans = 0
valid_bomb = 0
for pos, hp in ms:
    
    while bombs and bombs[0][0] < pos:
        bomb_border, bomb_cnt = bombs.popleft()
        valid_bomb -= bomb_cnt
    
    
    bomb_cnt = max(0, hp - valid_bomb)
    valid_bomb += bomb_cnt
    ans += bomb_cnt
    
    
    if bomb_cnt > 0:
        bombs.append([pos + d * 2, bomb_cnt])
 
print(ans)    

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
def main():
    import sys
    from collections import deque
    read=sys.stdin.read
    readline=sys.stdin.readline
    
    n, d, a = map(int, readline().split())
    m = map(int, read().split())
    monsters = sorted(zip(m, m), key=itemgetter(0))
    
    bomb_area = deque([])
    bomb_power = deque([])
    total_damage = 0
    ans = 0
    for pos, hp in monsters:
        while bomb_area:
            area = bomb_area[0]
            if area < pos:
                bomb_area.popleft()
                power = bomb_power.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            rest = hp - total_damage
            count = rest // a + (rest % a != 0)
            ans += count
            power = a * count
            total_damage += power
            bomb_area.append(pos + 2 * d)
            bomb_power.append(power)
    print(ans)


if __name__ == '__main__':
    main()




import numpy as np
i8 = np.int64

def solve(X, H, D):
    xi = np.empty_like(X)
    hi = np.empty_like(H)
    p = 0
    N = X.shape[0]
    for i in range(1, N):
        if X[i] > X[i - 1]:
            xi[p] = X[i - 1]
            hi[p] = H[i - 1]
            p += 1
    xi[p] = X[N - 1]
    hi[p] = H[N - 1]
    p += 1
    area = 2 * D
    res = 0
    sum_right = 0
    sum_left = 0
    left = 0
    for i in range(p):
        while xi[i] - xi[left] > area:
            sum_left += hi[left]
            left += 1
        x = hi[i] - (sum_right - sum_left)
        if x > 0:
            res += x
            sum_right += x
            hi[i] = x
        else:
            hi[i] = 0
    return res


def main(X, H, D, A):
    arg = np.lexsort((H, X))
    X = X[arg]
    H = H[arg]
    H = (H - 1) // A + 1
    print(solve(X, H, D))


if __name__ == '__main__':
    stdin = np.fromstring(open(0).read(), np.int64, sep=' ')
    N, D, A = stdin[:3]
    XH = stdin[3:].reshape((-1, 2)).T
    ans = main(XH[0], XH[1], D, A)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import math
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for i in range(N)]
XH.sort(key=lambda x: x[0])
left = D
flag = True
count = 0
ans = 0
for i in range(N):
    print(count)
    
    if i == 0 or pos + D < XH[i][0]:
        pos = XH[i][0] + D
        count = math.ceil(XH[i][1] / A)
        XH[i][1] = 0
        ans += count
    else:
        XH[i][1] -= count*A
        if XH[i][1] > 0:
            pos = XH[i][0] + D
            count = math.ceil(XH[i][1] / A)
            XH[i][1] = 0
            ans += count
        else:
            continue

print(ans)


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

XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q and q[0][0] < x):
        c -= q[0][1]
        q.popleft()
    h -= c * A
    if h < 0:
        h = 0
    ans += math.ceil(h/A)
    c += math.ceil(h/A)

    q.append((x+2*D, math.ceil(h/A)))

print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys, heapq
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = [[int(_) for _ in input().split()] for _ in range(N)]
He = [[2 * x, h, 0] for x, h in XH]
heapq.heapify(He)
now = 0
ans = 0
while He:
    x, h, t = heapq.heappop(He)
    if t:
        now -= h
    else:
        if h - D * now > 0:
            diff = (h - now - 1) // A + 1
            now += diff
            ans += diff
            heapq.heappush(He, [x + 4 * D + 1, diff, 1])
print(ans)


import sys, heapq
input = sys.stdin.readline
N, D, A = [int(_) for _ in input().split()]
XH = [[int(_) for _ in input().split()] for _ in range(N)]
He = [[2 * x, h, 0] for x, h in XH]
heapq.heapify(He)
now = 0
ans = 0
while He:
    x, h, t = heapq.heappop(He)
    if t:
        now -= h
    else:
        if h - A * now > 0:
            diff = (h - A * now - 1) // A + 1
            now += diff
            ans += diff
            heapq.heappush(He, [x + 4 * D + 1, diff, 1])
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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(cnt)

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

from math import ceil
from bisect import bisect_right
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
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()

damege_sum = 0
ans = 0
q = []
for i in range(N):
    x, h = monsters[i]
    while q:
        if q[0][0] < x:
            damege_sum -= q[0][1]
            q.pop(0)
    h -= damege_sum
    if h > 0:
        hit = -(-h // A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)




from math import ceil
from collections import deque


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


damage_sum = 0
ans = 0
q = deque([])
for i in range(N):
    x, h = monsters[i]
    while q and q[0][0] < x:
        damage_sum -= q[0][1]
        q.popleft()
    h -= damage_sum
    if h > 0:
        hit = ceil(h / A)
        ans += hit
        damage = hit * A
        damage_sum += damage
        q.append((x + 2 * D, damage))

print(ans)


Verdicts: Time Limit Exceeded

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
n,d,a=map(int,input().split())
flag=np.zeros(10**9+1)
XH=[list(map(int,input().split())) for _ in range(n)]
XH.sort(key=lambda A:A[0])
cnt=0
for i in range(n):
    kaisu=0
    x,h=XH[i]
    if flag[x]==0:
        kaisu=(h+a-1)//a
        flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
        cnt+=kaisu
    else:
        if flag[x]<h:
            h-=flag[x]
            kaisu=(h+a-1)//a
            flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
            cnt+=kaisu
print(cnt)

from heapq import heappush, heappop

n, d, a = map(int, input().split())
actions = []
for _ in range(n):
    x, h = map(int, input().split())
    heappush(actions, (x, 0, (h + a - 1) // a))
cnt = 0
bomb = 0
current_bomb = 0
while cnt < n:
    a, c, b = heappop(actions)
    if c:
        current_bomb -= b
        continue
    else:
        HP = b
        if HP <= current_bomb:
            cnt += 1
            continue
        else:
            HP -= current_bomb
            cnt += 1
            current_bomb += HP
            bomb += HP
            heappush(actions, (a + 2 * d, 1, HP))
print(bomb)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x: x[0])
damage = [0]*N

ans = 0
i = 0
while True:
    alive = True
    for j in range(i, N):
        x, h = XH[j]
        if h-damage[j] <= 0:
            continue
        i = j
        pos = x
        explode = (h + A - 1) // A
        break
    else:
        alive = False
        break

    if not alive:
        break

    for j in range(i, N):
        x, _ = XH[j]
        if x <= pos+2 * D:
            damage[j] += explode * A
        else:
            break
    ans += explode

print(ans)


import sys
from collections import deque
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
memo = deque()
cnt = 0
for x, h in XH:
    while memo and memo[0][0] < x:
        _, i = memo.popleft()
        cnt -= i
    h -= cnt * A
    h = max(h, 0)
    bomb = (h + A - 1) // A
    ans += bomb
    cnt += bomb
    memo.append((x + 2 * D, bomb))

print(ans)

Verdicts: Wrong Answer

Accepted