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:
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()
p = 0
j = 0
data = []
for i in range(n):
    while XH[i][0] > XH[j][0] + 2*d:
        p -= data[j]
        j += 1
    p_i = min(XH[i][1]-p,0)
    data.append(p_i)
    ans += p_i
    p += p_i

print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A = map(int,input().split())
import numpy as np
import math
XH = [list(map(int,input().split())) for _ in range(N)]
XH = sorted(XH)
ans = 0
l=[0]*N
x = XH[0][0]
j = 0
while True:
  if j+1>=N:
    break
  if XH[j+1][0]<=x+D:
    j+=1
  else:
    break
l[0]=j
for i in range(1,N):
  x = XH[i][0]
  j = l[i-1]
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+D:
      j+=1
    else:
      break
  l[i]=j
H = np.array([xh[1] for xh in XH])
for i,a in enumerate(l):
  h = H[i]
  if h<=0:
    continue
  else:
    b = math.ceil(h/A)
    ans += b
    H[i:l[a]+1:]-=b*A
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from bisect import bisect_left as bi_l

n, d, a, *xh = map(int, sys.stdin.read().split())
xh = [(x, ceil(h / a)) for x, h in sorted(zip(*[iter(xh)] * 2))]

def main():
    cnt = 0
    l = 0
    r = []
    s = [0]
    tmp = 0
    i = 0
    while l < n:
        x, h = xh[l]
        j = bi_l(r, x)
        if j > i:
            tmp -= s[j]
            i = j
        if h - tmp <= 0:
            l += 1
            continue
        cnt += h - tmp
        r.append(x + d * 2)
        s.append(h - tmp)
        tmp += h - tmp
        l += 1
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

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

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):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
L.sort()
X = []
for i in range(N):
    X.append(L[i][0])

import bisect
ans = 0
for i in range(N):
    L[i][1] -= bit.sum(N)-bit.sum(i)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    j -= 1
    if j > i:
        bit.add(i+1, num*A)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
cum = [0]*N
dam = 0
for i in range(N):
    dam += cum[i]
    H[i] -= dam
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_left(X,x+2*D)
    if i+1 < N:
        cum[i+1] += damage 
    if ind+1 < N:
        cum[ind+1] -= cnt_bom

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
l=0
before=0
T=[0]*n
for i,xh in enumerate(XH):
    x,h=xh
    while XH[l][0]+2*d<x:
        before-=T[l]
        l+=1
    h-=before*a
    if h<=0:
        continue
    T[i]=math.ceil(h//a)
    ans+=T[i]
    before+=T[i]
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
while True:
    cur = M[target][0] + D
    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:
        break

print(ans)

Submission status: Wrong Answer

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

lst1 = [list(map(int,input().split())) for i in range(n)]

lst2 = []
ans = 0
lst1.sort()
rang = [-d,d]
for i in range(n):
    for j,k,l in lst2:
        if j <= lst1[i][0] <= k:
            if lst1[i][0]-l > 0:
                lst1[i][1]-=l
            else:
                continue
    now = lst1[i][0]
    lst2.append([now,now+d*2,math.ceil(lst1[i][1]/a)*a])
    ans += math.ceil(lst1[i][1]/a)


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from bisect import bisect_right


def solve(*args: str) -> str:
    n, d, a = map(int, args[0].split())
    XH = [tuple(map(int, s.split())) for s in args[1:]]
    XH.sort()
    X, H = map(list, zip(*XH))

    count = 0
    for i, x in enumerate(X):
        if H[i] <= 0:
            continue

        j = bisect_right(X, x+(2*d))
        m = H[i]//a
        count += m
        for k in range(i, j):
            H[k] -= a*m

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import sys

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

for i in range(N):
  a, b = map(int, input().split())
  t = []
  t.append(a)
  t.append(b)
  X.append(t)

X_sorted = sorted(X, key=lambda x: x[0])
  
ind = 0
count= 0
mini = sys.maxsize
for i in range(sys.maxsize):
  if ind > N - 1:
    break;
  elif X_sorted[ind][1] <= 0:
      ind = ind + 1
  elif (X_sorted[ind][1]%A) != 0:
    count = count + (X_sorted[ind][1]/A) + 1
    X_sorted[ind][1] = 0
    for i in range(ind + 1, N):
      if X_sorted[i][0] <= (X_sorted[ind][0] + 2*D):
        X_sorted[i][1] = X_sorted[i][1] - ((X_sorted[ind][1]/A) + 1)
      else:
        break
    ind = ind + 1
  else: 
    count = count + (X_sorted[ind][1]/A)
    for i in range(ind + 1, N):
      if X_sorted[i][0] <= (X_sorted[ind][0] + 2*D):
      	X_sorted[i][1] = X_sorted[i][1] - (X_sorted[ind][1]/A)
      else:
        break
    ind = ind + 1

print(int(count))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,D,A=map(int,input().split())
    li=[]
    for i in range(N):
        li.append(tuple(map(int,input().split())))
    li.sort()
    X,H=[0]*N,[0]*N
    for i,t in enumerate(li):
        X[i],H[i]=t
    x=0
    ans=0
    l=D*2+1
    f2=True
    while f2:
        f=True
        index=bisect_right(X,X[x]+l)
        d=-(-H[x]//A)*A
        ans+=-(-H[x]//A)
        for i in range(x,index):
            if H[i]<=d and f:
                if i==N-1:
                    print(ans)
                    exit()
            else:
                if f:
                    x=i
                H[i]-=d
                f=False
        if f:
            x=index
            
        

if __name__ == '__main__':
    main()

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

b=0
now=0
stronger=now
end_i=0

while True:
    now_h=xh[now][1]
    stronger=now
    included=0

    for i in range(now+1,n):
        end_i+=1
        if xh[i][0]>xh[now][0]+2*d:
            break
        else:
            included+=1
            if now_h<xh[i][1]:
                stronger=i
            xh[i][1]-=now_h
    
    b+=xh[now][1]//a+1
    if xh[now][1]%a==0:
        b-=1

    if stronger==now:
        now+=included+1
    else:
        now=stronger
    if now>=n:
        break
print(b)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
XH=[]
for i in range(n):
  XH.append([int(i) for i in input().split()])
XH.sort(key=lambda x:x[0])
lx,lh=XH[0]
mx,mh=lx,lh
ans=0
for i in range(n-1):
  x,h=XH[i+1]
  if x>lx+2*d:
    if lh%a==0:
      ans+=lh//a
      mh-=lh
      lx,lh=mx,mh
    else:
      ans+=(lh-1)//a+1
      mh=max(0,mh-((lh-1)//a+1)*a)
      lx,lh=mx,mh
    if mh==0:
      lx,lh=x,h
      mx,mh=x,h

  else:
    if h>=mh:
      mx,mh=x,h


ans+=(mh-1)//a+1
print(ans)

Submission status: Wrong Answer

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

XH.sort(key=lambda x:x[0],reverse=False)

output = 0
s = 0
DA = [0]*N
while s<N:
    X = XH[s][0]
    L=X
    H = XH[s][1]
    if DA[s]>H:
        s+=1
        continue
    B = H//A+1*(H%A!=0)
    output += B
    DA[s]=B*A
    flag = 0
    s+=1
    while (s<N)and(XH[s][0]<=L+2*D):
        DA[s]+=B*A
        s+=1

print(output)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,d,a = inpm()
    xh = []
    for _ in range(n):
        x,h = inpm()
        key = h//a
        if h%a != 0:
            key += 1
        xh.append((x,key))
    
    xh.sort()
    ans = xh[0][1]
    r = deque()
    r.append((xh[0][0]+2*d,xh[0][1]))
    for i in range(1,n):
        [x,h] = xh[i]
        while r:
            if r[0][0]<x-2*d:
                r.popleft()
            else:
                break
        if r:
            num = len(r)
            index = 0
            while index < num and h > 0:
                h -= r[index][1]
                index += 1
            if h > 0:
                ans += h
                r.append((x+2*d,h))
        else:
            r.append((x+2*d,h))
            ans += h
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
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):
    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 i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  ans += remain[i]-bit.sum(i+1)
  bit.add(i+1,remain[i])
  bit.add(br+1,-remain[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
N,D,A= map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
X,H = [list(x) for x in zip(*XH)]

ans = 0
cum = [0]*N
dam = 0
for i in range(N):
    dam += cum[i]
    H[i] -= dam
    x = X[i]
    if H[i] <= 0:
        continue
    cnt_bom = -(-H[i] // A)
    ans += cnt_bom
    damage = cnt_bom * A
    ind = bisect.bisect_right(X,x+2*D)
    if i+1 < N:
        cum[i+1] += damage 
    if ind < N:
        cum[ind] -= cnt_bom

print(ans)

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,dtype="int64")

ans = 0
while True:
    tmp = bisect.bisect_left(hhh,1)
    if tmp == n:
        break
    tmp2 = bisect.bisect_right(xx,xx[tmp] + 2*d)
    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:
import bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)])
x = []
for X,h in xh:
  x.append(X)
data0 = [0]*(N+1)
data1 = [0]*(N+1)

def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0

for L,(X,H) in enumerate(xh):
  L += 1
  R = bisect.bisect_right(x,X+2*d)
  res = math.ceil((H - query(L,L+1) * a) / a) #ansを変える
  ans += res
  add(L,R+1,res)
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A = map(int, input().split())
P=[]
for i in range(N):
    L = list(map(int, input().split()))
    if(L[1]%A==0):
        L[1]=int(L[1]/A)
    else:
        L[1]=int(L[1]/A)+1
    L.append(L[0]-D)
    L.append(L[0]+D)
    P.append(L)
P.sort()
#print(P)
ans=0
for i in range(N):
    if(P[i][1]>0):
        ans+=P[i][1]
        P[i][1]=0
        for j in range(i+1,N):
            if(P[i][3]>=P[j][2]):
                P[j][1]-=P[i][1]
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
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):
    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 i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_left(x,x[i]+2*d)
  ans += remain[i]-bit.sum(i+1)
  bit.add(i+1,remain[i])
  bit.add(br+1,-remain[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    count = math.ceil(h // a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
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
    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())
XHlist = sorted([tuple(map(int, input().split())) for _ in range(N)])
utan = -1
help = 0
ans = 0
for i in range(N):
    X, H = XHlist[i]
    soko = ceil(H / A)
    if X <= utan:
        soko = max(0, soko - help)
    if soko > 0:
        ans += soko
        utan = X + 2 * D
        help = soko
    # print(i, soko, utan, ans)
XHlist = XHlist[::-1]
ans1 = 0
for i in range(N):
    X, H = XHlist[i]
    soko = ceil(H / A)
    if X > utan:
        soko = max(0, soko - help)
    if soko > 0:
        ans1 += soko
        utan = X - 2 * D
        help = soko
print(min(ans, ans1))

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
X.sort()
cnt = 0
i = 0
while i < N:
  F = X[i][0] + D
  if X[i][1] % A == 0:
    S = X[i][1] // A
  else:
    S = X[i][1] // A + 1
  j = i
  while X[j][0] <= F + D:
    X[j][1] -= S * A
    j += 1
    if j == N:
      break
  j = i + 1
  i = j
  cnt += S
  if j == N:
    break
  else:
    while X[j][1] < 0:
      j += 1
      if j == N:
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
N,D,A = list(map(int,input().split()))
data = []
for i in range(N):
    data.append(list(map(int,input().split())))
tmp = 0
i = 0
data.sort()
while  i < N:
    if data[i][1] > 0:
        tmpplus = (data[i][1] + A - 1) // A 
        tmp += tmpplus 
        for j in range(i,min(i+2*D,N)):
            if data[j][1] > 0:
                data[j][1] -= tmpplus*A
    i = i+1
print(tmp)

Submission status: Wrong Answer

Solution code:
import math


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

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

    xh.sort()
    ex = xh[0][0]
    ans = 0
    for i in range(N):
        if xh[i][1] <= 0:
            continue

        if i != 0 and ex  >= xh[i][0]:
            continue
        
        cnt = math.ceil(xh[i][1] / A)
        ans += cnt
        xh[i][1] = 0

        if cnt == 0:
            continue

        for j in range(i+1, N):

            if xh[j][0] > xh[i][0] + 2*D:
                break
            xh[j][1] -= cnt*A

        #print(ans, xh)
        ex = xh[i][0] + 2*D

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_dict = dict()
hp_dict = dict()
for j in range(N):

    monster_place, monster_hp = map(int, input().split())
    place_dict[monster_place] = j
    hp_dict[j] = monster_hp
ans = 0

place_dict = sorted(place_dict.items(), key=lambda x: x[0])

# print(place_dict)
for i in range(N):
    place = place_dict[i][0]
    index = place_dict[i][1]
    if index not in hp_dict:
        continue
    else:
        bomb = hp_dict[index] // A
        # print(bomb)
        ans += bomb
        for k in range(i, N):
            if place_dict[k][0] > place + 2 * D:
                break
            elif place_dict[k][1] not in hp_dict:
                continue
            else:
                hp_dict[place_dict[k][1]] -= bomb * A
                if hp_dict[place_dict[k][1]] <= 0:
                    del hp_dict[place_dict[k][1]]
print(ans)
# print(hp_dict)

Submission status: Wrong Answer

Solution code:
import math

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

L = list()

for i in range(N):
  X, H = map(int, input().split())
  L.append([X,H])

L.sort()
s = 0

for i,(x, h) in enumerate(L):
  num = math.ceil(h/A)
  s += num

print(s)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 1
    bit = defaultdict(int)
    for i in range(n):
        x, h = xh[i]
        h -= bit[i]
        if h > 0:
            t = (h - 1) // a + 1
            for ldi in range(ldi, n):
                if x + 2 * d >= xh[ldi][0]:
                    bit[ldi] += t * a
                    continue
                break
            ans += t
    tmp = 0
    bit = defaultdict(int)
    xh = xh[::-1]
    for i in range(n):
        x, h = xh[i]
        h -= bit[i]
        if h > 0:
            t = (h - 1) // a + 1
            for ldi in range(ldi, n):
                if x - 2 * d <= xh[ldi][0]:
                    bit[ldi] += t * a
                    continue
                break
            tmp += t
    print(min(tmp, ans))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
input = raw_input

n, d, a = map(int, input().split(" "))
pairs = sorted( [map(int, input().split(" "))  for _ in range(n)] , key=lambda x: x[0])

out = 0
for i in range(n):
    x1, h1 = pairs[i]
    if h1 <= 0:
        continue
    kaisu = h1 // a
    cost = kaisu * a
    out += kaisu
    #print("before out", out, cost, pairs)
    pairs[i][1] -= cost
    kijun = 2*d + x1

    for j in range(i+1, n):
        x2, h2 = pairs[j]
        if x2 > kijun:
            break
        pairs[j][1] -= cost
    #print("after out", out, cost, pairs)

# nokori
for i in range(n):
    x1, h1 = pairs[i]
    if h1 <= 0:
        continue
    cost = 1
    out += 1
    #print("before out", out, cost, pairs)
    pairs[i][1] -= cost
    kijun = 2*d + x1

    for j in range(i+1, n):
        x2, h2 = pairs[j]
        if x2 > kijun:
            break
        pairs[j][1] -= cost
    #print("after out", out, cost, pairs)


print(out)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,D,A=map(int,input().split())
    li=[]
    for i in range(N):
        li.append(tuple(map(int,input().split())))
    li.sort()
    X,H=[0]*N,[0]*N
    for i,t in enumerate(li):
        X[i],H[i]=t
    x=0
    ans=0
    l=D*2+1
    f2=True
    while f2:
        f=True
        index=bisect_right(X,X[x]+l)
        d=-(-H[x]//A)*A
        ans+=-(-H[x]//A)
        for i in range(x,index):
            if H[i]<=d and f:
                pass
            else:
                if f:
                    x=i
                H[i]-=d
                f=False
        if f:
            x=index
        if i==N-1:
            print(ans)
            exit()
                
            
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        print(enemies[j])
        enemies[j][1]-=bomb*A



print(retval)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
from operator import itemgetter
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, D, A = IL()
X = []
xx = []
H = []
for i in range(N):
  x, h = IL()
  xx.append(x)
  X.append([x, i])
  H.append(h)
else:
  xx.append(MAX_INT)
xx.sort()
X.sort(key=itemgetter(0))
data = [0]*(N+1)

D = D*2+1
damage = 0
ans = 0
for i in range(N):
  x,j = X[i]
  hp = H[j]
  damage += data[i]
  num = max(0,math.ceil((hp - damage)/A))
  damage += num*A
  ans += num
  rng = x + D
  nxt = bisect.bisect_right(xx, rng)
  data[nxt] -= num*A
#print(data)
print(ans)

"""
9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
11 5
"""

Submission status: Wrong Answer

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


seg = [0]*(2*N-1)
    
def update(k, x):
    k += N-1
    seg[k] += x
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1]+seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res += seg[p]
        if q&1 == 1:
            res += seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res += seg[q]
    else:
        res = seg[p] + seg[q]
    return res

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

import bisect
ans = 0
for i in range(N):
    L[i][1] -= query(i, N)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    j -= 1
    if j > i:
        update(j, num*A)
    

print(ans)

Submission status: Wrong Answer

Solution code:
input = raw_input

n, d, a = map(int, input().split(" "))
pairs = sorted( [map(int, input().split(" "))  for _ in range(n)] , key=lambda x: x[0])

out = 0
for i in range(n):
    x1, h1 = pairs[i]
    if h1 <= 0:
        continue
    kaisu = h1 // a
    cost = kaisu * a
    out += kaisu
    #print("before out", out, cost, pairs)
    pairs[i][1] -= cost
    kijun = 2*d + x1

    for j in range(i+1, n):
        x2, h2 = pairs[j]
        if x2 > kijun:
            break
        pairs[j][1] -= cost
    #print("after out", out, cost, pairs)

# nokori
for i in range(n):
    x1, h1 = pairs[i]
    if h1 <= 0:
        continue
    cost = 1
    out += 1
    #print("before out", out, cost, pairs)
    pairs[i][1] -= cost
    kijun = 2*d+1 + x1

    for j in range(i+1, n):
        x2, h2 = pairs[j]
        if x2 > kijun:
            break
        pairs[j][1] -= cost
    #print("after out", out, cost, pairs)


print(out)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 1
    bit = defaultdict(int)
    for i in range(n):
        x, h = xh[i]
        h -= bit[i]
        if h > 0:
            t = (h - 1) // a + 1
            for ldi in range(ldi, n):
                if x + 2 * d >= xh[ldi][0]:
                    bit[ldi] += t * a
                    continue
                break
            ans += t

    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil
N, D, A = map(int, input().split())
XHlist = sorted([tuple(map(int, input().split())) for _ in range(N)])
utan = -1
help = 0
ans = 0
for i in range(N):
    X, H = XHlist[i]
    soko = ceil(H / A)
    if X <= utan:
        soko = max(0, soko - help)
    if soko > 0:
        ans += soko
        utan = X + 2 * D
        help = soko
    # print(i, soko, utan, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
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):
    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 i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n)
for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  ans += remain[i]-bit.sum(i+1)
  bit.add(i+1,remain[i])
  bit.add(br+1,-remain[i])
print(ans)