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:
from collections import deque
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
monster = deque(monster)
ans = 0
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = j
        break
    k = nextk

print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
for k in range(N):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
  for j in range(k, N):
    if monster[j][0] <= nowx + 2*D:
      monster[j][1] -= damage
      continue
    else:
      break

print(ans)

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
for k in range(N):
  if monster[k][0] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
  for j in range(k, N):
    if monster[j][0] <= nowx + 2*D:
      monster[j][1] -= damage
      continue
    else:
      break

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if i<n and j<n:
      sd[j]=e[i][1]+s-mx
      mx=e[i][1]+s
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Wrong Answer

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if i<n and j<n:
    try:
      sd[j]=e[i][1]+s-mx
      mx=e[i][1]+s
    except IndexError:
      pass
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Wrong Answer

Solution code:
n,d,a=list(map(int,input().split()))
e=[]
for i in range(n):
  inp=list(map(int,input().split()))
  inp[1]=(inp[1]-1)//a+1
  e.append(inp)
e.sort()
sd=[0 for i in range(n)]
s=0
mx=0
i=0
j=0
while True:
  while e[i][1]+s<=mx:
    i+=1
    if i>=n:
      break
    s+=sd[i]
  while i<n and j<n and e[j][0]<=e[i][0]+2*d:
    j+=1
  if i<n and j<n:
    try:
      sd[j]=e[i][1]+s-mx
      mx=e[i][1]+s
    except:
      pass
  else:
    if i>=n:
      break
    mx=e[i][1]+s
    
print(mx)

Submission status: Wrong Answer

Solution code:
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  last = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,last)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    if i+2*D+1<=N-1:
      last[i+D+D+1] += damage
    else:
      last[-1] += damage
  return ans
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    explosion = FIFO deque and damage, range
    """
    N, D, A = read_ints()
    XH = []
    for _ in range(N):
        XH.append(read_ints())
    XH.sort()
    explosion = deque([])
    current_damage = 0
    count = 0
    for i in range(N):
        while len(explosion) != 0 and explosion[0][1] < XH[i][0]:
            current_damage -= explosion.popleft()[0]
        if current_damage < XH[i][1]: # damage is not enough
            left_health = XH[i][1]-current_damage
            more_bombs = (left_health//A+(1 if left_health%A != 0 else 0))
            count += more_bombs
            more_damage = more_bombs*A
            current_damage += more_damage
            explosion.append((current_damage, XH[i][0]+2*D))
    return count


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
from bisect import *

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

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

X = []
H = []
for x, h in data:
    X.append(x)
    H.append(h)

Imos = [0]*(N+1)
cnt = 0
damage = 0
res = 0
for i in range(N):
    damage -= Imos[i]*A
    h = H[i] - damage
    x = X[i]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = min(bisect_right(X, x+2*D)-1, N-1)
        Imos[p+1] += cnt
        damage = damage + cnt * A
        res += cnt
print(res)
print(Imos)

Submission status: Wrong Answer

Solution code:
from bisect import *

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

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

X = []
H = []
for x, h in data:
    X.append(x)
    H.append(h)

Imos = [0]*N
cnt = 0
damage = 0
res = 0
for i in range(N):
    h = H[i] - damage
    x = X[i]
    if h > 0:
        cnt = h//A + (h%A!=0)
        p = min(bisect_right(X, x+2*D)-1, N-1)
        Imos[p] += cnt
        damage = damage - Imos[i]*A + cnt * A
        res += cnt
print(res)

Submission status: Wrong Answer

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

hit = []

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

que = deque()
ans = 0
bomb = 0
for i in range(n):
  while que and que[0][0] < hit[i][0]:
    j, d = que.popleft()
    bomb -= d
  r = hit[i][1] - bomb
  if r <= 0:
    continue
  b = -(-r //a)
  ans += b
  bomb += b*a
  que.append((hit[i][0]+2*d,b*a))

print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import ceil

n,d,a = map(int,input().split())
M = [list(map(int,input().split())) for i in range(n)]
M = [[x,ceil(h/a)] for x,h in M]
M = sorted(M)

que = deque()

ans = 0
atack = 0
for x,h in M:
  if len(que) > 0:
    if que[0][0] < x:
      tx,ta = que.popleft()
      atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  if bomb_num > 0:
    que.append([x+d*2,bomb_num])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import ceil

n,d,a = map(int,input().split())
M = [list(map(int,input().split())) for i in range(n)]
M = [[x,ceil(h/a)] for x,h in M]
M = sorted(M)

que = deque()

ans = 0
atack = 0
for x,h in M:
  if len(que) > 0:
    if que[0][0] < x:
      tx,ta = que.popleft()
      atack -= ta      
  
  bomb_num = max(0, h-atack)
  atack += bomb_num
  ans += bomb_num
  
  que.append([x+d*2,bomb_num])

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
N,D,A = map(int,input().split())
monsters = [ list(map(int,input().split())) for _ in range(N) ]
monsters = [ [x, math.ceil(h/A)] for x,h in monsters ]

que = deque()
cur = 0
ans = 0
for x,h in monsters:
  while que and x > que[0][0]:
    _,n = que.popleft()
    cur -= n

  need = max(0, h-cur)
  ans += need
  cur += need

  if h:
    # 対象のモンスターを最も左端にいることを想定
    que.append([x+2*D, need])

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
N,D,A = map(int,input().split())
monsters = [ list(map(int,input().split())) for _ in range(N) ]
monsters = [ [x, math.ceil(h/A)] for x,h in monsters ]

print(monsters)

que = deque()
cur = 0
ans = 0
for x,h in monsters:
  while que and x > que[0][0]:
    _,n = que.popleft()
    cur -= n

  need = max(0, h-cur)
  ans += need
  cur += need

  if h:
    # 対象のモンスターを最も左端にいることを想定
    que.append([x+2*D, need])

print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans,i=0,0
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
while arr[i][1]>0 or arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=(arr[i][1]-1)//a+1
    tmp_i=i
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp*a
      tmp_i+=1
      if tmp_i>=n:
        break
  if i<n-1:
    i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans,i=0,0
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=(arr[i][1]-1)//a+1
    tmp_i=i
    tmp_a=tmp*a
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp_a
      tmp_i+=1
      if tmp_i>=n:
        break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans,i=0,0
for _ in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=-((-arr[i][1])//a)
    tmp_i=i
    tmp_a=tmp*a
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp_a
      tmp_i+=1
      if tmp_i>=n:
        break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=math.ceil(arr[i][1]/a)
    tmp_i=i
    tmp_a=tmp*a
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp_a
      tmp_i+=1
      if tmp_i>=n:
        break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=-((-arr[i][1])//a)
    tmp_i=i
    tmp_a=tmp*a
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp_a
      tmp_i+=1
      if tmp_i>=n:
        break
  i+=1
print(ans+4)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=-((-arr[i][1])//a)
    tmp_i=i
    tmp_a=tmp*a
    ans+=tmp
    while arr[tmp_i][0]<=arr[i][0]+2*d:
      arr[tmp_i][1]-=tmp_a
      tmp_i+=1
      if tmp_i>=n:
        break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=i
    tmp_a=(-((-arr[i][1])//a))*a
    ans+=-((-arr[i][1])//a)
    while arr[tmp][0]<=arr[i][0]+2*d:
      arr[tmp][1]-=tmp_a
      tmp+=1
      if tmp>=n:
        break
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=i
    tmp_a=-((-arr[i][1])//a)*a
    ans+=-((-arr[i][1])//a)
    while arr[tmp][0]<=arr[i][0]+2*d:
      arr[tmp][1]-=tmp_a
      tmp+=1
      if tmp==n:
        break
  if i!=n:
    i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,d,a=map(int,input().split())
arr=[]
ans=0
for i in range(n):
  arr.append(list(map(int,input().split())))
arr.sort()
i=0
while arr[-1][1]>0:
  if arr[i][1]>0:
    tmp=i
    tmp_a=-((-arr[i][1])//a)*a
    ans+=-((-arr[i][1])//a)
    while arr[tmp][0]<=arr[i][0]+2*d:
      arr[tmp][1]-=tmp_a
      tmp+=1
      if tmp==n:
        break
    arr[i][1]=0
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, D, A = NMI()
    M = [NLI() for _ in range(N)]
    M.sort()
    maxj = [0] * N
    j = 0
    for i in range(N):
        while j < N-1:
            if M[j+1][0] <= M[i][0] + D*2:
                j += 1
            else:
                break
        maxj[i] = j
    S = [0]*(N+1)
    attack = [0]*(N+1)
    ans = 0
    for i in range(N):
        x = M[i][0]
        hp = M[i][1] - S[i]
        need = max((hp-1) // A + 1, 0)
        ans += need
        attack[i] += need * A
        attack[maxj[i]+1] -= need * A
        S[i] += attack[i]
        S[i+1] += S[i]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n,d,a = map(int, input().split())
xhl = []
for _ in range(n):
    x,h = map(int, input().split())
    cnt = (h-1)//a + 1
    xhl.append((x,cnt))

attack_q = deque([])
attack_sum = 0
ans = 0
for x,h in xhl:
    while attack_q and attack_q[0][0] < x:
        poped_cnt = attack_q.popleft()[1]
        attack_sum -= poped_cnt
    rem = h-attack_sum
    if rem <= 0:
        continue
    attack_sum += rem
    ans += rem
    attack_q.append((x+2*d, rem))

print(ans)

Submission status: Wrong Answer

Solution code:

def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()

    # imos
    
    imos = [0] * 201010
    ans = 0
    R = 0
    for l in range(N):
        if l:
            imos[l] += imos[l - 1]
        x = AB[l][0]
        h = AB[l][1]
        if imos[l] < h:
            R = max(R, l + 1)
            while R < N and AB[R][0] - x <= 2 * D:
                R += 1
            d = h - imos[l]
            cnt = d // A
            imos[l] += cnt * A
            imos[R] -= cnt * A
            ans += cnt
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import math
import bisect
 
n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0

x.sort()
x.append(1145141919810)
h.append(0)

imos = [0]*(n+1)

atk = math.ceil(itv[i][1]/a)
imos[0] += atk * a
b = bisect.bisect(x,itv[0][0] + (2*d))
imos[b] -= atk * a
ans += atk
    
for i in range(1,n):
    atk = 0
    imos[i] += imos[i-1]
    if itv[i][1] > imos[i]:
        atk = math.ceil((itv[i][1]-imos[i])/a)
        imos[i] += atk * a
        b = bisect.bisect(x,itv[i][0] + (2*d))
        imos[b] -= atk * a
    ans += atk

print(ans)

Submission status: Wrong Answer

Solution code:
def binary(N,LIST,num):  # 二分探索 # N:探索要素数
    l, r = -1, N
    while r - l > 1:
        if LIST[(l + r) // 2] > num:  # 条件式を代入
            r = (l + r) // 2
        else:
            l = (l + r) // 2
    return r + 1


n, d, a = map(int, input().split())
xh = sorted(list(map(int, input().split())) for _ in range(n))
x = [i for i, j in xh]
h = [j for i, j in xh]

bomb, bsum, ans = [0] * (n + 1), [0] * (n + 1), 0
for i, xi in enumerate(x):
    j = binary(n, x, xi + 2 * d) - 1
    bsum[i] += bsum[i - 1] + bomb[i]
    bnum = max((h[i] - bsum[i])//a, 0)
    bomb[i] += bnum
    bomb[j] -= bnum
    bsum[i] += bnum
    ans += bnum
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

x = []
h = []
for d, i in sorted(X):
    x.append(d)
    h.append(i)

ans = 0
k = [-(-v // A) for v in h]
y = [0] * (N + 2)
for i in range(N):
    y[i + 1] += y[i]
    s = max(0, k[i] - y[i + 1])
    ans += s
    y[i + 1] += s
    y[bisect_left(x, x[i] + 2 * D) + 1] -= s
    
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

class BIT:
    def __init__(self, n):
        self.n = n + 1
        self.dat = [[0] * self.n for _ in range(2)]
        
    def _add_body(self, p, i, x):
        while i < self.n:
            self.dat[p][i] += x
            i += i & -i
            
    def add(self, l, r, x):
        # Add x to [l, r]
        self._add_body(0, l, -x * (l - 1))
        self._add_body(1, l, x)
        self._add_body(0, r + 1, x * r)
        self._add_body(1, r + 1, -x)
        
    def _query_body(self, p, i):
        res = 0
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def query(self, l, r):
        # Return sum of [l, r]
        res = 0
        res += self._query_body(0, r)
        res += self._query_body(1, r) * r
        res -= self._query_body(0, l - 1)
        res -= self._query_body(1, l - 1) * (l - 1)
        return res


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

bit = BIT(N)
x = [-1]
for i, (d, h) in enumerate(sorted(X)):
    x.append(d)
    bit.add(i + 1, i + 1, h)

ans = 0
for i in range(1, N + 1):
    j = bisect_left(x, x[i] + 2 * D)
    h = bit.query(i, i)
    if h > 0:
        n = -(-h // A)
        ans += n
        bit.add(i, j, -n * A)
    
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

class BIT:
    def __init__(self, n):
        self.n = n + 1
        self.dat = [[0] * self.n for _ in range(2)]
        
    def _add_body(self, p, i, x):
        while i < self.n:
            self.dat[p][i] += x
            i += i & -i
            
    def add(self, l, r, x):
        # Add x to [l, r]
        self._add_body(0, l, -x * (l - 1))
        self._add_body(1, l, x)
        self._add_body(0, r + 1, x * r)
        self._add_body(1, r + 1, -x)
        
    def _query_body(self, p, i):
        res = 0
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def query(self, l, r):
        # Return sum of [l, r]
        res = 0
        res += self._query_body(0, r)
        res += self._query_body(1, r) * r
        res -= self._query_body(0, l - 1)
        res -= self._query_body(1, l - 1) * (l - 1)
        return res


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

bit = BIT(N)
x = [-1]
for i, (d, h) in enumerate(sorted(X)):
    x.append(d)
    bit.add(i + 1, i + 1, h)

ans = 0
for i in range(1, N + 1):
    j = bisect_left(x, x[i] + 2 * D)
    h = bit.query(i, i)    
    if h > 0:
        ans += -(-h // A)
        bit.add(i, j, -h)
    
print(ans)

Submission status: Wrong Answer

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

enems = []
for i in range(N):
  enemy = list(map(int, input().split()))
  enems.append(enemy)

# enemsをXをkeyとしてsort (nlogn)
# 貪欲法でx = X_i + Dとなるような位置で爆弾をH_0//A回投げてX_iの敵を倒す。これをi=0, 1, ...と繰り返す
enems.sort(key=lambda enemy: enemy[0])

centers = []
counts = []

for i, enemy in enumerate(enems):
  # 他の敵を狙った爆弾でHが減っている場合
  for j, cent in enumerate(centers):
    if enemy[0] in [cent-D, cent+D]:
      enemy[1] -= counts[j] * A
      enemy[1] = max(0, enemy[1])
      
  # x = X_0 + D
  center = enemy[0] + D
  centers.append(center)
  
  count = enemy[1] // A
  if enemy[1] % A:
    count += 1
  enemy[1] = 0  # 必要ない？
  counts.append(count)

print(sum(counts))

Submission status: Wrong Answer

Solution code:
import bisect


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            print(self.N, i)
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    if N == 1:
        print((monsters[0][1] + A - 1) // A)
        return
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import itertools
import sys

input=sys.stdin.readline

def main(args):
    n, d, a = map(int,input().split())
    
    monster = [0]*n
    pos = [0]*n
    for i in range(n):
        x, h = map(int,input().split())
        monster[i] = (x, h)
        pos[i] = x
    
    pos.sort()
    monster.sort()
    
    #print(pos)
    
    limit = [0]*n
    #そのモンスターを攻撃したとき巻き添えにできるやつらの中で一番右のヤツのindex
    for i in range(n):
        limit[i] = bisect.bisect_right(pos, pos[i]+2*d)-1
    #print(limit)
    
    damage = [0]*n
    right = n-1
    left = 0
    for i in range(n):
        HP = monster[i][1]
        if i <= right:
            attack = -(-max(0, (HP-a*damage[left]))//a)
        if attack > 0:
            damage[i] += attack
            right = limit[i]
            left = i
        #print(damage)
            
    ans = list(itertools.accumulate(damage))
    print(ans[n-1])

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

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

xh = sorted(xh)
x_list = [i for i, _ in xh]
h_list = [i for _, i in xh]
cnt = 0
start_idx = 0
end_idx = 1
for i in range(N):
    start_idx = i
    if h_list[start_idx] == 0:
        continue

    for idx, (x,_) in enumerate(xh[end_idx-1:], end_idx-1):
        if x > x_list[start_idx] + 2*D:
            
            end_idx = idx
            break
        if idx == N-1:
            end_idx = N
            
    
    h = h_list[start_idx]
    cnt += (h//A) + (h%A!=0)
    for idx in range(start_idx, end_idx):
        h_list[idx] -= h
print(cnt)

Submission status: Wrong Answer

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

xh = sorted(xh)
x_list = [i for i, _ in xh]
h_list = [i for _, i in xh]
cnt = 0

for i in range(N):
    start_idx = i
    if h_list[start_idx] == 0:
        continue

    for idx, (x,_) in enumerate(xh[start_idx:], start_idx):
        if x > x_list[start_idx] + 2*D:
            
            end_idx = idx
            break
        if idx == N-1:
            end_idx = N
            
    
    h = h_list[start_idx]
    cnt += (h//A) + (h%A!=0)
    for idx in range(start_idx, end_idx):
        h_list[idx] -= h
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect
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])
attackloc = list(map(lambda x:x[0]+d, monster ))
left =list(map(lambda x: max(x[0]-d,0), monster ))
#right=[]
damage=[0]*n
#print(monster)
#print(attackloc)
#print(left)
ans = 0
counter = 0
while damage[n-1]<monster[n-1][1]:
  loc = attackloc[counter]
  at = bisect.bisect_right(left, loc)
  multi = (monster[counter][1]-damage[counter])//a
  if  (monster[counter][1]-damage[counter])%a != 0:
    multi+=1
  #print(at)
  for i in range(at):
    damage[i]+=a*multi
  ans+=multi
  while counter < n-1 and damage[counter]>=monster[counter][1]:
    counter+=1
  #print(damage)
  #print(counter)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

n, d, a = map(int, input().split())
lxh = [tuple(map(int, input().split())) for _ in range(n)]

lxh.sort()
lx, lh = [], []
for x, h in lxh:
    lx.append(x)
    lh.append(h)

n_bomb = 0
total_damage = 0
subtract = [0 for _ in range(n + 1)]

for i in range(n):
    x = lx[i]
    h = lh[i] - total_damage

    if h > 0:
        n_bomb += -(-h // a)
        damage = -(-h // a) * a
        total_damage += damage

        i_sub = bisect_right(lx, x + 2 * d) - 1
        subtract[i_sub] += damage

        total_damage -= subtract[i]

print(n_bomb)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, d, a = map(int, input().split())
    XH = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    total = 0
    end = deque([])
    for i in range(n):
        x, h = XH[i]
        while end and end[0][0] < x:
            r = end.popleft()
            total -= r[1]

        if total < h:
            res += ((h - total) + a - 1) // a
            end.append([x + (2 * d + 1), ((h - total + a - 1) // a) * a])
            total += ((h - total + a - 1) // a) * a
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-1//a)+1
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()
d=2*d
ans=0
total=0
q=deque()
for i in range(n):
  x,h=xh[i]
  while len(q)>=1 and x>q[0][0]:
    total-=q.popleft()[1]
  h-=total
  if h>0:
    num=(h-h%a)//a
    damage=a*num
    ans+=num
    total+=damage
    q.append([x+d,damage])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, d, a = ns()
    x = []
    for _ in range(n):
        xi, hi = ns()
        x.append([xi, hi])

    x.sort()
    x.append([INF, INF])

    perm = [0 for _ in range(n + 1)]
    idx = [xi for xi, hi in x]

    ans = 0
    cnt = 0
    for i in range(n):
        cnt -= perm[i]

        if x[i][1] - cnt * a > 0:
            tmp = ((x[i][1] - cnt * a) + a - 1) // a
        else:
            tmp = 0
        ans += tmp
        cnt += tmp

        if cnt > 0:
            tmp_idx = bisect.bisect_right(idx, x[i][0] + 2 * d)
            perm[tmp_idx] += cnt

    print(ans)


if __name__ == '__main__':
    main()