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 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,h=xh[0]
cnt=-(-h//a)
ans=cnt
#print(ans)
X=x+2*d
for i in range(1,n):
    x,h=xh[i]
    if x<=X:
        if h<=cnt*a:
            continue
        else:
            cnt=-(-(h-cnt*a)//a)
            ans+=cnt
            X=x+2*d
    else:
        cnt=-(-h//a)
        ans+=cnt
        X=x+2*d
    #print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
n,d,a=map(int,input().split())
s=sorted([list(map(int,input().split()))for i in range(n)])
c=0
p=[0]
q=[0]
for i in range(n):
    a=bl(q,s[i][0])
    s[i][1]-=p[-1]-p[a-1]
    if s[i][1]>0:
        t=((s[i][1]-1)//a+1)
        c+=t
        p.append(p[-1]+t)
        q.append(s[i][0]+2*d)
print(c)

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
totalDamage = 0
import queue
q=queue.Queue()
firstTime =True
for i in range(n):
    x,h = xh[i]
    if totalDamage == 0:
        ans += (h+a-1)//a
        damege = (h+a-1)//a*a
        totalDamage += damege
        q.put((x+2*d, damege))
    else:
        if firstTime:
            preX, preDamege = q.get()
            firstTime =False
            
        while(preX < x):
            totalDamage -= preDamege
            if q.empty():
                firstTime = True
                break
            preX, preDamege = q.get()
        
        h -= totalDamage
        ans += (h+a-1)//a
        damege = (h+a-1)//a*a
        totalDamage += damege
        q.put((x+2*d, damege))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]
  XH.sort(key=lambda x:x[0])
  #print(XH)

  B = []
  ans = 0
  for x,h in XH:
    for s,t,c in B:
      if s <= x <= t:
        h -= A*c
      if t < x:
        B.remove((s,t,c))
    if h > 0:
      B.append((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from math import ceil

from collections import deque

def resolve():
    N,D,A = (int(i) for i in input().split())
    XA=[[int(i) for i in input().split()] for j in range(N)]
    XA.sort()
    count=0
    D*=2
    q=deque(XA)
    last=N
    for _ in range(N):
        pos,life=q.popleft()
        if life<=0:
            break
        ucount=ceil(life/A)
        dmg=ucount*A

        count+=ucount
        for i in q:
            if i[0]>pos+2*D:
                break

            i[1]=max(0,i[1]-dmg)

        
    print(count)




    





if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import bisect



class LST:
    
    def __init__(self, n):
        self.lv = (n - 1).bit_length()
        self.num = 2 ** self.lv
        self.data = [0] * (2 * self.num)
        self.lazy = [None] * (2 * self.num)

    # 伝搬対象の区間を求める
    def gindex(self, l, r):
        L = (l + self.num) >> 1
        R = (r + self.num) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        ret = []
        for i in xrange(self.lv):
            if rc <= i:
                ret.append(R)
            if L < R and lc <= i:
                ret.append(L)
            L >>= 1
            R >>= 1
        return ret

    # 遅延伝搬処理
    def propagates(self, ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    # 区間[l, r)をxで更新
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)

        L = self.num + l
        R = self.num + r
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] += x
                self.lazy[R-1] = self.data[R-1]
            if L & 1:
                self.data[L-1] += x
                self.lazy[L-1] = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.num + l
        R = self.num + r

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

def main():
    n, d, a = map(int, raw_input().split())
    xh = []
    for _ in xrange(n):
        x, h = map(int, raw_input().split())
        xh.append([x, (h + a - 1) // a])
    xh.sort()
    xx = []
    hh = []
    for x, h in xh:
        xx.append(x)
        hh.append(h)
    st = LST(n)
    count = 0
    for i, x in enumerate(xx):
        j = bisect.bisect_right(xx, x + 2 * d, lo=i)
        diff = hh[i] - st.query(i, i + 1)
        if diff > 0:
            st.update(i, j, diff)
            count += diff
    print count


main()

Submission status: Wrong Answer

Solution code:
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N; V = [[]for _ in range(N)]
    for i in range(N):
        A[i],B[i] = LI()
        V[i] = [A[i],B[i],A[i]/B[i]]
    V.sort(key=lambda x:x[2],reverse=True)
    dp = [[inf]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            if j <= H - V[i][0]:
                dp[i + 1][j + V[i][0]] = min(dp[i + 1][j + V[i][0]], dp[i][j] + V[i][1])
            else:
                dp[i + 1][H] = min(dp[i + 1][H], dp[i][j] + V[i][1])
    loop = (H-1) // V[0][0] + 1
    ans = [0]*loop
    for i in range(loop):
        curH = H - V[0][0]*i
        ans[i] = i * V[0][1] + min(dp[N][curH:])
    print(ans)
#    print(dp)
    print(min(ans))
    return

def examF():
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

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

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(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 = self.segfun(ret, self.data[i])
            return ret
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    S = SegmentTree(N,0,lambda a, b: max(a,b))
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        cur -= min(S.query(i),cur)
        now = bisect.bisect_right(X,X[i]+D*2)
#        print(now)
        S.update_add(i,now,cur)
        ans +=cur
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

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
        l = 0
        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
        idx.append(nex - 1)
        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:
from math import ceil

from collections import deque

def resolve():
    N,D,A = (int(i) for i in input().split())
    XA=[[int(i) for i in input().split()] for j in range(N)]
    XA.sort()
    count=0
    D*=2
    q=deque(XA)
    last=N
    for _ in range(N):
        pos,life=q.popleft()
        ucount=ceil(life/A)
        dmg=ucount*A
        if ucount==0:
            continue
        count+=ucount
        for i in q:
            if i[0]>pos+2*D:
                break

            i[1]=max(0,i[1]-dmg)

        
    print(count)




    





if __name__ == "__main__":
    resolve()

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 data[-1][1] > 0:
    if data[i][1] > 0:
        tmpplus = (data[i][1] + A - 1) // A 
        tmp += tmpplus 
        for j in range(i,N):
            if data[j][1] > 0:
                if data[j][0] - data[i][0] <= 2*D:
                    data[j][1] -= tmpplus*A
        i = i+1
print(tmp)

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):
  ct=0
  f=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])
      f=1
    else:
      ct+=1
      if f==1:
        break
  for k in range(ct):
    L.popleft()
  ans+=l[i][1]
  L.append([l[i][0],l[i][0]+2*d,l[i][1]])
  l[i][1]=0
  left=l[i][0]+2*d
print(ans)

Submission status: Wrong Answer

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

x = [0] * n
h = [0] * n



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

s = sorted(zip(x, h))

x = [k for k, _ in s]
h = [k for _, k in s]


cus = 0
total = 0
while cus < n:
    bd = x[cus] + d
    t = math.ceil(h[cus] / a)
    total += t
    m = t * a
    tmp = n
    for j in range(cus,n):
        if x[j] <= bd + d:
            h[j] -= m
            if h[j] >0:
                if j < tmp:
                    tmp = j
        else:
            break
    cus = tmp

print(total)

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,h=xh[0]
cnt=-(-h//a)
ans=cnt
#print(ans)
X=x+2*d
for i in range(1,n):
    x,h=xh[i]
    if x<=X:
        if h<=cnt*a:
            continue
        else:
            cnt=-(-h//a)-cnt
            ans+=cnt
            X=x+2*d
    else:
        cnt=-(-h//a)
        ans+=cnt
        X=float("inf")
        cnt=0
    #print(ans)
print(ans)

Submission status: Wrong Answer

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

N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
    monsters.append((x+2*D, -h))
monsters.sort(key=lambda x: (x[0], -x[1]))

ans = 0
damage = 0
for x, h in monsters:
    if h > 0:
        h -= damage
        if h <= 0:
            continue
        bomb = (h+A-1) // A
        damage += bomb * A
        ans += bomb
    else:
        bomb = (-h+A-1) // A
        damage -= bomb * A
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        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

    bit = BIT([0]*N)

    count1 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v=0
        if enemy[i][1] - v>0:
            count1 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)

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

    bit = BIT([0]*N)

    count2 = 0
    for i in range(N):
        if i>0:
            v = bit.sum(N-1) - bit.sum(i-1)
        else:
            v = 0
        if enemy[i][1] - v>0:
            count2 += enemy[i][1] - v
            j = bisect(i)
            bit.add(j,enemy[i][1] - v)

    print(min(count1,count2))

if __name__ == '__main__':
    main()

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

    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:
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N; V = [[]for _ in range(N)]
    for i in range(N):
        A[i],B[i] = LI()
        V[i] = [A[i],B[i],A[i]/B[i]]
    V.sort(key=lambda x:x[2],reverse=True)
    dp = [[inf]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            if j <= H - V[i][0]:
                dp[i + 1][j + V[i][0]] = min(dp[i + 1][j + V[i][0]], dp[i][j] + V[i][1])
            else:
                dp[i + 1][H] = min(dp[i + 1][H], dp[i][j] + V[i][1])
    loop = (H-1) // V[0][0] + 1
    ans = [0]*loop
    for i in range(loop):
        curH = H - V[0][0]*i
        ans[i] = i * V[0][1] + min(dp[N][curH:])
    print(ans)
#    print(dp)
    print(min(ans))
    return

def examF():
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

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

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(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 = self.segfun(ret, self.data[i])
            return ret
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        cur -= S.query(i)
        now = bisect.bisect_right(X,X[i]+D*2)
#        print(now)
        S.update_add(i,now,cur)
        ans +=cur
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]

  B = []
  ans = 0
  for x,h in XH:
    for s,t,c in B:
      if s <= x <= t:
        h -= A*c
    if h > 0:
      B.append((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def inpl():
    return list(map(int, input().split()))


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()
# print(XH)

bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
tmp = 0
last = -1
for i in range(N):
    if XH[i][0] > last:
        tmp = 0

    bomb[i] -= tmp
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        tmp = bomb[i]
        last = XH[i][0] + 2 * D

print(ans)

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]
    while True:
        if j >= len(hist):
            break
        if hist[j][0] >= X:
            break
        if hist[j][0] < X:
            P -= hist[0][1]
            j += 1
    
    if H - P > 0:
        if (H - P) % A == 0:
            bomb = (H - P) // A
        else:
            bomb = (H - P) // A + 1
        ans += bomb
        P += bomb * A
        hist.append((X + 2 * D, bomb * A))
    

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)

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:
N, D,A = map(int, input().split())
R =[] * N
for i in range(N):
    v, w = map(int, input().split())
    R.append([v,w])
P = sorted(R)
cnt = 0
k = 0
for i in range(N):
    if P[i][1]>0:
        k = -(-P[i][1]//A)
        cnt += k 
    for j in range(1,N-i):
        if P[i][0]<P[i+j][0]<=P[i][0]+2 * D:
            P[i+j][1] += -k*A
        else:
            break
print(cnt)

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):
  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])
      break
    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]])
  l[i][1]=0
  left=l[i][0]+2*d
print(ans)

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 rind < X[i]:
         rind = X[i]+2*D
         tmp = ceil(H[i]/A)
         dmg = tmp*A
         ans += tmp

    elif H[i] > dmg:
        rind = X[i]+2*D
        tmp = ceil((H[i]-dmg)/A)
        dmg = tmp*A
        ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n, d, a = map(int, input().split())
monster = [[0, 0] for i in range(n)]

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

monster.sort(key = lambda x : x[0])
x = [0 for i in range(n)]
h = [0 for i in range(n)]
for i in range(n):
  x[i] = monster[i][0]
  h[i] = monster[i][1]

ans = 0
idx = 0
while True:
  if idx == n:
    break
  if h[idx] > 0:
    idx2 = bisect.bisect_right(x, x[idx] + d * 2) - 1
    bomb = (h[idx] + a - 1) // a
    ans += bomb
    for i in range(idx, idx2 + 1):
      h[i] = min(h[i] - a * bomb, 0)
  idx += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    H,A = LI()
    ans = (H-1)//A+1
    print(ans)
    return

def examB():
    H, N = LI()
    A = LI()
    if H>sum(A):
        print("No")
    else:
        print("Yes")
    return

def examC():
    N, K = LI()
    H = LI()
    H.sort()
    ans = sum(H[:max(0,N-K)])
    print(ans)
    return

def examD():
    H = I()
    ans = 2**(H.bit_length())-1
    print(ans)
    return

def examE():
    H, N = LI()
    A = [0]*N; B = [0]*N; V = [[]for _ in range(N)]
    for i in range(N):
        A[i],B[i] = LI()
        V[i] = [A[i],B[i],A[i]/B[i]]
    V.sort(key=lambda x:x[2],reverse=True)
    dp = [[inf]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            if j <= H - V[i][0]:
                dp[i + 1][j + V[i][0]] = min(dp[i + 1][j + V[i][0]], dp[i][j] + V[i][1])
            else:
                dp[i + 1][H] = min(dp[i + 1][H], dp[i][j] + V[i][1])
    loop = (H-1) // V[0][0] + 1
    ans = [0]*loop
    for i in range(loop):
        curH = H - V[0][0]*i
        ans[i] = i * V[0][1] + min(dp[N][curH:])
    print(ans)
#    print(dp)
    print(min(ans))
    return

def examF():
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

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

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(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 = self.segfun(ret, self.data[i])
            return ret
    N, D, A = LI()
    XH = [LI() for _ in range(N)]
    XH.sort(key = lambda x:x[0])
    X = [0]*N
    for i in range(N):
        X[i] = XH[i][0]
    S = SegmentTree(N+1,0,lambda a, b: a+b)
    ans = 0
    for i in range(N):
        cur = (XH[i][1]-1)//A +1
        cur -= max(S.query(i),0)
        now = bisect.bisect_right(X,X[i]+D*2)
#        print(now)
        S.update(i,now,cur)
        ans +=cur
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

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]
    while True:
        if j >= len(hist):
            break
        if hist[j][0] >= 0:
            break
        if hist[j][0] < X:
            P -= hist[0][1]
            j += 1
    
    if H - P > 0:
        if (H - P) % A == 0:
            bomb = (H - P) // A
        else:
            bomb = (H - P) // A + 1
        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())
tekis = []
for i in range(N):
    x, h = map(int, input().split())
    tekis.append((x, h))

tekis.sort()

haba = 2 * D

# iryoku, zahyoumigihaji
ruisekiwa = [(0, float("-inf"))]

left = 0

ans = 0
for i in range(N):
    x, h = tekis[i]

    while left < len(ruisekiwa) and ruisekiwa[left][1] < x:
        left += 1
    left -= 1
    rui = ruisekiwa[left:]
    # print("------x=", x, "h=", h)
    # print(ruisekiwa)
    # print("rui=", rui, "left=", left)

    imamadeiryoku = 0
    if left < len(ruisekiwa):
        imamadeiryoku = ruisekiwa[-1][0] - ruisekiwa[left][0]
    # print("imamadeiryoku=", imamadeiryoku)

    h -= imamadeiryoku

    bakudankaisuu = 0
    if h > 0:
        bakudankaisuu = h // A + (1 if h % A > 0 else 0)
    ans += bakudankaisuu
    bakudaniryoku = A * bakudankaisuu
    ruisekiwa.append((bakudaniryoku + imamadeiryoku, x + haba))

print(ans)