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 operator


import operator


class SegmentTree():

    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        self.st = [init_value for i in range(treesize)]
        # 遅延評価用の更新値キャッシュ
        self.is_dirty = [False for i in range(treesize)]
        self.uv = [0 for i in range(treesize)]
    
    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, i+1, x)
        return st
    
    def _lazy_eval(self, k):
        """ノードの遅延評価"""
        if not self.is_dirty[k]:
            return
        n = len(self.st) // 2
        if k < n:
            self.uv[k * 2] = self.uv[k]
            self.is_dirty[k * 2] = True
            self.uv[k * 2 + 1] = self.uv[k]
            self.is_dirty[k * 2 + 1] = True
        self.st[k] = self.uv[k]
        self.uv[k] = 0
        self.is_dirty[k] = False
    
    def _update(self, a, b, value, k, l, r):
        """区間[a, b) に対する値の更新
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] = value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
    
    def update(self, a, b, value):
        """区間[a, b) に対する値の更新"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._update(a, b, value, k=1, l=0, r=n)
    
    def _add(self, a, b, value, k, l, r):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.uv[k] += value
            self.is_dirty[k] = True
            self._lazy_eval(k)
            return
        mid = (l + r) // 2
        self._update(a, b, value, k * 2, l, mid)
        self._update(a, b, value, k * 2 + 1, mid, r)
        self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._add(a, b, value, k=1, l=0, r=n)
    
    def _query(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        self._lazy_eval(k)
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query(a, b, k * 2, l, mid)
        rv = self._query(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        n = len(self.st) // 2
        return self._query(a, b, k=1, l=0, r=n)


def read():
    N, D, A = list(map(int, input().strip().split()))
    XH = list()
    for i in range(N):
        x, h = list(map(int, input().strip().split()))
        XH.append((x, h))
    return N, D, A, XH


def solve(N, D, A, XH):
    XH = sorted(XH)
    X = [x for x, h in XH]
    H = [h for x, h in XH]

    st = SegmentTree(N)
    for i, (x, h) in enumerate(XH):
        st.update(i, i+1, h)

    ans = 0
    i = 0
    while i < N:
        l = XH[i][0]
        r = l + 2 * D + 1
        c = XH[i][1] // A + (XH[i][1] % A > 0)
        v = c * A
        lidx = bisect.bisect_left(X, l)
        ridx = bisect.bisect_right(X, r)
        st.add(lidx, ridx, -v)
        ans += c
        m = -1
        i += 1
        while i < N:
            m = st.query(i, i+1)
            if m > 0:
                break
            i += 1
    return ans


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

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

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

cnt = 0

ol = z[0][1]
mx = 0
i = 0
while i < n:
	if z[i][1] == 0:
		i += 1
		continue
	x = 2*d+i+1
	while i < n and i <= x:
		mx = max(mx,z[i][1])
		i += 1
	cnt += math.ceil(mx/a)
print (cnt)

Submission status: Wrong Answer

Solution code:
from collections import *


def f(): return map(int, input().split())


n, d, a = f()
A = sorted(tuple(f()) for _ in range(n))
q = deque()
ans = s = 0
for x, hp in A:
    while q and q[0][0] < x:
        s -= q.popleft()[1]
    hp -= s
    if hp > 0:
        t = hp // a
        ans += t
        s += t * a
        q.append((x + d * 2, t * a))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import *


def f(): return map(int, input().split())


n, d, a = f()
A = sorted(tuple(f()) for _ in range(n))
q = deque()
ans = s = 0
for x, hp in A:
    while q and q[0][0] < x:
        s -= q.popleft()[1]
    print(q,s)
    hp -= s
    if hp > 0:
        t = hp // a
        ans += t
        s += t * a
        q.append((x + d * 2, t * a))
print(ans)

Submission status: Wrong Answer

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

for start in range(n-1):
  if l[start][1] > 0:
    for end in range(start+1, n):
      if l[end][0] <= l[start][0]+2*d:
        l[end][1] = max(l[end][1] - l[start][1], 0)
      else:
        break

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

N, D, A = map(int, input().split())
monster = [list(map(int, input().split())) for _ in range(N)]
monster.sort(key=lambda x:x[0])

bomb = deque()
s = 0
ans = 0
for i in range(N):
    x, h = monster[i]
    while len(bomb) > 0 and bomb[0][1] < x:
        s -= bomb.popleft()[2]
    h -= s
    if h > 0:
        cnt = math.ceil((h-s)/A)
        damage = cnt*A
        bomb.append([x, x+2*D, damage])
        s += damage
        ans += cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

N, D, A = map(int, input().split())
monster = [list(map(int, input().split())) for _ in range(N)]
monster.sort(key=lambda x:x[0])

bomb = deque()
s = 0
ans = 0
for i in range(N):
    x, h = monster[i]
    while len(bomb) > 0 and bomb[0][1] < x:
        s -= bomb.popleft()[2]
    cnt = math.ceil((h-s)/A)
    damage = cnt*A
    bomb.append([x, x+2*D, damage])
    s += damage
    ans += cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

N, D, A = map(int, input().split())
monster = [list(map(int, input().split())) for _ in range(N)]
monster.sort(key=lambda x:x[0])

bomb = deque()
s = 0
ans = 0
for i in range(N):
    x, h = monster[i]
    while len(bomb) > 0 and bomb[0][1] < x:
        bomb.popleft()
        s -= damage
    cnt = math.ceil((h-s)/A)
    damage = cnt*A
    bomb.append([x, x+2*D, damage])
    s += damage
    ans += cnt
print(ans)

Submission status: Wrong Answer

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

Monster.sort(key=lambda x:x[0])

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    if len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
    Monster[i][1] -= damage
    count = -(-max(Monster[i][1],0)//A)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)

Submission status: Wrong Answer

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

Monster.sort(key=lambda x:x[0])

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    if len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
    Monster[i][1] -= damage
    count = max(-(-Monster[i][1]//A),0)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)

Submission status: Wrong Answer

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

Monster.sort(key=lambda x:x[0])

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    if len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
    Monster[i][1] -= damage
    count = -(-Monster[i][1]//A)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
XH = sorted([tuple(map(int, input().split())) for _ in range(N)])
ans, R, S = 0, 0, [0] * (N + 2)
for L in range(N):
    while R < N and XH[R][0] - XH[L][0] <= 2 * D + 1:
        R += 1
    S[L + 1] += S[L]
    bomb = (max(XH[L][1] - S[L + 1], 0) + A - 1) // A
    ans += bomb
    S[L + 1] += bomb * A
    S[R + 1] -= bomb * A
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353

'''
# example input
3 3 2
1 2
5 4
9 2
'''
N, D, X = map(int, input().split())
MAXN = 2 * 10**5 + 10

DATA = [list(map(int, input().split())) for i in range(N)]
DATA.sort(key=lambda a: a[0])

A = [0] * (N + 1)
B = [0] * (N + 1)
for i in range(1, N + 1):
    A[i] = DATA[i - 1][0]
    B[i] = DATA[i - 1][1]

SUM = [0] * (N + 2)
for i in range(1, N + 1):
    B[i] = (B[i] + X - 1) // X
for i in range(1, N + 1):
    SUM[i] = B[i] - B[i - 1]

ans = 0
for i in range(1, N + 1):
    if SUM[i] != 0:
        origin = A[i]
        right = origin + 2 * D
        pos = bisect_right(A, right)
        # print(i, pos)
        SUM[pos] += SUM[i]
        ans += SUM[i]
        SUM[i] -= SUM[i]
print(ans)

Submission status: Wrong Answer

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

X = list(sorted(XH.keys()))

ans = 0
for i,x in enumerate(X):
    if x >0:
        num = -(-XH[x]//A)
    else:
        continue
    for x2 in X[i:]:
        if x2 <= x+2*D:
            XH[x2] -= num*A
        else:
            break

    ans += num
    if all(XH[j]<=0 for j in X[i:]) == True:
        print(ans)
        exit()

Submission status: Wrong Answer

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

X = list(sorted(XH.keys()))

ans = 0
for i,x in enumerate(X):
    if x >0:
        num = -(-XH[x]//A)
    else:
        continue
    for x2 in X[i:]:
        if x2 <= x+2*D:
            XH[x2] -= num*A
        else:
            break

    ans += num
    if XH[X[-1]] <=0:
        print(ans)
        exit()

Submission status: Wrong Answer

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

X = list(sorted(XH.keys()))

ans = 0
for i,x in enumerate(X):
    if x >0:
        num = -(-XH[x]//A)
    for x2 in X[i:]:
        if x2 <= x+2*D:
            XH[x2] -= num*A
        else:
            break

    ans += num
    if XH[X[-1]] <=0:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
xh=[]
n,d,a=map(int,input().split())
for _ in range(n):
	x,h=map(int,input().split())
	xh.append([x,h])
xh.sort()
ans=0
cnt=[0]*n
j=0
limit=[]
for i in range(n):
	while xh[j][0]-xh[i][0]<=2*d:
		j+=1
		if j==n:
			break
	j-=1
	limit.append(j)
num=[0]*(n+1)
cnt=0
for i in range(n):
	xh[i][1]-=(ans-cnt)*a
	ans+=(xh[i][1]-1)//a+1
	num[limit[i]]+=(xh[i][1]-1)//a+1
	cnt+=num[i]
print(ans)

Submission status: Wrong Answer

Solution code:
xh=[]
n,d,a=map(int,input().split())
for _ in range(n):
	x,h=map(int,input().split())
	xh.append([x,h])
xh.sort()
ans=0
cnt=[-1]*n
j=0
limit=[]
for i in range(n):
	while xh[j][0]-xh[i][0]<=2*d:
		j+=1
		if j==n:
			break
	j-=1
	limit.append(j)
num=[0]*(n+1)
cnt=0
for i in range(n):
	xh[i][1]-=(ans-cnt)*a
	ans+=(xh[i][1]-1)//a+1
	num[limit[i]]+=(xh[i][1]-1)//a+1
	cnt+=num[i]
print(ans)

Submission status: Wrong Answer

Solution code:
xh=[]
n,d,a=map(int,input().split())
for _ in range(n):
	x,h=map(int,input().split())
	xh.append([x,h])
xh.sort()
ans=0
cnt=[-1]*n
j=0
limit=[]
for i in range(n):
	while xh[j][0]-xh[i][0]<=2*d:
		j+=1
		if j==n:
			break
	j-=1
	limit.append(j)
num=[0]*(n+1)
cnt=0
for i in range(n):
	xh[i][1]-=(ans-cnt)*a
	ans+=(xh[i][1]-1)//a+1
	num[limit[i]]=(xh[i][1]-1)//a+1
	num[i+1]+=num[i]
	cnt+=num[i]
	xh[i][1]=max(-1,xh[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import math
import sys
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 = tuple(X)
  ans = 0
  start = 0
  while True:
    end = bisect_left(X,X[start]+2*d)
    num = math.ceil(H[start] / a)
    ans += num
    H[start] = 0
    s = start
    start = end+1
    A = a * num
    for i in reversed(range(s,end)):
      if H[i] <= 0:
        continue
      H[i] -= A
      if H[i] > 0:
        start = i
    if start > n-1:
      break

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

Submission status: Wrong Answer

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)
      else:
        X.pop()

    if end < 0:
      break

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

Submission status: Wrong Answer

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)
      else:
        X.pop()

    if end < 0:
      break

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import math

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

xh.sort()
X.sort()

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

print(ans)

Submission status: Wrong Answer

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

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    if h % A == 0:
        h //= A
    else:
        h = h//A + 1
    S[i] = [x, h]

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1] * A
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,d,a=f()
lt=sorted([tuple(f()) for _ in range(n)])
from collections import *
q=deque()
c=s=0
for x,h in lt:
  while q and q[0][0]<x:
    s+=q.popleft()[1]
  h-=s
  t=-h//a
  c-=t
  s-=t*a
  q.append((x+d*2,t*a))
print(c)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
XH = [tuple(map(int, 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
c = 0
s = 0
for i in range(n):
    H[i] = max(0, H[i]-s)
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    s += -(-H[i]//a)*a
    H[j] += s
print(c)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
XH = [tuple(map(int, 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
c = 0
s = 0
for i in range(n):
    H[i] = max(0, H[i]-s)
    c += -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    H[j] += -(-H[i]//a)*a
    s += -(-H[i]//a)*a
print(c)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
XH = []
for i in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
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
c = 0
for i in range(n):
    H[i] = max(0, H[i]-s)
    c += -(-H[i]//a)
    s += a*(-(-H[i]//a))
    while X[j] <= X[i]+2*d:
        j += 1
    H[j] += s
print(c)

Submission status: Wrong Answer

Solution code:
import math
N,D,A = map(int,input().split())
lx = []
lc = []
for i in range(N):
  X,H = map(int,input().split())
  lx.append(X)
  lc.append(math.ceil(H/A))

migi = []
m = 0
i = 0
while i <= N-1:
  if lx[m] - lx[i] > 2*D:
    migi.append(m)
    i += 1
  elif m != N-1:
    m += 1
  elif m == N-1:
    migi.append(-1)
    i += 1 

cnt = 0
dam = [0 for i in range(N)]
for i in range(N):
  if dam[i] < lc[i]:
    c = lc[i] - dam[i]  
    dam[i] += c
    if migi[i] >= 0:
      dam[migi[i]] -= c
    cnt += c
  if i <=N-2:
    dam[i+1] += dam[i]   
print(cnt)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
xhl = []
for _ in range(n):
    x,h = map(int,input().split())
    xhl.append((x, h))

xhl = sorted(xhl)
xl = [x for x,h in xhl]
def ceil(a, b):
   return a // b + (a % b > 0)

ans = 0
import bisect
reduc = [0 for i in range(n+1)]
damage = 0
for i in range(n):
    damage -= reduc[i]
    if xhl[i][1] > damage:
        hp = xhl[i][1] - damage
        count = ceil(hp, a)
        damage += count * a
        ans += count
        idx = bisect.bisect_right(xl, xhl[i][0] + 2*d)
        reduc[idx] += damage

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
xhl = []
for _ in range(n):
    x,h = map(int,input().split())
    xhl.append((x, h))

xhl = sorted(xhl)
xl = [x for x,h in xhl]
def ceil(a, b):
   return a // b + (a % b > 0)

ans = 0
import bisect
reduc = [0 for i in range(n+1)]
damage = 0
for i in range(n):
    if xhl[i][1] > damage:
        hp = xhl[i][1] - damage
        count = ceil(hp, a)
        damage += count * a
        ans += count
        idx = bisect.bisect_right(xl, xhl[i][0] + 2*d)
        reduc[idx-1] += damage
    damage -= reduc[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
xhl = []
for _ in range(n):
    x,h = map(int,input().split())
    xhl.append((x, h))

xhl = sorted(xhl)
xl = [x for x,h in xhl]
def ceil(a, b):
   return a // b + (a % b > 0)

ans = 0
import bisect
reduc = [0 for i in range(n+1)]
damage = 0
for i in range(n):
    if xhl[i][1] > damage:
        hp = xhl[i][1] - damage
        count = ceil(hp, a)
        damage += count * a
        ans += count
        idx = bisect.bisect_left(xl, xhl[i][0] + 2*d)
        reduc[idx] += damage
    damage -= reduc[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
xhl = []
for _ in range(n):
    x,h = map(int,input().split())
    xhl.append((x, h))

xhl = sorted(xhl)
xl = [x for x,h in xhl]

def ceil(a, b):
   return a // b + (a % b > 0)

ans = 0
import bisect
reduc = [0 for i in range(n)]
damage = 0
for i in range(n):
    if xhl[i][1] > damage:
        hp = xhl[i][1] - damage
        count = (hp + a - 1) // a
        damage += count * a
        ans += count
        idx = bisect.bisect_right(xl, xhl[i][0] + 2*d)
        reduc[idx-1] += damage
    damage -= reduc[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
xhl = []
for _ in range(n):
    x,h = map(int,input().split())
    xhl.append((x, h))

xhl = sorted(xhl)
xl = [x for x,h in xhl]

def ceil(a, b):
   return a // b + (a % b > 0)

ans = 0
import bisect
reduc = [0 for i in range(n)]
damage = 0
for i in range(n):
    if xhl[i][1] > damage:
        hp = xhl[i][1] - damage
        count = ceil(hp, a)
        damage += count * a
        ans += count
        idx = bisect.bisect(xl, xhl[i][0] + 2*d)
        reduc[idx-1] += damage
    damage -= reduc[i]

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

n,d,a = map(int,input().split())
queue = deque()
f = []
for i in range(n):
    x,h = map(int,input().split())
    f.append((x,h))
f.sort()
tot = 0
ans = 0
for i in range(n):
    x = f[i][0]
    h = f[i][1]
    while queue:
        now = queue.popleft()
        if now[0] >= x:break
        tot -= now[1]
    h -= tot
    if h > 0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        tot+=damage
        queue.append((x+2*d,damage))
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a = map(int,input().split())
queue = []
f = []
for i in range(n):
    x,h = map(int,input().split())
    f.append((x,h))
f.sort()
tot = 0
ans = 0
for i in range(n):
    x = f[i][0]
    h = f[i][1]
    while queue:
        now = queue.pop()
        if now[0] >= x:break
        tot -= now[1]
    h -= tot
    if h > 0:
        num = (h+a-1)//a
        ans += num
        damage = num*a
        tot+=damage
        queue.append((x+2*d,damage))
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
import math
import sys
input=sys.stdin.buffer.readline
def main():
    N,D,A=map(int,input().split())
    monster=[list(map(int,input().split()))+[0] for i in range(N)]
    heapify(monster)
    ans=0
    damage=0
    while(monster):
        m=heappop(monster)
        if(m[2]==1):
            damage-=m[1]
            continue
        else:
            if(m[1]==0):
                continue
            m[1]=max(0,m[1]-damage)
            b=math.ceil(m[1]/A)
            ans+=b
            damage+=b*A
            heappush(monster,[m[0]+2*D,b*A,1])
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import collections
N, D, A = map(int, input().split())

XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q and q[0][0] < x):
        c -= q[0][1]
        q.popleft()
    h -= c * A
    ans += math.ceil(h/A)
    c += math.ceil(h/A)
    q.append((x+2*D, math.ceil(h/A)))

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
N, D, A = map(int, input().split())

XH = [tuple(map(int, input().split())) for i in range(N)]

q = collections.deque()
c = 0
ans = 0
for x, h in XH:
    while(q and q[0][0] < x):
        c -= q[0][1]
        q.popleft()

    h -= c * A
    ans += math.ceil(h/A)
    c += math.ceil(h/A)
    q.append((x+2*D, math.ceil(x/A)))
    #print(ans, x)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while qq and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
        print(atk,qq)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # 累積ダメージの有効期限を超過
    if len(qq)!=0 and i>qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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