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:
from heapq import heappop, heappush
from math import ceil
n,d,a = map(int,input().split())
heap = []
for _ in range(n):
    x,h = map(int,input().split())
    heappush(heap, (x,h))

ans = 0
while heap:
    x,h = heappop(heap)
    dist = x + 2 * d
    mx = h
    p = x
    while heap:
        xx,hh = heappop(heap)
        # print(xx,hh)
        if dist < hh:
            heappush(heap, (xx,hh))
            break
        if mx < hh:
            mx = hh
            p = xx

    cnt = ceil(mx/a)
    # print(p,mx, '-', cnt,dist)
    ans += cnt
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, D, A = map(int, input().split(' '))
X_H_pairs = [list(map(int, input().split(' '))) for _ in range(N)]

X_H_pairs.sort(key=lambda x: x[0])

import math
i, ans = 0, 0
while i < N:
    x, h = X_H_pairs[i]
    if h <= 0:
        i += 1
        continue
    else:
        times = int(math.ceil(h / A))
        ans += times

        dh = times * A
        dx = x + 2*D
        while i < N and X_H_pairs[i][0] <= dx:
            X_H_pairs[i][1] -= dh
            i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
s=sorted([list(map(int,input().split()))for i in range(n)])
c=0
p=[]
for i in range(n):
    j=0
    while p and j<len(p):
        if p[j][0]>=s[i][0]:
            s[i][1]-=a*p[j][0]
            if s[i][1]<=0:
                break
            j+=1
        else:
            p.pop(0)
    if s[i][1]>0:
        t=((s[i][1]-1)//a+1)
        c+=t
        p.append([s[i][0]+2*d,t])
print(c)

Submission status: Wrong Answer

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

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

    ans = 0
    index = deque()
    damage = 0
    for i in range(N):
        if index and index[0][0] + 2*D < XH[i][0]:
            _,c = index.popleft()
            damage -= A*c
        
        XH[i][1] -= damage

        if XH[i][1] > 0:
            count = ceil(XH[i][1]/A)
            damage += count * A
            index.append([XH[i][0],count])
            ans += count

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n,d,a = mi()
lii = []
for i in range(n):
    x,h = mi()
    lii.append((x,h))
lii.sort()
xx = []
hh = []
for i in range(n):
    xx.append(lii[i][0])
    hh.append(lii[i][1])


import bisect 
import numpy as np

hhh = np.array(hh)

ans = 0
while True:
    tmp = bisect.bisect_left(hhh,1)
    if tmp == n:
        break
    tmp2 = bisect.bisect_left(xx,xx[tmp] + 2*d + 1)
    if hhh[tmp] % a ==0:
        tmp3 = hhh[tmp] // a
    else:
        tmp3 = (hhh[tmp] // a) + 1
    hhh[:tmp2] -= a * tmp3
    ans += tmp3
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from bisect import bisect
from operator import itemgetter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key=itemgetter(0))
X = [XH[i][0] for i in range(N)]
H = [XH[i][1] for i in range(N)]

bit = BIT(N)

ans = 0
for i in range(N):
    bit.add(i+1,H[i])
    bit.add(i+2,-H[i])
    h = bit.sum(i+1)
    if h>0:
        ans += ceil(h/A)
        x = -ceil(h/A)*A
        j = bisect(X,X[i]+2*D)
        bit.add(i+1,x)
        bit.add(j+1,-x)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
n,d,a=map(int,input().split())
xh=[]
xx=[]
for i in range(n):
    x,h=map(int,input().split())
    xx.append(x)
    xh.append((x,h//a+(h%a>0)))
xh.sort()
xx.sort()
dp=[0]*n
import bisect
buf=0
count=0
if d==0:
    for i in range(n):
        count+=xh[i][1]
    print(count)
    sys.exit()
for i in range(n):
    #print(buf)
    y=max(xh[i][1]-buf,0)
    count+=y
    buf+=y
    buf+=dp[i]
    idx=bisect.bisect_left(xx,xx[i]+2*d)
    if idx>=n:
        continue
    dp[idx]=-y
    #print(dp,y,buf)
print(count)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

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

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l

    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count1 = 0
    for i in range(N):
        v = ST.query(i)
        if v>0:
            count1 += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    enemy = enemy[::-1]
    for i in range(N):
        enemy[i][0] = -enemy[i][0]

    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count2 = 0
    for i in range(N):
        v = ST.query(i)
        if v>0:
            count2 += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(min(count1,count2))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める

    if a == 0:
        return 0
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1


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

XH = []
Xlis = []
dic = {}

for i in range(N):

    i += 1
    
    X,H = map(int,input().split())
    XH.append([X,H])
    if X not in dic:
        Xlis.append(X)
        dic[X] = 1
    if X+D not in dic:
        Xlis.append(X+D)
        dic[X+D] = 1

Xlis.sort()
XH.sort()
BIT = [0] * (len(Xlis)+1)
ans = 0

for i in range(N):

    nx = XH[i][0]
    nh = XH[i][1]

    left = bisect.bisect_right(Xlis,nx-D)
    right = bisect.bisect_right(Xlis,nx+D)

    now = bitsum(right ,BIT) - bitsum(left-1,BIT)

    pl = updiv(nh - A*now ,A)
    ans += pl
    #print ("rem",nh - A*now,now)

    bitadd(min(N,right),pl,BIT)

#print (Xlis)
#print (BIT)
print (ans)

Submission status: Wrong Answer

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

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

    ans = 0
    index = deque()
    damage = 0
    for i in range(N):
        XH[i][1] -= damage

        if XH[i][1] > 0:
            count = ceil(XH[i][1]/A)
            damage += count * A
            index.append([XH[i][0],count])
            ans += count

        if index[0][0] + 2*D == XH[i][0]:
            _,c = index.popleft()
            damage -= A*c

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys, math, bisect
sys.setrecursionlimit(300000)


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    p = []
    for i in range(N):
        p.append([X[i], H[i]])
    p.sort()
    ret = 0
    idx = []
    val = []
    cur = 0
    nex = 0
    cum = 0
    minus = 0
    l = 0
    for i in range(N):
        v = cum
        while l < i and idx[l] < i:
            minus = val[l]
            l += 1
        v -= minus
        p[i][1] = max(0, p[i][1] - v * A)
        tmp = math.ceil(p[i][1] // A)
        ret += tmp
        x = p[i][0] + D
        while nex < N and p[nex][0] <= x + D:
            #$print('hogehoge')
            #$print(nex, p[nex][0], x + D)
            nex += 1
        cum += tmp
        idx.append(nex - 1)
        val.append(cum)
        #print(i)
        #print(idx)
        #print(val)
        #print('tmp ', tmp)
        #print(ret)
        #print(cum)
        #print()
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
  l[i][1]=(l[i][1]+a-1)//a
ans=0
L=[]
L=deque(L)
left=l[0][0]
for i in range(n):
  left=l[i][0]
  ct=0
  for j in range(len(L)):
    if L[j][0]<=l[i][0]<=L[j][1]:
      l[i][1]=max(0,l[i][1]-L[j][2])
    else:
      ct+=1
  for k in range(ct):
    L.popleft()
  ans+=l[i][1]
  L.append([left,l[i][0]+2*d,l[i][1]])
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)]
X = [XH[i][0] for i in range(N)]
X.sort()
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

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

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l

    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
N,D,A = map(int,input().split())
XH = [tuple(map(int,input().split())) for i in range(N)]
XH.sort()

#参考
#https://smijake3.hatenablog.com/entry/2018/11/03/100133
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1

def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v==0:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = 0

def add(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x
            data[R-1] += x
        if L & 1:
            lazy[L-1] += x
            data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

ans = 0
for i,(x,h) in enumerate(XH):
    p = query(i,i+1)
    if h - p*A <= 0: continue
    j = bisect(XH, (x + 2*D+1, -1))
    rem = h - p*A
    a = -(-rem // A)
    ans += a
    add(i,j,a)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

monster = []
xs = []
for i in range(N):
    x, h = map(int, input().split())
    cost = (h + A - 1) // A
    xs.append(x+2*D)
    monster.append((x, cost))

sorted_monster = sorted(monster)
xs = sorted(xs)


ans = 0

for idx, (x, cost) in enumerate(sorted_monster):
    bidx = bisect.bisect_left(xs, x)
    if bidx != idx:
        ans += max(0, cost - sorted_monster[bidx][1])
    else:
        ans += cost
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,d,a=map(int,input().split())
xh=[]
xx=[]
for i in range(n):
    x,h=map(int,input().split())
    xx.append(x)
    xh.append((x,h//a+(h%a>0)))
xh.sort()
xx.sort()
dp=[0]*n
import bisect
buf=0
count=0
if d==0:
    for i in range(n):
        count+=xh[i][1]
    print(count)
    sys.exit()
for i in range(n):
    y=max(xh[i][1]-buf,0)
    count+=y
    buf+=y
    buf-=dp[i]
    idx=bisect.bisect_left(xx,xx[i]+2*d)
    if idx>=n:
        continue
    dp[idx]=-y
print(count)

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()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(XH, [x+D*2+1, -1])
    cnt[j] += n*A
    res += n*A
    ans+=n
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
from math import ceil
n,d,a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()

res = 0
b = []
heapq.heapify(b)
r = 0
for i in range(n):
    x,h = xh[i]

    j = 0
    while len(b)>0 and b[j][0]<=x:
        r += b[j][1]
        heapq.heappop(b)
    c = ceil((h-r)/a)
    res += c
    r += c*a
    
    if c>0:
        heapq.heappush(b, (x+2*d+1, -c*a))

print(res)

Submission status: Wrong Answer

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

left = 0
right = 0
life = monsters[0][1]
ans = 0
while right <= n-1:
    now = monsters[left][0]
    maxim = life
    max_idx = left

    right = left+1
    while right <= n-1:
        new_pos, new_h = monsters[right]
        if new_pos - now > 2 * d:
            break
        else:
            if new_h > maxim:
                maxim = new_h
                max_idx = right
            right += 1

    count = life // a + bool(life % a)
    ans += count
    maxim -= a * count

    if maxim > 0:
        left = max_idx
        life = maxim
    else:
        left = right
        if left == n:
            break
        life = monsters[left][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
#A = [[0]*3]*N
X = np.zeros((2, N))

for i in range(N):
    X[0][i], X[1][i] = map(int, input().split())
    
    
X = sorted(X, key=lambda x: x[0])
ans = 0
for i in range(N):
    if X[1][i] > 0:
        hoge = math.ceil(X[1][i] / A)
        j = i + 1
        while j < N and X[0][j] <= X[0][i] + 2 * D:
            X[1][j] -= hoge * A
            j += 1
        ans += hoge

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
from math import ceil
n,d,a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()
print(xh)
res = 0
b = []
heapq.heapify(b)
r = 0
for i in range(n):
    x,h = xh[i]

    j = 0
    while len(b)>0 and b[j][0]<=x:
        r += b[j][1]
        heapq.heappop(b)
    c = ceil((h-r)/a)
    res += c
    r += c*a
    
    if c>0:
        heapq.heappush(b, (x+2*d+1, -c*a))

print(res)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monsterlist = [0] * N
for j in range(N):
    monsterlist[j] = [0] * 2
    monsterlist[j][0], monsterlist[j][1] = map(int, input().split())
ans = 0
monsterlist = sorted(monsterlist)
for i in range(N):
    if monsterlist[i][1] <= 0:
        continue
    else:
        bomb = monsterlist[i][1] // A
        # print(bomb)
        ans += bomb
        place = monsterlist[i][0]
        for k in range(i, N):
            if monsterlist[k][0] > place + 2 * D:
                break
            elif monsterlist[k][1] <= 0:
                continue
            else:
                monsterlist[k][1] -= bomb*A
print(ans)
# print(monsterlist)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

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

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l

    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count1 = 0
    for i in range(N):
        v = ST.query(i)
        count1 += v
        j = bisect(i)
        ST.update(i,j+1,-v) 

    enemy = enemy[::-1]
    for i in range(N):
        enemy[i][0] = -enemy[i][0]

    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count2 = 0
    for i in range(N):
        v = ST.query(i)
        count2 += v
        j = bisect(i)
        ST.update(i,j+1,-v) 

    print(min(count1,count2))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from bisect import bisect_left, bisect_right

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

XH.sort()
X = []
for x, _ in XH :
  X.append(x)

# 添字が1から始まることに注意
class BinaryIndexedTree() :
  def __init__(self, N) :
    self.size = N
    self.tree = [0] * (N + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.size :
      self.tree[i] += x
      i += i & -i

ret = 0
BIT = BinaryIndexedTree(N + 10)
for x, h in XH :
  a = bisect_right(X, x - D - 1)
  b = bisect_left(X, x + D) + 1
  s = BIT.sum(b) - BIT.sum(a)
  if s >= h :
    continue
  
  cnt = (h - s + A - 1) // A
  ret += cnt
  BIT.add(b, cnt * A)

print(ret)

Submission status: Wrong Answer

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

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



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

monster = []
xs = []
for i in range(N):
    x, h = map(int, input().split())
    cost = (h + A - 1) // A
    xs.append(x+2*D)
    monster.append((x, cost))

sorted_monster = sorted(monster)
xs = sorted(xs)


ans = 0

for idx, (x, cost) in enumerate(sorted_monster):
    bidx = bisect.bisect_left(xs, x)
    if bidx != idx:
        ans += max(0, cost - sorted_monster[bidx-1][1])
    else:
        ans += cost
print(ans)

Submission status: Wrong Answer

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

ans = 0
skipfrag=0
for i,xh in enumerate(XH):
    x,h=xh
    if h<=0:
        continue
    t=math.ceil(h//a)
    ans+=t
    for j in range(i,n):
        if XH[j][0] > x+2*d:
            break
        XH[j][1]-=a*t
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
loans = []
bar = 0
ans = 0
xh = sorted([tuple(map(int, input().split())) for _ in range(n)])

for x, h in xh:
    while len(loans) > 0:
        xx, dd = loans[0]
        if xx < x:
            loans.pop(0)
            bar -= dd
        else:
            break

    h -= bar
    c = h // a if h % a == 0 else ((h // a) + 1)
    ans += c
    dd = c * a
    bar += dd
    loans.append((x + 2 * d, dd))

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
XH = [[0, 0] for _ in range(N)]

for i in range(N):
    XH[i][0], XH[i][1] = map(int, input().split())

XH.sort()
# XH

ans = 0
P = 0
hist = []
j = 0
for i in range(N):
    X, H = XH[i]
    if hist != [] and hist[j][0] < X:
        P -= hist[j][1]
        j += 1
    if H - P > 0:
        if (H - P) % A == 0:
            bomb = (H - P) // A
        else:
            bomb = (H - P) // A + 1
#         print(bomb)
        ans += bomb
        P += bomb * A
        hist.append((X + 2 * D, bomb * A))
    

print(ans)

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import heapq
from math import ceil
n,d,a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()

res = 0
b = []
heapq.heapify(b)
r = 0
for i in range(n):
    x,h = xh[i]

    j = 0
    while len(b)>0 and b[j][0]<x:
        r += b[j][1]
        heapq.heappop(b)
    c = ceil((h-r)/a)
    res += c
    r += c*a
    
    if c>0:
        heapq.heappush(b, (x+2*d+1, -c*a))

print(res)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
XH = []
for _ in range(n):
    x,h = map(int,input().split())
    h = (h+a-1)//a
    XH.append([x,h])
ans = 0
XH.sort()
#print(XH)
i,j = 0,0
while i <= n or j <= n:
    if i == n or XH[j][0] + 2 * d < XH[i][0]:
        p = XH[j][1]
        ans += XH[j][1]
        t = True
        for k in range(j,i):
            XH[k][1] -= p
            if XH[k][1] > 0 and t:
                t = False
                j = k
        if t:
            j = i
            if j == n:
                break
    if i <= n-1:
        i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, D, A = [int(x) for x in input().split()]
X = []
H = []
XH = []
for _ in range(N):
    XH.append([int(x) for x in input().split()])
XH = sorted(XH)
for i in range(N):
    X.append(XH[i][0])
    H.append(XH[i][1])
cnt = 0
import numpy as np
XH = np.array(XH, np.int64)
X = np.array(X)
H = np.array(H)
for j in range(N):
    if H[j] > 0:
        bombrange_left = X[j]
        bombrange_right = X[j] + 2 * D
        if A >= H[j]:
            cnt += 1
            damage = A
        else:
            cnt += (H[j] // A) + 1
            damage = A * (H[j] // A) + 1
        idx = np.searchsorted(X, bombrange_right)
        H[j:idx] = H[j:idx] - H[j]
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




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

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

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l
    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i)
        count += v
        j = bisect(i)
        ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()