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

Solution code:
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A))+1
lst.sort()
ans=0
print(ans)

Submission status: Runtime Error

Solution code:
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A))+1
lst.sort()

Submission status: Runtime Error

Solution code:
def nibun_right(a, x):
 lo, hi = 0, len(a)
 while lo < hi:
  mid = (lo+hi)//2
  if x < a[mid][0]: hi = mid
  else: lo = mid+1
 return lo
N,D,A=map(int,input().split())
lst=[0]*N
for i in range(N):
 lst[i]=list(map(int,input().split()))
 lst[i][1]=int((lst[i][1]-1)/A))+1
lst.sort()
DMG=[0]*(N+1)
ans=0
for i in range(N):
 renji=nibun_right(lst,lst[i][0]+2*D)
 Z=max(lst[i][1]-DMG[i],0)
 DMG[i]+=Z
 DMG[renji]-=Z
 ans+=Z
 DMG[i+1]+=DMG[i]
print(ans)

Submission status: Runtime Error

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import OrderedDict
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 入力
    n, d, a = map(int, input().strip().split())
    xh = OrderedDict()
    for _ in range(n):
        temp1, temp2 = map(int, input().strip().split())
        if temp1>3*(10**5):
            raise ValueError("error!")
        xh[temp1] = temp2
        if temp1+2*d+1 < 3*(10**5) and (temp1+2*d+1) not in xh:
            xh[temp1+2*d+1] = 0
    xh = OrderedDict(sorted(xh.items(), key=lambda x:x[0]))

    # メイン処理
    imos = [0 for _ in range(3*(10**5))]
    x = 0
    cnt = 0
    for i, h in xh.items():
        x += imos[i]
        cnt += -(-(max(h-x, 0)//a))
        damage = a*(-(-(max(h-x, 0)//a)))
        x += damage
        imos[i] += damage
        if i + 2*d + 1 < 3*(10**5):
            imos[i+2*d+1] -= damage

    # 出力
    print(cnt)

    # デバッグ
    # eprint("xh.item()")
    # for i, h in xh.items():
    #     eprint(i, h)
    # eprint()

    # eprint('imos ', end=':\n')
    # eprint(imos)

    # lsum = [0 for _ in range(10**5)]
    # temp = 0
    # for i in range(10**5):
    #     temp += imos[i]
    #     lsum[i] = temp
    # eprint('lsum ', end=':\n')
    # eprint(lsum)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import OrderedDict
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 入力
    n, d, a = map(int, input().strip().split())
    xh = OrderedDict()
    for _ in range(n):
        temp1, temp2 = map(int, input().strip().split())
        if temp1>3*(10**5):
            raise ValueError("error!")
        xh[temp1] = temp2
        xh[temp1+2*d+1] = 0
    xh = OrderedDict(sorted(xh.items(), key=lambda x:x[0]))

    # メイン処理
    imos = [0 for _ in range(3*(10**5))]
    x = 0
    cnt = 0
    for i, h in xh.items():
        x += imos[i]
        cnt += -(-(max(h-x, 0)//a))
        damage = a*(-(-(max(h-x, 0)//a)))
        x += damage
        imos[i] += damage
        if i + 2*d + 1 < 3*(10**5):
            imos[i+2*d+1] -= damage

    # 出力
    print(cnt)

    # デバッグ
    # eprint("xh.item()")
    # for i, h in xh.items():
    #     eprint(i, h)
    # eprint()

    # eprint('imos ', end=':\n')
    # eprint(imos)

    # lsum = [0 for _ in range(10**5)]
    # temp = 0
    # for i in range(10**5):
    #     temp += imos[i]
    #     lsum[i] = temp
    # eprint('lsum ', end=':\n')
    # eprint(lsum)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import OrderedDict
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 入力
    n, d, a = map(int, input().strip().split())
    xh = OrderedDict()
    for _ in range(n):
        temp1, temp2 = map(int, input().strip().split())
        if temp1>3*(10**5):
            raise ValueError("error!")
        xh[temp1] = temp2
    xh = OrderedDict(sorted(xh.items(), key=lambda x:x[0]))

    # メイン処理
    imos = [0 for _ in range(3*(10**5))]
    x = 0
    cnt = 0
    for i, h in xh.items():
        x += imos[i]
        cnt += -(-(max(h-x, 0)//a))
        damage = a*(-(-(max(h-x, 0)//a)))
        x += damage
        imos[i] += damage
        if i + 2*d + 1 < 3*(10**5):
            imos[i+2*d+1] -= damage

    # 出力
    print(cnt)

    # デバッグ
    # eprint("xh.item()")
    # for i, h in xh.items():
    #     eprint(i, h)
    # eprint()

    # eprint('imos ', end=':\n')
    # eprint(imos)

    # lsum = [0 for _ in range(10**5)]
    # temp = 0
    # for i in range(10**5):
    #     temp += imos[i]
    #     lsum[i] = temp
    # eprint('lsum ', end=':\n')
    # eprint(lsum)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import OrderedDict
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 入力
    n, d, a = map(int, input().strip().split())
    xh = OrderedDict()
    for _ in range(n):
        temp1, temp2 = map(int, input().strip().split())
        if temp1>3*(10**5):
            raise ValueError("error!")
        xh[temp1 - 1] = temp2
    xh = OrderedDict(sorted(xh.items(), key=lambda x:x[0]))

    # メイン処理
    imos = [0 for _ in range(3*(10**5))]
    x = 0
    cnt = 0
    for i, h in xh.items():
        x += imos[i]
        cnt += -(-(max(h-x, 0)//a))
        damage = a*(-(-(max(h-x, 0)//a)))
        x += damage
        imos[i] += damage
        if i + 2*d + 1 < 3*(10**5):
            imos[i+2*d+1] -= damage

    # 出力
    print(cnt)

    # デバッグ
    # eprint("xh.item()")
    # for i, h in xh.items():
    #     eprint(i, h)
    # eprint()

    # eprint('imos ', end=':\n')
    # eprint(imos)

    # lsum = [0 for _ in range(10**5)]
    # temp = 0
    # for i in range(10**5):
    #     temp += imos[i]
    #     lsum[i] = temp
    # eprint('lsum ', end=':\n')
    # eprint(lsum)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import OrderedDict
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    # 入力
    n, d, a = map(int, input().strip().split())
    if n>10**5:
        raise ValueError("error!")
    xh = OrderedDict()
    for _ in range(n):
        temp1, temp2 = map(int, input().strip().split())
        if temp1>10**5:
            raise ValueError("error!")
        xh[temp1 - 1] = temp2
    xh = OrderedDict(sorted(xh.items(), key=lambda x:x[0]))

    # メイン処理
    imos = [0 for _ in range(10**5)]
    x = 0
    cnt = 0
    for i, h in xh.items():
        x += imos[i]
        cnt += -(-(max(h-x, 0)//a))
        damage = a*(-(-(max(h-x, 0)//a)))
        x += damage
        imos[i] += damage
        if i + 2*d + 1 < 10**5:
            imos[i+2*d+1] -= damage

    # 出力
    print(cnt)

    # デバッグ
    # eprint("xh.item()")
    # for i, h in xh.items():
    #     eprint(i, h)
    # eprint()

    # eprint('imos ', end=':\n')
    # eprint(imos)

    # lsum = [0 for _ in range(10**5)]
    # temp = 0
    # for i in range(10**5):
    #     temp += imos[i]
    #     lsum[i] = temp
    # eprint('lsum ', end=':\n')
    # eprint(lsum)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
n,d,a = map(int, input().split())
l = []
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])

l = sorted(l, key=lambda x:x[0])
start = 0
end = 1
while end < n: 
  if l[end][0] <= l[start][0]+2*d and l[start][1] > 0:
    l[end][1] = max(l[end][1] - l[start][1], 0)
    end += 1
  else:
    start += 1
    end = start + 1

count = 0
for i in range(n):
  count += math.ceil(l[i][1]/a)
print(ceil)

Submission status: Runtime Error

Solution code:
import math
n, d, a = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n):
    x, h = map(int,input().split())
    e[i] = [x,h]
num = 0

e.sort()
sd = [0 for i in range(n)]
l = [i for i in range(n)]
for i in range(n):
    for j in range(l[i-1],i):
        if e[i][0]-e[j][0] <= 2*d:
            l[i] = j
            break

for i in range(n):
    res = x[i][1] - sd[i-1] + sd[l[i]-1]
    if res < 0:
        sd[i] = sd[i-1]
    else:
        k = math.ceil(res/a)
        sd[i] = sd[i-1]+k*a
        num += k
        
print(num)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import math
import sys
from collections import deque
readlines = sys.stdin.readline

def main():
  n,d,a = map(int,input().split())
  xx = []
  hh = []
  X = []
  H = []
  for _ in range(n):
    tmp = list(map(int,input().split()))
    xx.append(tmp[0])
    hh.append(tmp[1])

  k = zip(xx,hh)
  q = sorted(k)
  for xxx,hhh in q:
    X.append(xxx)
    H.append(hhh)
  X = deque(X)
  H = deque(H)
  ans = 0
  end = n-1
  while True:
    x = X[end] - d
    start = bisect_left(X,x-d)
    num = math.ceil(H[end] / a)
    ans += num
    H.pop()
    X.pop()
    e = end
    end = start-1
    A = a * num
    for i in range(start,e):
      h = H.pop()
      if h > A:
        H.append(h-A)
        end = i
      else:
        X.pop()

    if end < 0:
      break

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import math

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

xh.sort()

ans = 0
end = n-1
while True:
  x = xh[end][0] - d
  start = bisect_left(X,x-d)
  num = math.ceil(xh[end][1] / a)
  ans += num
  xh[end][1] = 0
  e = end
  end = start-1
  for i in range(start,e):
    xh[i][1] -= a * num
    if xh[i][1] > 0:
      end = i
  if end < 0:
    break

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class RangeBIT:
        def __init__(self,n):
            self.p=self.BIT(n+1)
            self.q=self.BIT(n+1)
        
        def add(self,s,t,x):
            self.p.add(s,-x*s)
            self.p.add(t,x*t)
            self.q.add(s,x)
            self.q.add(t,-x)
        
        def sum(self,s,t):
            return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
        
        class BIT:
            def __init__(self,n):
                self.num=n
                self.dat=[0]*(self.num+1)
            
            def add(self,i,x):
                i+=1
                while i<=self.num:
                    self.dat[i]+=x
                    i+=i&-i
            
            def sum(self,i):
                i+=1
                s=0
                while i>0:
                    s+=self.dat[i]
                    i-=i&-i
                return s

    N,D,A=map(int,input().split())
    XH=[]
    for i in range(N):
        X,H=map(int,input().split())
        XH.append((X-1,H))
    XH.sort()
    b=RangeBIT(XH[-1][0]+10)
    index=0
    ans=0
    while index<N:
        h=XH[index][1]-b.sum(XH[index][0],XH[index][0]+1)
        if h<=0:
            index+=1
            continue
        d=-(-h//A)
        ans+=d
        b.add(XH[index][0],min(XH[index][0]+D*2+1,XH[-1][0]+1),d*A)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class RangeBIT:
        def __init__(self,n):
            self.p=self.BIT(n+1)
            self.q=self.BIT(n+1)
        
        def add(self,s,t,x):
            self.p.add(s,-x*s)
            self.p.add(t,x*t)
            self.q.add(s,x)
            self.q.add(t,-x)
        
        def sum(self,s,t):
            return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
        
        class BIT:
            def __init__(self,n):
                self.num=n
                self.dat=[0]*(self.num+1)
            
            def add(self,i,x):
                i+=1
                while i<=self.num:
                    self.dat[i]+=x
                    i+=i&-i
            
            def sum(self,i):
                i+=1
                s=0
                while i>0:
                    s+=self.dat[i]
                    i-=i&-i
                return s

    N,D,A=map(int,input().split())
    XH=[]
    for i in range(N):
        X,H=map(int,input().split())
        XH.append((X-1,H))
    XH.sort()
    b=RangeBIT(XH[-1][0]+1)
    index=0
    ans=0
    while index<N:
        h=XH[index][1]-b.sum(XH[index][0],XH[index][0]+1)
        if h<=0:
            index+=1
            continue
        d=-(-h//A)
        ans+=d
        b.add(XH[index][0],min(XH[index][0]+D*2+1,XH[-1][0]+1),d*A)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
XH = [tuple(map(input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import math
N,D,A=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(N)]
monster.sort(key=lambda x:x[0])
minus=[0]*N
ans=0
damage=0
for i in range(N):
    monster[i][1]-=damage
    if(monster[i][1]<=0):
        continue
    cnt=math.ceil(monster[i][1]/A)
    ans+=cnt
    if(D==0):
        continue
    b=bisect.bisect_left(monster[0],monster[i][0]+2*D)
    damage+=A*cnt
    damage-=minus[i]
    if(b!=0):
        minus[b-1]+=cnt*A
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

I = np.array(read().split(), np.int64)
X = I[::2]
H = I[1::2]

sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]

atack = np.zeros(N+1)
cover = np.searchsorted(X, X + (2 * D), side = 'right')

ans = 0
cnt = 0
for i in range(N):
	cnt += atack[i]
	H[i] -= cnt
	if H[i] > 0:
		tmp = -(-H[i]//A)
		ans += tmp
		cnt += tmp * A
		atack[cover[i]] -= tmp * A

print(ans)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : (-1 * (a)))
#define rep(i, n) for ((i) = 0; (i) < (int)(n); (i)++)
#define rep2(i, s, e) for ((i) = (s); (i) < (int)(e); (i)++)

void arg_marge(int *, int *, int);

int main(void)
{

    int n, d, a, i, k, l, *x, *h, p, *pp, ppp;
    long long int at = 0;

    scanf("%d %d %d", &n, &d, &a);
    x = (int *)malloc(n * sizeof(int));
    h = (int *)malloc(n * sizeof(int));
    pp = (int *)malloc(n * sizeof(int));
    rep(i, n)
    {
        scanf("%d %d", x + i, h + i);
        h[i] = (h[i] + a - 1) / a;
    }
    arg_marge(x, h, n);

    p = 0;
    ppp = 0;
    rep(i, n)
    {
        l = x[i] - d - d;
        while (x[p] < l)
            ppp -= pp[p++];
        pp[i] = max(h[i] - ppp, 0);
        at += pp[i];
        ppp += pp[i];
    }
    printf("%lld", at);
}

void arg_marge(int *a, int *b, int n)
{

    if (n == 1)
        return;

    int *tmp, *arg_tmp;
    tmp = (int *)malloc((n) * sizeof(int));
    arg_tmp = (int *)malloc((n) * sizeof(int));
    arg_marge(a, b, n / 2);
    arg_marge(a + n / 2, b + n / 2, n - n / 2);

    for (int i = 0; i < n / 2; i++)
    {
        tmp[i] = a[i];
        arg_tmp[i] = b[i];
    }
    for (int i = n / 2; i < n; i++)
    {
        tmp[i] = a[n / 2 + n - i - 1];
        arg_tmp[i] = b[n / 2 + n - i - 1];
    }

    int lp = 0, rp = n - 1, p = 0;
    int l3, r3;
    while (p < n)
    {
        l3 = tmp[lp];
        r3 = tmp[rp];
        if (l3 < r3)
        {
            a[p] = l3;
            b[p] = arg_tmp[lp];
            lp++;
            p++;
        }
        else
        {
            a[p] = r3;
            b[p] = arg_tmp[rp];
            rp--;
            p++;
        }
    }

    return;
}

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_f
# 座標圧縮、貪欲法、imos法


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


# まず、何回攻撃すればいいのかを計算する。これがとにかく必要だ(なくてもいいけど)。
#
# 素直な戦略として、左から倒せるギリギリの爆弾を投下して倒すのが最適
# だけどナイーブに実装すると、O(N^2)。だから体力を管理するのが重要。
# どこにどれだけダメージが蓄積したのかはimos法(デルタ関数をおいてから累積和)で管理できる。

from bisect import bisect_left
N, D, A = read_ints()
XH = read_tuple(N)
XH.sort()  # 座標でソート

n_atk = []  # 何回攻撃するのが必要か
X = []  # 座標アクセス用配列
for x, h in XH:
    n_atk.append((h - 1) // A + 1)
    X.append(x)

damege = [0] * (N + 10)  # ダメージ管理用、配列外アクセスがめんどくさいので長めに取る
ans = 0
# j = 0  # 次のxが、今のx+2d以下でもっとも大きなidx
for i, (x, n) in enumerate(zip(X, n_atk)):
    damege[i] += damege[i - 1]  # 積分して、現時点の蓄積回数を表示
    atk = max(0, n - damege[i])  # iには何回攻撃したか
    ans += atk
    # 攻撃下回数を記録
    damege[i] += atk
    # 効果が切れる点を予約 # 尺取ならO(1)で次に行けるけど二分探索でも間に合うか
    damege[bisect_left(X, x + 2 * D + 1, lo=x)] -= atk  # 効果切れを予約

print(ans)

Submission status: Runtime Error

Solution code:
n,d,a=map(int,input().split())
xh=[]
for i in range(n):
  xh.append(list(map(int,input().split())))
xh=sorted(xh)
x=[0]*n
h=[0]*n
for i in range(n):
  x[i]=xh[i][0]
  h[i]=xh[i][1]
count=0
for i in range(n):
  if h[i]%a!=0:
    h[i]=h[i]//a+1
  else:
    h[i]=h[i]//a

for i in range(d,n-d):
  count+=h[i-d]
  for j in range(i-d+1,i+d+1):
    h[j]=max(h[j]-h[i-d],0)
for i in range(n-d,n):
  count+=h[i]
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

def calc(x,h):
    if 2*d >= x[-1]-x[0]:
        b = np.max(h)
        ans = b//a + min(1,b%a)
    else:
        ans1 = h[0]//a + min(1,h[0]%a)
        ans2 = h[-1]//a + min(1,h[-1]%a)
        ans = ans1 + ans2
        h[:np.searchsorted(x,x[0]+2*d,side='right')] -= ans1*a
        h[np.searchsorted(x,x[-1]-2*d,side='left'):] -= ans2*a
        c = np.where(h > 0)[0]
        if len(c) > 0:
            x_ = x[c[0]:c[-1]+1]
            h_ = h[c[0]:c[-1]+1]
            ans += calc(x_,h_)
    
    return ans

print(int(calc(x,h)))

Submission status: Runtime Error

Solution code:
import numpy as np
n,d,a = map(int,input().split())
x = np.zeros(n)
h = x.copy()
for i in range(n):
    x[i],h[i] = map(int,input().split())
    
ind = np.argsort(x)
ind2 = np.arange(n)
x = np.sort(x)
h[ind2] = h[ind]

def calc(x,h):
    if 2*d >= x[-1]-x[0]:
        b = np.max(h)
        ans = b//a + min(1,b%a)
    else:
        ans1 = h[0]//a + min(1,h[0]%a)
        ans2 = h[-1]//a + min(1,h[-1]%a)
        ans = ans1 + ans2
        h[:np.searchsorted(x,x+2*d,side='right')] -= ans1*a
        h[np.searchsorted(x,x[-1]-2*d,side='left'):] -= ans2*a
        c = np.where(h > 0)[0]
        if len(c) > 0:
            x_ = x[c[0]:c[-1]+1]
            h_ = h[c[0]:c[-1]+1]
            ans += calc(x_,h_)
    
    return ans

print(int(calc(x,h)))

Submission status: Runtime Error

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

enemy = {}
field = {}
poss = []
for i, (Xi, Hi) in enumerate(XH):
    enemy[str(Xi)] = max(field.setdefault(str(Xi), 0), Hi)
    field[str(Xi)] = field.setdefault(str(Xi), 0)
    field[str(Xi + 2 * D + 1)] = field.setdefault(str(Xi + 2 * D + 1), 0)
    poss.append(Xi)
    poss.append(Xi + 2 * D + 1)

# print("#", field)
# print("#", enemy)
poss.sort()

ans = 0
state = 0
for pos in poss:
    key = str(pos)
    state += field[key]
    if state < enemy.setdefault(key, 0):
        bomb = enemy.setdefault(key, 0) - state
        # print("#", pos, ((bomb + A - 1) // A))
        cnt = (bomb + A - 1) // A
        ans += cnt 
        state += A * cnt
        field[str(pos + 2 * D + 1)] -= A * cnt

print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil
import bisect

N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
X = [x for x, h in Monsters]
H = [ceil(h / A) for x, h in Monsters]

min_n = 0

for i in range(N):
  if H[i] <= 0:
    continue
  #i_2Di = bisect.bisect_left(X, X[i]+2*D)
  for j in range(i+1,N):
    if X[j] - X[i] > 2*D:
      i_2Di = j
      break
  H[i:i_2Di] -= A * ni
  min_n += ni
  
print(min_n)

Submission status: Runtime Error

Solution code:
from math import ceil
import bisect

N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
X = [x for x, h in Monsters]
H = [ceil(h / A) for x, h in Monsters]

min_n = 0

for i in range(N):
  if H[i] <= 0:
    continue
  i_2Di = bisect.bisect_left(X, X[i]+2*D)
  H[i:i_2Di] -= A * ni
  min_n += ni
  
print(min_n)

Submission status: Runtime Error

Solution code:
import math


def get_inputs():
    inputs = input().split(" ")
    monsters_num, diff, attack = int(inputs[0]), int(inputs[1]), int(inputs[2])
    monsters = []
    for monster in range(monsters_num):
        inputs = input().split(" ")
        coordinate, health = int(inputs[0]), int(inputs[1])
        monsters.append({"coordinate": coordinate, "health": health})
    return monsters, diff, attack, monsters_num


def between_coordinates(monster, coordinate, diff):
    if (coordinate - diff <= monster["coordinate"] <= coordinate) or (
            coordinate <= monster["coordinate"] <= coordinate + diff):
        return True
    return False


def sort_monsters_coordinates(monsters):
    return sorted(monsters, key=lambda k: k['coordinate'])


def get_alive_monsters(monsters):
    return [monster for monster in monsters if monster["health"] > 0]


def attack_leftmost_monster(coordinate, monsters, attack, diff):
    bombs_num = 0
    if len(monsters) == 0:
        return 0
    leftmost_monster = monsters.pop(0)
    needed_attacks = math.ceil(leftmost_monster["health"] / attack)
    bombs_num += needed_attacks
    for monster in monsters:
        if between_coordinates(monster, coordinate, diff):
            monster["health"] -= (needed_attacks * attack)
    monsters = get_alive_monsters(monsters)
    return monsters, bombs_num


def get_max_health(monsters):
    if len(monsters) == 0:
        return 0

    max_health = - math.inf
    for monster in monsters:
        if monster["health"] >= max_health:
            max_health = monster["health"]
    return max_health


monsters, diff, attack, monsters_num = get_inputs()
if len(monsters) > 0:
    monsters = sort_monsters_coordinates(monsters)
else:
    print(0)

coordinate = monsters[0]["coordinate"] + diff
total_bombs_num = 0

while len(monsters) > 0 and coordinate <= monsters[-1]["coordinate"] - diff:
    monsters, bombs_num = attack_leftmost_monster(coordinate, monsters, attack, diff)
    total_bombs_num += bombs_num
    if len(monsters) > 0:
        coordinate = monsters[0]["coordinate"] + diff
        
print(total_bombs_num + math.ceil(get_max_health(monsters) / attack))