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: Wrong Answer

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])
print(xh)

while len(xh) > 0.5:
    nat = math.ceil((xh[0][1])/a)
    num += nat
    dam = nat*a
    for i in range(len(xh)):
        if xh[i][0] <= xh[0][0]+2*d:
            xh[i][1] -= dam
        else:
            break
    xh = [i for i in xh if i[1] > 0]

print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

num = 0
xh = xh[np.argsort(xh[:, 0])]

while xh.size > 0.5:
    if xh[0,1]%a == 0:
        nat = int((xh[0,1])/a)
    else:
        nat = int((xh[0,1])/a+1)
    num += nat
    dam = nat*a
    for i in range(xh.shape[0]):
        if xh[i,0] <= xh[0,0]+2*d:
            xh[i,1] -= dam
        else:
            break
    xh = xh[np.all(xh<0.5,axis=1)]

print(num)

Submission status: Wrong Answer

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

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1

print(ans)

Submission status: Wrong Answer

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

class segTree:
  inf = 10 ** 9
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
    s.D = [0] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def get(s, l, r):
    s.down(l)
    if l != r:
      s.down(r)
    return s.gets(l, r, 0, 0, s.N - 1)
  def gets(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.gets(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.gets(l, r , 2 * k + 1, kl, t)
    return s.do(s.gets(l, r , 2 * k + 1, kl,t),
              s.gets(l, r , 2 * k + 2, t + 1, kr))
  def add(s, l, r, v):
    s.adds(l, r, v, 0, 0, s.N - 1)
  def adds(s, l, r, v, k, kl, kr):
    if k >= 2 * s.N - 1: return
    if l <= kl and kr <= r:
      s.D[k] += v
      return
    if kl <= r and l <= kr:
      t = (kl + kr) // 2
      s.adds(l, r, v, 2 * k + 1, kl, t)
      s.adds(l, r, v, 2 * k + 2, t + 1, kr)
  def down(s, x):
    k, kl, kr = 0, 0, s.N - 1
    while True:
      v = s.D[k]
      s.T[k] += v
      s.D[k] = 0
      t = (kl + kr) // 2
      if 2 * k + 1 >= 2 * s.N - 1: return
      s.D[2 * k + 1] += v
      s.D[2 * k + 2] += v
      if x <= t:
        k = 2 * k + 1
        kr = t
      else:
        k = 2 * k + 2
        kl = t + 1

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

XH.sort()
H = [XH[i][1] for i in range(N)]

T = segTree(N)
T.set(H)

exit()

p = 0
ans = 0
for i in range(N):
  for j in range(p + 1, N):
    if XH[j][0] > XH[i][0] + D * 2:
      p = j - 1
      break
    else:
      p = N - 1
  t = (T.get(i, i) - 1) // A + 1
  if t <= 0: continue
  ans += t
  T.add(i, p, -t * A)

print(ans)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
from collections import deque

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        c = -(-dam//A)
        count += c
        aldam += c*A
        q.append([now+2*D,aldam])
    
    print(count)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
from collections import deque

def main():
    N,D,A = map(int,input().split())
    X = [tuple(map(int,input().split())) for _ in range(N)]
    
    X.sort(key=itemgetter(0))
    aldam = 0
    count = 0
    q = deque([])
    for now,dam in X:
        while q:
            if now <= q[0][0]:
                break
            aldam -= q[0][1]
            q.popleft()
        dam -= aldam
        if dam < 0:
            continue
        count += -(-dam//A)
        aldam += count*A
        q.append([now+2*D,aldam])
    
    print(count)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import math

#####segfunc######
def segfunc(x,y):    
    return x+y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0
#input
data = []
n, d, a = map(int, input().split())
x_point = []
for i in range(n):
    x, h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
x_point.sort()
data.sort()
##初期化
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
ans = 0
for i in range(n):
    x, h = data[i]
    index = bisect.bisect_left(x_point, x - 2*d)
    sum_damage = query(index, i)
    h -= sum_damage
    count = math.ceil(h/a)
    ans += count
    update(i, count * a)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

for i in range(N):
  X, H=XH[i]
  while len(q) and q[0][0]<X:
    total-=q.pop()[1]
  H-=total
  if H>0:
    attack_cnt=(H-1)//A+1
    ans+=attack_cnt
    damage=attack_cnt*A
    total+=damage
    q.append([X+2*D, damage])
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A = map(int,input().split())
XH = []
for _ in range(N):
  X,H = map(int,input().split())
  XH.append([X,H])
XH.sort()
counter = 0
for item in XH:
  damage = item[1]
  counter += item[1]//A
  for piece in XH:
    if piece[0] <= item[0]+2*D:
      piece[1] = max(0,piece[1]-damage)
print(counter)

Submission status: Wrong Answer

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

"""

3 3 2
9 2
1 2
5 4
ans 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5
ans 5

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000
ans 3000000000
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
n, d, a = map(int, input().split())
XH = np.array([tuple(map(int, input().split())) for _ in range(n)], 
              dtype="int64")
xh = XH[np.argsort(XH[:, 0])]


#ans = 0
#for i in range(n):
#    xi = xh[i, 0]
#    hi = xh[i, 1]
#    if hi > 0:
#        an = hi // a + int(hi % a != 0)
#        ai = an * a
#        xj = xi + 2 * d
#        xh[:, 1][xh[:, 0] < xj+1] -= ai
#        ans += an
#    
#print(int(ans))

Submission status: Wrong Answer

Solution code:
import math

n,d,a = map(int,input().split())
line = [0] * n

for i in range(n):
    line[i] = list(map(int,input().split()))
line.sort()
ans = 0
tmpd = 0
tmpt = 0
for i in range(n):
    if line[i][1] > 0:
        tmpt = math.ceil(line[i][1]//a)
        tmpd = line[i][0] + 2*d +1
        ans += tmpt
        for j in range(d*2+1):
            if i+j >= n:
                break
            elif line[i+j][0] < tmpd:
                line[i+j][1] -= tmpt*a
            else:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x:x[0])
x = [0]*n
h = [0]*n
for i in range(n): x[i],h[i] = lst[i]

length = [0]*n
for i in range(n):
    left = i+1
    right = n-1
    while left <= right:
        mid = (left+right)//2
        if x[mid] - x[i] <= 2*d:
            left = mid+1
        else:
            right = mid-1
    length[i] = left-1

d = [0]*n
dmg = 0
idx = 0
ans = 0
for i in range(n):
    if i > length[idx]:
        idx += 1
    h[i] = max(h[i]-dmg+d[idx-1],0)
    cnt = (h[i]+a-1)//a
    ans += cnt
    dmg += cnt*a
    d[i] = dmg

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x:x[0])
x = [0]*n
h = [0]*n
for i in range(n): x[i],h[i] = lst[i]

length = [0]*n
for i in range(n):
    left = i+1
    right = n-1
    while left <= right:
        mid = (left+right)//2
        if x[mid] - x[i] <= 2*d:
            left = mid+1
        else:
            right = mid-1
    length[i] = left-1

d = [0]*n
dmg = 0
idx = 0
ans = 0
for i in range(n):
    if i > length[idx]:
        idx += 1
    h[i] = max(h[i]-dmg+d[idx-1],0)
    cnt = (h[i]+a-1)//a
    ans += cnt
    dmg += cnt*a
    d[i] = dmg

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
n, d, a = map(int, input().split())
monster = []

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

monster.sort()
hp = []
x = []
damage = [0] * (n+1)

for i in range(n):
    hp.append(monster[i][1])
    x.append(monster[i][0])

ans = 0
for i in range(n):
    bomb = (hp[i] - damage[i] - 1) // a + 1
    ans += bomb
    damage[i] += bomb * a
    damage[bisect_right(x, x[i]+2*d)] -= bomb * a
    damage[i+1] += damage[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH=[]
for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]

from bisect import bisect_right
import numpy as np
H=np.array(H)
ans=0
js=[bisect_right(X, 2*D+X[i]) for i in range(N)]

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
from math import ceil

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 = ceil(h / A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

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

ans = 0

target = 0
FLG = True
while FLG:
    cur = M[target][0] + D
    if M[target][1] <= 0:
        attack = 0
    else:
        attack = ceil(M[target][1]/A)
    ans += attack
    damage = attack * A
    for i in range(target+1, N):
        if cur - D <= M[i][0] <= cur + D:
            if M[i][1] > damage:
                target = i
                M[target][1] -= damage
                break
        else:
            target = i
            break
    else:
        if i >= N - 1:
            FLG = False

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil


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


def problem_a(h):
    return ceil(h/A)


cnt_sum = 0
cnt = [0] * N
l = 0
for i in range(N):
    while monsters[l][0] + 2 * D < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
    already = cnt_sum * A
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

print(sum(cnt))

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
A.sort()
count = 0
for i in range(n):
    if A[i][1] > 0:
        sx = A[i][0]
        if A[i][1] % a == 0:
            count_a = A[i][1] // a
        else:
            count_a = A[i][1] // a +1
        A[i][1] -= count_a * a
        count += count_a
        for j in range(i+1, n):
            if A[j][1] > sx + d*2:
                break
            else:
                A[j][1] -= count_a * a
print(count)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
A.sort()
count = 0
for i in range(n):
    if A[i][1] > 0:
        sx = A[i][0]
        if A[i][1] % a == 0:
            count_a = A[i][1] // a
        else:
            count_a = A[i][1] // a +1
        A[i][1] -= count_a * a
        count += count_a
        for j in range(i+1, n):
            if A[j][1] > sx + d*2:
                break
            else:
                A[j][1] -= count_a * 2
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
n,d,a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
L=[]
T=[]
for i in range(n):
    L.append(l[i][0])
    T.append(l[i][1])
Q=[]
for i in range(n):
    Q.append(bisect.bisect_right(L,L[i]+2*d))
ans=0
for i in range(n):
    z=-(-T[i]//a)
    for j in range(i,Q[i]):
        T[j]-=z*a
    ans+=z
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
import bisect
n, d, a = map(int, input().split())
data = []
x_point = []
for i in range(n):
    x,h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
data.sort()
x_point.sort()
imos = [0] * (n+1)
ans = 0
for i in range(1,n+1):
    x, h = data[i-1]
    imos[i] += imos[i-1]
    index = bisect.bisect_right(x_point, x + 2*d)
    h -= imos[i]
    count = max(math.ceil(h/a), 0)
    ans += count
    imos[i] += count*a
    if index <= n:
        imos[index] -=count*a
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
import bisect
n, d, a = map(int, input().split())
data = []
x_point = []
for i in range(n):
    x,h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
data.sort()
x_point.sort()
imos = [0] * (n+1)
ans = 0
for i in range(1,n+1):
    x, h = data[i-1]
    imos[i] += imos[i-1]
    index = bisect.bisect_left(x_point, x + 2*d)
    h -= imos[i]
    count = max(math.ceil(h/a), 0)
    ans += count
    imos[i] += count*a
    if index+1 <= n:
        imos[index+1] -=count*a
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
import bisect
n, d, a = map(int, input().split())
data = []
x_point = []
for i in range(n):
    x,h = map(int, input().split())
    data.append([x,h])
    x_point.append(x)
data.sort()
x_point.sort()
imos = [0] * (n+1)
ans = 0
for i in range(1,n+1):
    x, h = data[i-1]
    imos[i] += imos[i-1]
    index = bisect.bisect_left(x_point, x + 2*d)
    h -= imos[i]
    count = max(math.ceil(h/a), 0)
    ans += count
    imos[i] += count*a
    if index+1 < n:
        imos[index+1] -=count*a

print(ans)

Submission status: Wrong Answer

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

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

for i in range(n):
    xh[i][1] = -(-xh[i][1] // a)

ans = 0
count = 0
r = 0
l = 0
li = [0]*n
li2 = [xh[0][1]]

for i in range(1,n):
    li2.append(li2[-1] + xh[i][1])

while l < n:
    if r < n:
        if xh[l][0] + 2 * d >= xh[r][0]:
            r += 1
        else:
            li[l] = r - 1
            l += 1
    else:
        li[l] = n - 1
        l += 1

for i in range(n):
    if count < li2[i]:
        ans += li2[i] - count
        count += (li[i] - i + 1) * (li2[i] - count)

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np

n, d, a = map(int, input().split())
ml = [list(map(int, input().split())) for _ in range(n)]
ml = np.array(ml)
ml = ml[ml[:, 0].argsort(), :].T
print(n, d, a)

for i in range(n):
    ml[1][i] = (ml[1][i] - 1) // a + 1
count = 0
for i in range(n):
    if ml[1][i] > 0:
        dmg = ml[1][i]
        count += dmg
        for j in range(i, n):
            if ml[0][j] <= ml[0][i] + 2 * d:
                ml[1][j] = max(ml[1][j] - dmg, 0)
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    from bisect import bisect_right
    ans = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        cur = (h + A - 1) // A
        damage = cur * A
        BIT_update(left+1, -damage)
        right = bisect_right(X, x + 2*D)
        BIT_update(right+1, damage)
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        while right < N and P[right][0] <= x + 2*D:
            right += 1
        cur = (h + A - 1) // A
        damage = cur * A
        BIT_update(left+1, -damage)
        if right < N:
            BIT_update(right + 1, damage)
        ans += cur
        if left + 1 == right:
            right += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        while right < N and P[right][0] <= x + 2*D:
            right += 1
        cur = (h + A - 1) // A
        damage = cur * A
        BIT_update(left+1, -damage)
        if right < N:
            BIT_update(right + 1, damage)
        ans += cur
        if left == right:
            right += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        while right < N and P[right][0] <= x + 2*D:
            right += 1
        cur = (h + A - 1) // A
        damage = cur * A
        BIT_update(left+1, -damage)
        if right < N:
            BIT_update(right + 1, damage)
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import *

n, d, a = map(int, input().split())
damage_diff = [0] * n
damage = 0
p = sorted(tuple(map(int, input().split())) for _ in range(n))

j = 0
c = 0

for i in range(n):
  damage -= damage_diff[i]
  
  x, h = p[i]
  h -= damage
  if h <= 0: continue
  m = ceil(h/a)
  c += m
  m = m*a
  while j < n and p[j][0] - x <= 2 * d:
    j += 1

  if j < n:
    damage_diff[j] = m
  damage += m
print(c)

Submission status: Wrong Answer

Solution code:
from math import *

n, d, a = map(int, input().split())
damage_diff = [0] * n
damage = 0
p = sorted(tuple(map(int, input().split())) for _ in range(n))

j = 0
c = 0

for i in range(n):
  damage -= damage_diff[i]
  
  x, h = p[i]
  h -= damage
  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

  if j < n:
    damage_diff[j] = m
  damage += m
print(c)

Submission status: Wrong Answer

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
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: Wrong Answer

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