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
import numpy as np
input = sys.stdin.readline
N,D,A=map(int, input().split())
mg = [None]*N
for i in range(N):
  mg[i]=list(map(int, input().split()))
mg.sort(key=lambda x:x[0])
mg = (np.array(mg)).T
X = mg[0]
H = mg[1]
XD = [0]*N
l = 0
r = 0
while r <= N - 1:
  if X[r] <= X[l] + 2*D:
    r += 1
    XD[l] = r
  else:
    l += 1
XD = np.array(XD)
i = 0
ans = 0
while i<N:
  if H[i]>0:
    k = (H[i]+A-1)//A
    ans +=k
    H[i:XD[i]]=np.maximum(0,H[i:XD[i]]-k*A)
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from operator import itemgetter
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    xh = [None] * n
    for i in range(n):
        xh[i] = tuple(map(int, read().split()))
    xh.sort(key=itemgetter(0))
    x, h = [0] * n, [0] * n
    for i, (xi, hi) in enumerate(xh):
        x[i] = xi
        h[i] = hi
    cnt = 0
    for i, (xi, hi) in enumerate(xh):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        r = bisect_right(x, xi + 2 * d) - 1
        for j in range(i, r + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from operator import itemgetter
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    xh = [None] * n
    for i in range(n):
        xh[i] = tuple(map(int, read().split()))
    xh.sort(key=itemgetter(0))
    x, h = [0] * n, [0] * n
    for i, (xi, hi) in enumerate(xh):
        x[i] = xi
        h[i] = hi
    r = [0] * n
    for xi in x:
        r[i] = bisect_right(x, xi + 2 * d) - 1
    cnt = 0
    for i, hi in enumerate(h):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        for j in range(i, r[i] + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from operator import itemgetter
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, d, a = map(int, read().split())
    xh = [None] * n
    for i in range(n):
        xh[i] = tuple(map(int, read().split()))
    xh.sort(key=itemgetter(0))
    x, h = [0] * n, [0] * n
    for xi, hi in xh:
        x[i] = xi
        h[i] = hi
    r = [0] * n
    for xi in x:
        r[i] = bisect_right(x, xi + 2 * d) - 1
    cnt = 0
    for i, hi in enumerate(h):
        if hi <= 0:
            continue
        b = (hi + a - 1) // a
        cnt += b
        for j in range(i, r[i] + 1):
            h[j] -= a * b
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,D,A = MI()
    XH = LLIN(N)
    XH.sort()
    q = deque()
    ans = 0
    now = 0
    for x,h in XH:
        if q and x > q[0][0]:
            now -= q.popleft()[1]
        h-=now
        if h>0:
            ans += (h-A+1)//A
            q.append((x+2*D, ((h-A+1)//A)*A))
            now += ((h-A+1)//A)*A
    print(ans)
    



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,D,A = MI()
    XH = LLIN(N)
    XH.sort()
    q = deque()
    ans = 0
    now = 0
    for x,h in XH:
        if q and x > q[0][0]:
            now -= q.popleft()[1]
        h-=now
        if h>0:
            ans += ceil(h/A)
            q.append((x+2*D, ceil(h/A)*A))
            now += ceil(h/A)*A
    print(ans)
    



if __name__ == '__main__':
    main()