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 math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
ma=[0]*N
tmp=1
for i in range(N):
  value=0
  x=l[i][0]
  h=l[i][1]
  for j in range(tmp,N):
    if abs(l[j][0]-(x+D))>D:
      ma[i]=j
      tmp=j
      break
print(ma)
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  for j in range(i,ma[i]):
    l[j][1]-=time*A
  ans+=time
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

n, d, a = (int(v) for v in stdin.readline().split())
monsters = [(int(v) for v in line.split()) for line in stdin.readlines()]

monsters = [[x, (h // a + 1) if h % a > 0 else (h // a)] for x, h in monsters]
monsters = sorted(monsters)
bomb_size = 2 * d + 1
num_bombs = 0

current_bombs = 0
bomb_endpoints = deque()
bomb_endnumbers = deque()

for i in range(len(monsters)):
    if len(bomb_endpoints) > 0 and bomb_endpoints[0] == i:
        current_bombs -= bomb_endnumbers[0]
        bomb_endpoints.popleft()
        bomb_endnumbers.popleft()
    monsters[i][1] -= current_bombs
    if monsters[i][1] > 0:        
        bombs_now = monsters[i][1]
        monsters[i][1] = 0
        num_bombs += bombs_now
        current_bombs += bombs_now
        bomb_endpoints.append(i + bomb_size)
        bomb_endnumbers.append(bombs_now)

print(num_bombs)

Submission status: Wrong Answer

Solution code:
import sys
import math

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

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

    cur = 0
    right_indices = [0] * n
    for i in range(n):
        cur = max(cur, i)
        x, h = xh[i]
        right_val = x + d * 2
        while cur < n-1 and xh[cur+1][1] <= right_val:
            cur += 1
        right_indices[i] = cur

    imos = [0] * (n+1)
    ans = 0
    for i in range(n):
        if imos[i] < xh[i][1]:
            need = math.ceil((xh[i][1] - imos[i]) / a)
            ans += need
            imos[i] += need * a
            right_idx = right_indices[i]
            imos[right_idx+1] -= need * a
        imos[i+1] += imos[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math

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

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

    cur = 0
    right_indices = [0] * n
    for i in range(n):
        cur = max(cur, i)
        x, h = xh[i]
        right_val = x + d * 2
        while cur < n-1 and xh[cur+1][1] <= right_val:
            cur += 1
        right_indices[i] = cur

    imos = [0] * (n+1)
    ans = 0
    for i in range(n):
        if imos[i] < xh[i][1]:
            need = math.ceil((xh[i][1] - imos[i]) / a)
            print('need', need)
            ans += need
            imos[i] += need * a
            right_idx = right_indices[i]
            imos[right_idx+1] -= need * a
        imos[i+1] += imos[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  heapq.heappush(monster, (x, h))
bomb = 0
damage = 0
queue = deque()
while monster:
  x, h = heapq.heappop(monster)
  while True:
    if queue and x > queue[0][0]:
      damage -= queue.popleft()[1]
    else:
      break
  h -= damage
  b = (h - 1) // a + 1
  bomb += b
  queue.append((x + 2 * d, a * b))
  damage += a * b
print(bomb)

Submission status: Wrong Answer

Solution code:
def resolve():
    N, D, A = map(int, input().split())
    lXH = []
    while True:
        try:
            x, h = map(int, input().split())
            lXH.append([x, h])
        except:
            break
    lXHs = sorted(lXH, key=lambda k: k[0])
    from collections import deque
    q = deque()
    tot = 0
    ans = 0
    for i in range(N):
        x, h = lXHs[i]
        while len(q) > 0 and q[0][0] < x:
            qx, qh = q.popleft()
            tot -= qh
        h -= tot
        if h > 0:
            num = h//A
            ans += num
            dam = num*A
            tot += dam
            q.append([x+2*D, dam])
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import math

n, d, a = map(int, input().split())
monsters = sorted([list(map(int, input().split())) for i in range(n)], key=lambda x: x[0])
last = [0, 0]
ans = 0
pos = []

for monster in monsters:
    x, h = monster
    pos.append(x - 1 + d)

for i, monster in enumerate(monsters):
    x, h = monster
    count = 0
    if i == 0:
        count = math.ceil(h / a)
    else:
        if x > last[0]:
            count = math.ceil(h / a)
        else:
            if h - last[1] * a > 0:
                count = math.ceil((h - last[1] * a) / a)
    if count > 0:
        last = [x + d*2, count]
    ans += count

print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  while l<N and r<N and 2*D>=xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
      if r<N:
      	xh[min(r,N-1)][1]=max(0,xh[min(r,N-1)][1]-la*A)
      	#print(xh,l,r)
  #print(1,l,r)
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  la = (xh[l][1]+A-1)//A
  #xh[l][1]=0
  while l<N and r<N and 2*D>=xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    xh[min(r,N-1)][1]=max(0,xh[min(r,N-1)][1]-la*A)
   # print(xh)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  S = [0]*(N+1)
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  b = (h+A-1)//A
  ans += b
  y = b*A
  while True:
    if j+1>=N:
      break
    if XH[j+1][0]<=x+2*D:
      j+=1
    else:
      break
  S[0]+=y
  S[j+1]-=y
  S[1]+=S[0]
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    if S[i]>=h:
      S[i+1]+=S[i]
      continue
    else:
      x = xh[0]
      j = max(j,i)
      while True:
        if j+1>=N:
          break
        if XH[j+1][0]<=x+2*D:
          j+=1
        else:
          break
      b = (h+A-1)//A
      ans += b
      y = b*A
      S[i]+=y
      S[j+1]-=y
      S[i+1]+=S[i]
  print(ans)
main()

Submission status: Wrong Answer

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  while l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    #xh[r][1]=max(0,xh[r][1]-la*A)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
      xh[min(r,N-1)][1]=max(0,xh[min(r,N-1)][1]-la*A)
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  while l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
    #mi=min(mi,(xh[r][1]+A-1)//A)
    #xh[r][1]=max(0,xh[r][1]-la*A)
    if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
      break
    else:
      r+=1
      if r<N:
      	xh[r][1]=max(0,xh[r][1]-la*A)
  ans +=la
  if r==l:
    r+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  def syaku(j,x,h,D,ans):
    b = (h+A-1)//A
    ans += b
    y=b*A
    while True:
      if j+1>=N:
        break
      if XH[j+1][0]<=x+2*D:
        j+=1
        XH[j][1]-=y
      else:
        break
    return j,ans
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  l[0],ans=syaku(j,x,h,D,ans)
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    if h<=0:
      continue
    else:
      x = xh[0]
      j = max(l[i-1],i)
      l[i],ans=syaku(j,x,h,D,ans)
  print(ans)
main()

Submission status: Wrong Answer

Solution code:
def main():
  def syaku(j,x,h,D,ans):
    b = (h+A-1)//A
    ans += b
    y=b*A
    while True:
      if j+1>=N:
        break
      if XH[j+1][0]<=x+2*D:
        j+=1
        XH[j][1]-=y
      else:
        break
    return j,ans
  N,D,A = map(int,input().split())
  XH = [list(map(int,input().split())) for _ in range(N)]
  XH = sorted(XH)
  ans = 0
  l=[0]*N
  x = XH[0][0]
  h = XH[0][1]
  j = 0
  l[0],ans=syaku(j,x,h,D,ans)
  for i in range(1,N):
    xh = XH[i]
    h = xh[1]
    if h<=0:
      continue
    x = xh[0]
    j = max(l[i-1],i)
    l[i],ans=syaku(j,x,h,D,ans)
  print(ans)
main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read

N, D, A, *XH = map(int, read().split())
X = XH[::2]
H = XH[1::2]
X = [-1] + X
H = [-1] + H
D *= 2
X, H = zip(*sorted(zip(X, H)))

damages = [0] * (N + 2)
answer = 0

for i in range(1, N + 1):
    damages[i] += damages[i - 1]
    h = H[i]
    if damages[i] >= h:
        continue
    else:
        h -= damages[i]

    x = X[i]
    cnt = (h + h % A) // A
    answer += cnt
    damage = A * cnt
    damages[i] += damage
    damages[bisect_right(X, x + D)] -= damage

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from heapq import heappush, heappop

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

    xh = [[]] * n

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

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        attack_rightmost_idx[i] = cur
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    # events = deque()
    events = []
    total_damage = 0
    ans = 0
    for i in range(n):
        if events:
            while True:
                if not events:
                    break
                popped = heappop(events)
                if popped[0] <= i:
                    total_damage += popped[1]
                else:
                    heappush(events, popped)
                    break
        # while events and events[0][0] <= i:
        #     total_damage += events[0][1]
        #     events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = remaining_life // a
        if remaining_life % a:
            needed += 1
        ans += needed
        total_damage += needed * a
        # events.append((attack_rightmost_idx[i]+1, - needed * a))
        heappush(events, (attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque


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

    xh = [None] * n

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

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        attack_rightmost_idx[i] = cur
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = remaining_life // a
        if remaining_life % a:
            needed += 1
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque


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

    xh = [None] * n

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

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        attack_rightmost_idx[i] = cur
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = math.ceil(remaining_life / a)
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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(key=lambda xh: xh[0])
que = deque()
D = 2*D

H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
tot = a * A
que.append([XH[0][0]+D,tot])
ans = a
for i in range(1,N):
	if(XH[i][0] > que[0][0]):
		tot -= que[0][1]
		que.popleft()
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

N, D, A = map(int, input().split())
E = []
for _ in range(N):
    x, h = map(int, input().split())
    E.append((x, h))

E = sorted(E, key=lambda x: x[0])

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

    if x > dx:
        damage = 0

    h -= damage

    if h <= 0:
        continue

    x = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    dx = x
    #damage[x+D] = cnt * A
    ans += cnt

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from heapq import heappop, heappush


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

    xh = [None] * n

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

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = math.ceil(remaining_life / a)
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, - needed * a))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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(key=lambda xh: xh[0])
que = deque()
d = 2*D

H = XH[i][1]
if(0==H%A): a = H//A
else: a = H//A+1
tot = a * A
que.append([XH[0][0]+d+1,tot])
ans = a
for i in range(1,N):
	if(XH[i][0] > que[0][0]):
		tot -= que[0][1]
		que.popleft()
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+d+1,a*A])
		tot += a*A
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append([x, h])
monster.sort()
bomb = 0
j = 0
for i in range(n):
  while j < n and monster[j][0] - monster[i][0] <= 2 * d:
    j += 1
  if monster[i][1] <= 0:
    continue
  print(type(a))
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  for k in range(i+1, j):
    monster[k][1] -= atk
print(bomb)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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(key=lambda xh: xh[0])
que = deque()
d = 2*D

H = XH[i][1]
if(0==H%A): a = H//A
else: a = H//A+1
tot = a * A
que.append([tot,XH[0][0]+d])
ans = a
for i in range(1,N):
	if(XH[i][0] > que[0][1]):
		tot -= que[0][0]
		que.popleft()
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([a*A,XH[i][0]+d])
		tot += a*A
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from heapq import heappop, heappush


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

    xh = [None] * n

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

    cur = 0
    attack_rightmost_idx = [-1] * n
    for i in range(n):
        if cur == n:
            attack_rightmost_idx[i] = n-1
            continue
        x, h = xh[i]
        attack_rightmost = x + 2 * d
        while cur < n and xh[cur][0] <= attack_rightmost:
            attack_rightmost_idx[i] = cur
            cur += 1

    events = deque()
    total_damage = 0
    ans = 0
    for i in range(n):
        while events and events[0][0] <= i:
            total_damage += events[0][1]
            events.popleft()

        x, h = xh[i]

        remaining_life = h - total_damage
        if remaining_life <= 0:
            continue

        needed = math.ceil(remaining_life / a)
        ans += needed
        total_damage += needed * a
        events.append((attack_rightmost_idx[i]+1, -needed))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,D,A=map(int,input().split())
XH=[list(map(int,input().split())) for i in range(N)]
XH=sorted(XH,key=lambda x:x[0])

lst=[]
bomb=[]
count=0
nowbomb=0
idx=0
#print(XH)
for x,h in XH:
    #print(lst,bomb)
    if lst:
        while idx<len(lst) and lst[idx]<x-D:
            nowbomb-=bomb[idx]
            idx+=1
    a=h-nowbomb
    if a>0:

        b=a//A
        #print(b)
        nowbomb+=D*b
        count+=b
        lst.append(x+D)
        bomb.append(b*D)

print(count)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,D,A=map(int,input().split())
XH=[list(map(int,input().split())) for i in range(N)]
XH=sorted(XH,key=lambda x:x[0])

lst=[]
bomb=[]
count=0
nowbomb=0
idx=0
#print(XH)
for x,h in XH:
    print(lst,bomb)
    if lst:
        while idx<len(lst) and lst[idx]<x-D:
            nowbomb-=bomb[idx]
            idx+=1
    a=h-nowbomb
    if a>0:

        b=a//A
        #print(b)
        nowbomb+=D*b
        count+=b
        lst.append(x+D)
        bomb.append(b*D)

print(count)

Submission status: Wrong Answer

Solution code:
import sys

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

class LazySegmentTree:
    # Range Minimum Query
    def __init__(self, N):
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.INF = 2**31 - 1
        self.data = [self.INF]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 1-indexedで単調増加のインデックスリストを渡す
    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

    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
    
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小値を求める
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


def main():
    N,D,A = list(map(int,input().split()))

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

    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
    ST = LazySegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i,i+1)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

XH=[[0,0] for _ in range(N)]
for i in range(N):
    x,h=map(int,input().split())
    XH[i][0]=x
    XH[i][1]=h
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]


#bの倍数の中でaを超える最小
def calc(a,b):
    return math.ceil(a/b)*b

ans=0
S=[0]*(N+1)#累積和


for i in range(N):
    if S[i]<X[i]:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        ans+=(XH[i][1]-S[i])//A
        if XH[i][1]%A!=0:
            ans+=1
        dam=calc(XH[i][1]-S[i],A)
        #imosで遅延
        S[Lb]+=dam
        S[Rb]-=dam
    S[i+1]+=S[i]
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
N, D, A = map(int, input().split())
X = []
 
for i in range(N):
  a, b = map(int, input().split())
  t = []
  t.append(a)
  t.append(b)
  X.append(t)
 
X_sorted = sorted(X, key=lambda x: x[0])
  
ind = 0
count= 0
mini = sys.maxsize
for i in range(sys.maxsize):
  if ind > N - 1:
    break;
  elif X_sorted[ind][1] <= 0:
      ind = ind + 1
  elif (X_sorted[ind][1]%A) != 0:
    count = count + (X_sorted[ind][1]/A) + 1
    X_sorted[ind][1] = 0
    for i in range(ind + 1, N):
      if X_sorted[i][0] <= (X_sorted[ind][0] + 2*D):
        X_sorted[i][1] = X_sorted[i][1] - ((X_sorted[ind][1]/A) + 1)*A
      else:
        break
    ind = ind + 1
  else: 
    count = count + (X_sorted[ind][1]/A)
    for i in range(ind + 1, N):
      if X_sorted[i][0] <= (X_sorted[ind][0] + 2*D):
      	X_sorted[i][1] = X_sorted[i][1] - (X_sorted[ind][1]/A)*A
      else:
        break
    ind = ind + 1
 
print(int(count))

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from bisect import bisect_left as bi_l

n, d, a, *xh = map(int, sys.stdin.read().split())
xh = [(x, ceil(h / a)) for x, h in sorted(zip(*[iter(xh)] * 2))]

def main():
    cnt = 0
    l = 0
    r = []
    s = []
    tmp = 0
    i = 0
    while l < n:
        x, h = xh[l]
        if bi_l(r, x) > i:
            tmp -= s[i]
            i += 1
        if h - tmp <= 0:
            l += 1
            continue
        cnt += h - tmp
        r.append(x + d * 2)
        s.append(h - tmp)
        tmp += h - tmp
        l += 1
    return cnt

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

Submission status: Wrong Answer

Solution code:
def main():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    readline = sys.stdin.readline

    mon = namedtuple('mon', 'x h')

    N, D, A = map(int, readline().split())
    mons = []
    for _ in range(N):
        x, h = map(int, readline().split())
        mons.append(mon(x=x, h=h))
    mons.sort(key=attrgetter('x'))

    imos = [0] * (N + 1)

    bomb = 0
    j = 0
    for i, mon in enumerate(mons):
        while (j + 1 < N) and (mons[j + 1].x - mon.x) <= D * 2:
            j += 1
        count = (mon.h - imos[i] * A + A - 1) // A
        bomb += count

        imos[i] += count
        imos[j + 1] -= count

        imos[i + 1] += imos[i]

    print(bomb)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl
    n, d, a = map(int, input().split())
    xh = [list(map(int, input().split())) for _ in [0]*n]
    xh.sort()
    x_list = [x for x, h in xh]
    ac = [0]*(n+1)
    ans = 0
    temp = 0
    for i in range(n):
        j = xh[i][1]-temp
        if j > 0:
            atk_cnt = (j-1)//a+1
            k = bl(x_list, x_list[i]+2*d)
            ac[i] += a*atk_cnt
            ac[k] -= a*atk_cnt
            ans += atk_cnt
        temp += ac[i]
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import bisect

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

XH.sort()
X, H =  zip(*XH)

K = [-(-h // A) for h in H]
L = [0] * (N + 2)

ans = 0
for i in range(N):
    L[i + 1] += L[i]
    s = max(K[i] - L[i], 0)
    ans += s
    L[i + 1] += s
    L[bisect.bisect_right(X, X[i] + 2 * D) + 1] -= s

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left as bl
    n, d, a = map(int, input().split())
    xh = [list(map(int, input().split())) for _ in [0]*n]
    xh.sort()
    x_list = [x for x, h in xh]
    ac = [0]*(n+1)
    ans = 0
    temp = 0
    for i in range(n):
        j = xh[i][1]-temp
        if j <= 0:
            continue
        atk_cnt = (j-1)//a+1
        k = bl(x_list, x_list[i]+2*d)
        ac[i] += a*atk_cnt
        ac[k] -= a*atk_cnt
        temp += ac[i]
        ans += atk_cnt
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split(" "))
line = []
line_append = line.append
for i in range(N):
    x,h = map(int,input().split(" "))
    
    h //= A
    line_append((x,h))
line.sort()
X = list(map(lambda x: x[0],line))
dmg = [0 for _ in range(N+1)]
ans = 0
for i in range(N):
    x,h = line[i]
    h = max(0,h - dmg[i])
    dmg[i] += h
    dmg[bisect_right(X,x+2*D)] -= h
    dmg[i+1] += dmg[i]
    ans += h

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split(" "))
line = []
line_append = line.append
for i in range(N):
    x,h = map(int,input().split(" "))
    if h % A != 0:
        h //= A+1
    else:
        h //= A
    line_append((x,h))
line.sort()
X = list(map(lambda x: x[0],line))
dmg = [0 for _ in range(N+1)]
ans = 0
for i in range(N):
    x,h = line[i]
    h = max(0,h - dmg[i])
    dmg[i] += h
    dmg[bisect_right(X,x+2*D)] -= h
    dmg[i+1] += dmg[i]
    ans += h

print(ans)