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 bisect
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)])
x = []
h = []
for x1,h1 in xh:
  x.append(x1)
  h.append(h1)

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(zip(x,h)):
  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:
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)
print(x)
print(remain)
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:
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)
    if j == N:
        j -= 1
    update(j, num*A)
    

print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a  = map(int,input().split())
x = []
h_b = []
h = [0]*n
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x.append({'key':i, 'val':x_temp})
    h_b.append(h_temp)

x.sort(key = lambda x : x['val'])

for i in range(n):
    ind = x[i]['key']
    h[ind] = h_b[i]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]['val']
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]['val']):
            h[i] -= at_num * a
        else:
            break

print(ans)

Submission status: Wrong Answer

Solution code:
def find_threshold(monster, D):
    start = 0
    end = len(monster)
    while True:
        test = (start + end)//2
        if monster[test][0] <= monster[0][0] + 2*D:
            start = test
        else:
            end = test
        if end-start == 1:
            break
    return end

def hp_threshold(monster, attack):
    start = 0
    end = len(monster)
    while True:
        test = (start + end)//2
        if monster[test][1] <= attack:
            start = test
        else:
            end = test
        if end-start == 1:
            break
    return end
    

def attack(monster, D, A):
    num = (monster[0][1]-1)//A + 1
    new_monster = []
    sep = find_threshold(monster, D)
    
    monster_attacked = monster[:sep]
    if sep < len(monster):
        monster_remain = monster[sep:]
    else:
        monster_remain = []
    
    monster_attacked = sorted(monster_attacked, key=lambda x: x[1])
    sep_hp = hp_threshold(monster, A*num)
    
    if sep_hp < len(monster_attacked):
        monster_attacked = monster_attacked[sep_hp:]
    else:
        monster_attacked = []
        
    monster_attacked = sorted(monster_attacked, key=lambda x: x[0])
    
    for elem in monster_attacked:
        new_monster.append([elem[0], elem[1] - num*A])
    new_monster += monster_remain
    
    if len(new_monster) == 0:
        flag=True
    else:
        flag=False
    #print(num, new_monster, flag)
    return num, new_monster, flag



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

total = 0
while True:
    num, monster, flag = attack(monster, D, A)
    total += num 
    if flag == True:
        break

print(total)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import heapq
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(1,n):
  x,h=XH[i]
  if x<lx+2*d:
    if h>=mh:
      mx,mh=x,h
  else:
    if x==lx+2*d:
      if h>=mh:
        mx,mh=x,h
    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 and x==lx+2*d:
      mx,mh=x,0
      lx,lh=x,0
    elif mh==0:
      mx,mh=x,h
      lx,lh=x,h

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

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())
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_left(X, L[i][0]+2*D)
    if j == N:
        j -= 1
    update(j, num*A)
    

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import math

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

ans = 0
for i, (xi, hi) in enumerate(monsters):
  if (hi > 0):
    ans += math.ceil(hi / a) 
    index_r = bisect.bisect_right(monsters, [xi + 2 * d, float("inf")], lo=0, hi=n)
    if (i < n - 1):
      for monster in monsters[i + 1: index_r]:
        monster[1] = max(0, monster[1] - hi)

print(ans)

Submission status: Wrong Answer

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

import math

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

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

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

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

print(t)

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
                ldi -= 1
                break
            ans += t

    print(ans)

    return


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

Submission status: Wrong Answer

Solution code:
import sys
import math

def main():
    n_d_a = sys.stdin.readline().strip().split(' ')
    n, d, a = [int(s) for s in n_d_a]

    xh = [None] * n

    for i in range(n):
        x, h = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        xh[i] = [x, h]
    xh.sort()

    attacks = []
    count = 0
    for i in range(n):
        x, h = xh[i]
        for attack in attacks:
            if x <= attack[0]:
                h -= attack[1]
        more_attack_count = math.ceil(h / a)
        count += more_attack_count
        if more_attack_count:
            attacks.append((x + 2 * d, more_attack_count * a))

    print(count)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

import collections

dms = collections.deque()
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []
for i in range(N):
    xh.append(LI())
xh.sort()

# sum_dm = [] # start + 2 * D
ans = 0
sum_dm = 0
for i in range(N):
    X, H = xh[i]
    if len(dms) > 0:
        if dms[0][0] + 2 * D < X:
            x, dm = dms.popleft()
            sum_dm -= dm
    if H <= sum_dm:
        pass
    else:
        H -= sum_dm
        ans += math.ceil(H / A)
        # print(H, A)
        dms.append([X, math.ceil(H/A) * A])
        sum_dm += math.ceil(H/A) * A
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):
    #print(buf)
    buf+=dp[i]
    y=max(xh[i][1]-buf,0)
    count+=y
    buf+=y
    idx=bisect.bisect_left(xx,xx[i]+2*d+1)
    if idx>=n:
        continue
    dp[idx]=-y
    #print(dp,y,buf)
print(count)

Submission status: Wrong Answer

Solution code:
import math
n,d,a = map(int,input().split())
if d == 0:
  d += 1
e = []
for i in range(n):
  x,h = map(int,input().split())
  e.append([x/d,math.ceil(h/a)])
e.sort()
ans = 0
for i in range(n):
  at = e[i][1]
  if at > 0:
    ans += at
    hani = e[i][0] + 2
    for j in range(i,n):
      if e[j][0] <= hani:
        e[j][1] -= at
      else:
        break
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()
idx = 0
idx_next = 0
ans = 0
while m[-1][-1] > 0:
    k = -(-m[idx][-1] // a)
    dd = m[idx][0] + 2 * d
    idx_next = idx
    ans += k
    for i in range(idx, n):
        if dd < m[i][0]:
            break
        m[i][-1] -= k * a
        if m[i][-1] <= 0:
            idx_next = i
    idx = idx_next + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import heapq
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(1,n):
  x,h=XH[i]
  if x<lx+2*d:
    if h>=mh:
      mx,mh=x,h
  else:
    if x==lx+2*d:
      if h>=mh:
        mx,mh=x,h
    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:
      mx,mh=x,h
      lx,lh=x,h

    
    
ans+=(mh-1)//a+1
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.add(i+1,remain[i])
  bit.add(br+1,-remain[i])
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()
result = 0
for i in range(N):
    if XH[i][1] < 0:
        continue
    c = (XH[i][1] + (A - 1)) // A
    result += c
    for j in range(i + 1, N):
        if XH[j][0] > XH[i][0] + D:
            break
        XH[j][1] -= c * A
print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import sys
input=sys.stdin.readline
n,d,a=[int(j) for j in input().split()]
xh=[[int(j) for j in input().split()] for i in range(n)]
xh.sort()
xh=np.array(xh)
ans=0
l=np.array([[0,0]])

for i in range(n):
    ind=np.searchsorted(l[:,0],xh[i][0],side="left")-1
    xh[i][1]-=l[-1][1]-l[ind][1]
    if xh[i][1]>0:
        k=math.ceil(xh[i][1]/a)
        ind=np.searchsorted(xh[:,0],xh[i][0]+2*d+1,side="right")-1
        l=np.append(l,[[ind,k+l[-1][1]]],axis=0)
        xh[i:ind+1,1]-=a*k
        ans+=k

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from math import ceil
    from bisect import bisect_right
    N, D, A = map(int, raw_input().split())
    Monsters = [list(map(int, raw_input().split())) for i in range(N)]
    Monsters = sorted([[x, ceil(h / A)] for x, h in Monsters])
    
    
    class BIT2:
        """ 区間加算BIT(区間加算・区間合計取得) """
    
        def __init__(self, N):
            self.N = N
            self.data0 = [0] * N
            self.data1 = [0] * N
    
        def _add(self, data, k, x):
            while k < self.N:
                data[k] += x
                k += k & -k
    
        def _get(self, data, k):
            s = 0
            while k:
                s += data[k]
                k -= k & -k
            return s
    
        def add(self, l, r, x):
            """ 区間[l,r)に値xを追加 """
    
            self._add(self.data0, l, -x*(l-1))
            self._add(self.data0, r, x*(r-1))
            self._add(self.data1, l, x)
            self._add(self.data1, r, -x)
    
        def query(self, l, r):
            """ 区間[l,r)の和を取得 """
    
            return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) \
                 - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)
    
    
    RUQ = BIT2(2 * N)
    for i, (x, h) in enumerate(Monsters, start=1):
        RUQ.add(i, i + 1, h)
    
    
    i = 0
    ans = 0
    while i < N:
        cost = RUQ.query(i + 1, i + 2)
        if cost > 0:
            index = bisect_right(Monsters, [Monsters[i][0] + 2 * D, float('inf')])
            RUQ.add(i + 1, index + 1, -cost)
            ans += cost
        i += 1
        #
        # check = []
        # for j in range(1, N + 1):
        #     check.append(str(RUQ.query(j, j + 1)))
        # print(' '.join(check))
    
    print(int(ans))


if __name__ == '__main__':
    main()

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


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size

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

    print(ans)

    return


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

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if h[i] > 0:
        left = i # 可能
        right = n # 不可能
        while left+1 < right:
            mid = (left + right) // 2
            if x[mid] - x[i] <= 2*d:
                left = mid
            else:
                right = mid
        cnt += h[i]
        for j in range(i, left+1):
            h[j] -= h[i]

print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
from operator import itemgetter
from math import ceil
def main():
    N ,D ,A  = map(int,input().split())
    XH = [list(map(int,input().split())) for _ in range(N)]
    XH.sort(key = itemgetter(0))
    X = [x for x,h in XH]
    S = [0]*(N + 10)
    sm = 0
    for i in range(N):
        x,h = XH[i]
        right = max(br(X,x + 2*D) - 1,0)
        h -= (sm - S[i-1])
        sm += max(0,ceil(h/A))*A
        S[right] = max(0,ceil(h/A))*A
        S[i] += S[i-1]
    print(sm // A)
    return

if __name__ == "__main__":
    main()

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):
    if h[i] <= 0:
        continue
    for j,yi in enumerate(x[maxalli+1:],maxalli+1):
        if yi <= xi+2*d:
            maxalli=j
            alli.append(j)
        else:
            break
    mhi = h[alli].max()
    r=mhi%a
    idm = mhi//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())
mg = [None]*N
for i in range(N):
  X,H=map(int, input().split())
  mg[i]=[X,H]
mg.sort(key=lambda x:x[0],reverse=True)
i = 0
ans = 0
while i<N:
  k = (mg[i][1]+A-1)//A
  ans +=k
  for j in range(i+1,N):
    if mg[j][0]<=mg[j][0]+2*D:
      mg[j][1]=max(0,mg[j][1]-k*A)
    else:
      break
  i+=1
print(ans)

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]+d,xh[0][1]])
    for i in range(1,n):
        [x,h] = xh[i]
        while r:
            if r[0][0]<x-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+d,h])
        else:
            r.append([x+d,h])
            ans += h
    print(ans)

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 = sorted(XH)

ans = 0
nw = 0
mm = 0
cst = 0
while(1):
    mm = XH[nw][0]+2*D
    cst = ((XH[nw][1]-1)//A)+1
    ans += cst

    con = True
    for i in range(nw+1,N):
        if XH[i][0] <= mm:
            XH[i][1] -= cst*A
        else:
            break

        if XH[i][1] <= 0 and con:
            nw = i+1
        else:
            con = False

    nw += 1
    if nw >= N:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, d, a = map(int, input().split())
    num_list = []
    for i in range(n):
        num_list.append(list(map(int,input().split())))

    ans = 0

    num_list.sort()

    for i in range(n):
        if num_list[i][1] <= 0:
            continue
        bakudanhassha = num_list[i][0] + d
        down = num_list[i][0]
        up = bakudanhassha + d
        kaisu = num_list[i][1] // a
        ans += kaisu
        num_list[i][1] -= a * kaisu
        for j in range(i+1,n):
            if num_list[j][0] <= up and num_list[j][0] >= down:
                num_list[j][1] -= a * kaisu
            else:
                break

        # print(num_list,ans,kaisu,down,up)
            
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count = []
for _ in range(n):
    x, h = map(int, input().split())
    h = h//a or 1
    count += [(x, h)]

count = sorted(count, key=lambda x:x[0])
answer = 0
while count:
    pos = count[0][0]
    _range = pos + d*2
    num = count[0][1]
    answer += num
    count = [(x, h-num) if x <= _range else (x, h) for x, h in count]
    count = [_ for _ in count if _[1] > 0]
print(answer)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

max_H = 10**9
ans = 0
damage = 0
while monsters:
    x, h = heappop(monsters)
    if h <= max_H:
        h -= damage
        if h <= 0:
            continue
        bomb = (h+A-1) // A
        damage += bomb * A
        ans += bomb
        heappush(monsters, (x+2*D, max_H+damage))
    else:
        damage -= h-max_H
print(ans)

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

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

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 = []
    nex = 0
    minus = 0
    l = 0
    for i in range(N):
        #print(i)
        #print(p[i])
        v = ret
        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:
            nex += 1
        nex -= 1
        idx.append(nex)
        val.append(ret)
        #print(idx)
        #print(val)
        #print('tmp ', tmp)
        #print(ret)
        #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:
N, D, A = map(int, input().split())
X = []
H = []
XH = []
for i in range(N):
  _x, _h = map(int, input().split())
  X.append(_x)
  H.append(_h)
  XH.append([_x, _h])
XH.sort(key=lambda x : x[0])
print("None")

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
from math import ceil
xh = [list(map(int,input().split())) for i in range(n)]
xh.sort()
memo=[]
ans = 0
while len(xh)>0:
  if memo != []:
    t=len(memo)
    for i in range(len(memo)):
      if xh[0][0] > memo[t-i-1][0]:
        del memo[t-i-1]
      else:
        xh[0][1] -= memo[t-i-1][1]
  c = ceil(xh[0][1]/a)
  memo.append([xh[0][0]+(2*d),c*a])
  ans += c
  del xh[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect

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

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

XH.sort()
XH = np.array(XH)

idx = 0
now = XH[0, 0]
ans = 0
while idx < N:
  h = XH[idx, 1]
  now = XH[idx, 0]
  count = -(-h//A)
  ans += count
  XH[XH[:, 0] <= now+W, 1] -= count*A
  idx = bisect.bisect_right(XH[:, 1]>0, 0)
  
print(ans)