Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, D, A = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列
    S.sort()
    xs=[0]*N
    hs=[0]*N
    
    for i,s in enumerate(S):
        x,h=s
        xs[i]=x
        hs[i]=h
    tot=[0]*N
    accu=0
    count=0
    for i,x in enumerate(xs):
        accu+=tot[i]
        h=hs[i]-accu*A
        num=math.ceil(h/A)
        accu+=num
        count+=num
        ei=bisect_right(xs,x+2*D)
        if ei<N:
            tot[ei]-=num
    print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()

cnt=0

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
#heapq.heappush(a, -2)

bomb=0
he=[]
heapq.heapify(he)
dic={}

for i in range(n):
    (x,h)=xh[i]

    if bomb==0:
        secchi=x+d
        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        dic[secchi]=damage
        bomb+=damage
        heapq.heappush(he, secchi)
    else:
        while a:
            tmp=heapq.heappop(he)  
            if tmp+d<x:
                bomb-=dic[tmp]
            else:
                heapq.heappush(he, tmp)
                break
            if bomb==0:
                break

        if damage<h:
            h-=damage
            secchi=x+d
            count=((-1*h)//a)*(-1)
            damage=count*a
            cnt+=count
            dic[secchi]=damage
            bomb+=damage
            heapq.heappush(he, secchi)



print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline
 
 
class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
 
        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    def propagates(self, ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0
 
    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(ids)
 
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
 
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


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

    l.sort()
    lh = [h for x,h in l]
    lx = [x for x,h in l]
    tree = LazySegTree(N)
    tree.set_list(lh, N)
    ans = 0

    for i in range(N):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            tree.update(i, min(N, i+2*D+1), -c*A)
            ans += c

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import math
from bisect import bisect_left

n, d, a = map(int, input().split())
x_list = []
max_x = 0
for _ in range(n):
    x, h = map(int, input().split())
    x -= 1
    x_list.append([x, h])
    max_x = max(max_x, x)
x_list.sort()
xx = [x[0] for x in x_list]
ans = 0
for index_left, [x, h] in enumerate(x_list):
    if h > 0:
        ans += math.ceil(h / a)
        index_right = bisect_left(xx, x + (d * 2))
        for i in range(index_left, min(index_right + 1, n)):
            x_list[i][1] -= math.ceil(h / a) * a
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
x_list = []
max_x = 0
xx = []
for _ in range(n):
    x, h = map(int, input().split())
    x -= 1
    x_list.append([x, h])
    xx.append(x)
    max_x = max(max_x, x)
x_list.sort()
xx.sort()
damage_list = {i[0]:0 for i in x_list}
import copy
c = copy.deepcopy(x_list)
import math
from bisect import bisect_left
ans = 0
for index_left, [x, h] in enumerate(c):
    h -= damage_list[x]
    if h > 0:
        ans += math.ceil(h / a)
        index_right = bisect_left(xx, x + (d * 2))
        for i in range(index_left, min(index_right + 1, n)):
            damage_list[xx[i]] += math.ceil(h / a) * a
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,D,A = map(int,input().split())
XH = []
MIN = 10**9
MAX = -1
for i in range(N):
    x,h = map(int,input().split())
    h -= 1
    h //= A
    h += 1
    XH.append([x,h])
    MIN = min(MIN,x)
    MAX = max(MAX,x)
xh = sorted(XH,key = lambda x:x[0])
print(2)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dam = []
de = deque()
ret = 0

for item in xh:
    x, h = item
    left = h
    rem = 0
    for i, val in enumerate(de):
        p, c = val
        if p + d < x:
            rem = i
            continue
        else:
            left -= c * a

    for i in range(rem):
        de.pop()

    if left <= 0:
        continue
    else:
        cnt = (left + a - 1) // a
        ret += cnt
        de.append((x + d, cnt))

print(ret)

Submission status: Wrong Answer

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

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

print(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    while dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
        else:
            break
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)

Submission status: Wrong Answer

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

mons = []

for i in range(n):
    x, h = map(int, input().split())
    mons.append((x, h))

mons = sorted(mons)

q = deque()

dm_sum = 0

ans = 0

for i in range(n):
    if dm_sum > 0:
        if q[0][0] < mons[i][0]:
            cur = q.popleft()
            dm_sum -= cur[1]
    if mons[i][1] <= dm_sum:
        continue
    rem = mons[i][1] - dm_sum
    at_num = rem // a
    if rem % a != 0:
        at_num += 1
    ans += at_num

    q.append((mons[i][0] + 2 * d, at_num*a))
    dm_sum += at_num*a

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,D,A = map(int,input().split())
XH = []
MIN = 10**9
MAX = -1
for i in range(N):
    x,h = map(int,input().split())
    h -= 1
    h //= A
    h += 1
    XH.append([x,h])
    MIN = min(MIN,x)
    MAX = max(MAX,x)
xh = sorted(XH,key = lambda x:x[0])
cnt = xh[0][1]
index = 0
curx = xh[0][0]
curh = xh[0][1]
final = 0
while final == 0:
    for i in range(index+1,N):
        x,h = xh[i]
        if x > curx+2*D:
            index = i
            curx = x
            curh = h
            cnt += h
            if index == N-1:
                final = 1
            break
        else:
            if h <= curh:
                if i == N-1:
                    final = 1
                    break
                else:
                    continue
            else:
                index = i
                curx = x
                curh = h - curh
                cnt += curh
                if index == N-1:
                    final = 1
                break
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,D,A = map(int,input().split())
XH = []
MIN = 10**9
MAX = -1
for i in range(N):
    x,h = map(int,input().split())
    h -= 1
    h //= A
    h += 1
    XH.append([x,h])
    MIN = min(MIN,x)
    MAX = max(MAX,x)
xh = sorted(XH,key = lambda x:x[0])
cnt = 0
index = 0
curx = xh[0][0]
curh = xh[0][1]
final = 0
while final == 0:
    for i in range(index+1,N):
        x,h = xh[i]
        if x > curx+2*D:
            index = i
            curx = x
            cnt += curh
            curh = h
            if index == N-1:
                cnt += curh
                final = 1
            break
        else:
            if h <= curh:
                if i == N-1:
                    cnt += curh
                    final = 1
                    break
                else:
                    continue
            else:
                index = i
                curx = x
                cnt += curh
                curh = h - curh
                if index == N-1:
                    cnt += curh
                    final = 1
                break
print(cnt)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int, input().split())
B=[list(map(int, input().split())) for _ in range(N)]
C=sorted(B)
d,E=zip(*C)
import bisect
Damage=[0]*N
for i in range(N):
  e=bisect.bisect_right(d,d[i]+2*D)
  Damage[i]=e
dd=[0]*(N+1)
cnt=0
for i in range(N):
  g=(E[i]-dd[i])
  if g>0:
    f=-(-g//A)
    cnt+=f
    for j in range(i,Damage[i]+1):
      dd[j]+=A*f
print(cnt)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import deque
import bisect
n,d,a = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
lst.sort()
bx = [float("inf")]*(n+1)
bn = deque([0])
mon = deque(lst)
i = 0
ans = 0
while mon:
    l = deque.popleft(mon)
    x,h = l[0],l[1]
    damage = bn[bisect.bisect_left(bx, x)]
    if h-damage <= 0:
        continue
    h -= damage
    time = ceil(h/a)
    ans += time
    i += 1
    bx[i-1] = x+2*d
    bn.appendleft(bn[0]+time*a)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
from collections import deque

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

acc_damage = 0
que = deque()
ans = 0
for x, h in m:
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    rest_h = max(0, h - acc_damage)
    ans += rest_h
    acc_damage += rest_h

    if rest_h:
        que.append([x + 2 * d, rest_h])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
import bisect,math

n,d,a = map(int,readline().split())
# N: 処理する区間の長さ

INF = 10**9

LV = (n-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
  
xh = []
for _ in range(n):
    x,h = map(int,readline().split())
    xh.append((x,h))
    
xh = sorted(xh)
xl = [x for x,h in xh]
 
for i in range(n):
    update(i,i+1,xh[i][1])
    
ans = 0
for i in range(n):
    hp = query(i,i+1) 
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect(xl,xl[i]+2*d)
        update(i,idx,-damage)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
import bisect,math

n,d,a = map(int,readline().split())
# N: 処理する区間の長さ

INF = 10**9

LV = (n-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
  
xh = []
for _ in range(n):
    x,h = map(int,readline().split())
    xh.append((x,h))
    
xh = sorted(xh)
xl = [x for x,h in xh]
 
for i in range(n):
    update(i+1, i+2, xh[i][1])
    
ans = 0
for i in range(n):
    hp = query(i+1,i+2) 
    if hp > 0:
        count = math.ceil(hp/a)
        ans += count
        damage = count * a
        idx = bisect.bisect_right(xl, xl[i] + 2*d)
        update(i+1,idx+1,-damage)
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int, input().split())
B=[list(map(int, input().split())) for _ in range(N)]
C=sorted(B)[::-1]
b=0
bl=10**10
c=0
for i in range(N):
  if C[i][0]<bl:
    c=(-C[i][1]//A)*(-1)
    bl=C[i][0]-2*D
    b+=c
  elif C[i][0]>=bl and c*A<C[i][1]:
    d=C[i][1]-c*A
    bl=C[i][0]-2*D
    c=(-d//A)*(-1)
    b+=c
print(b)

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()
cnt = 0
bomb = 0
current_bomb = 0
owari = deque([])
for i in range(n):
    x, h = XH[i]
    temp = (h + (a - 1)) // a
    if owari:
        if owari[0][0] < x:
            p, q = owari.popleft()
            current_bomb -= q
    if temp <= current_bomb:
        continue
    delta = temp - current_bomb
    current_bomb += delta
    bomb += delta
    owari.append(((x + 2 * d), delta))
print(bomb)

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()
cnt = 0
bomb = 0
current_bomb = 0
owari = deque([])
for i in range(n):
    x, h = XH[i]
    h //= a
    if owari:
        if owari[0][0] < x:
            p, q = owari.popleft()
            current_bomb -= q
    if h <= current_bomb:
        continue
    delta = h - current_bomb
    current_bomb += delta
    bomb += delta
    owari.append(((x + 2 * d), delta))
print(bomb)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

n, d, a = map(int, input().split())

XH = [list(map(int, input().split())) for _ in range(n)]
XH.sort()
cnt = 0
bomb = 0
current_bomb = 0
owari = []
for i in range(n):
    x, h = XH[i]
    h //= a
    if owari:
        while owari[0][0] < x:
            p, q = heappop(owari)
            current_bomb -= q
            if not owari:
                break
    if h <= current_bomb:
        continue
    delta = h - current_bomb
    current_bomb += delta
    bomb += delta
    heappush(owari, ((x + 2 * d), delta))
print(bomb)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

n, d, a = map(int, input().split())
actions = []
for _ in range(n):
    x, h = map(int, input().split())
    heappush(actions, (x, 0, h // a))
cnt = 0
bomb = 0
current_bomb = 0
while cnt < n:
    a, c, b = heappop(actions)
    if c:
        current_bomb -= b
        continue
    else:
        HP = b
        if HP <= current_bomb:
            cnt += 1
            continue
        else:
            HP -= current_bomb
            cnt += 1
            current_bomb += HP
            bomb += HP
            heappush(actions, (a + 2 * d, 1, HP))
print(bomb)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

n, d, a = map(int, input().split())
actions = []
for _ in range(n):
    x, h = map(int, input().split())
    heappush(actions, (x, h // a, 0))
cnt = 0
bomb = 0
current_bomb = 0
while cnt < n:
    a, b, c = heappop(actions)
    if c:
        current_bomb -= b
        continue
    else:
        HP = b
        if HP <= current_bomb:
            cnt += 1
            continue
        else:
            HP -= current_bomb
            cnt += 1
            current_bomb += HP
            bomb += HP
            heappush(actions, (a + 2 * d, HP, 1))
print(bomb)

Submission status: Wrong Answer

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

n,d,a=map(int,input().split())
xl = []
hl = []
for i in range(n):
    x,h = map(int,input().split())
    xl.append(x)
    hl.append(h)
now = 0
cnt = 0
import bisect
while True:
    r = bisect.bisect_left(xl,now+2*d)
    bomb = max(math.ceil(hl[now]/a),0)
    #print(bomb)
    for i in range(now+1,r):
        hl[i] = min(0,hl[i]-a*bomb)
    now += 1
    cnt += bomb
    if now >= n:
        break

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class LazySegmentTree:

    def __init__(self, array, operator, identity):
        self.identity = identity
        self.operator = operator

        self.array_size = len(array)
        self.tree_height = (self.array_size - 1).bit_length()
        self.tree_size = 2 ** (self.tree_height + 1)
        self.leaf_start_index = 2 ** self.tree_height
        self.tree = [identity] * self.tree_size
        self.lazy = [None] * self.tree_size

        for i in range(self.array_size):
            self.tree[self.leaf_start_index + i] = array[i]

        for i in range(self.leaf_start_index - 1, 0, -1):
            self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])

    def calc_indice(self, begin, end):
        indice = []
        left = self.leaf_start_index + begin
        right = self.leaf_start_index + end

        for i in range(self.tree_height):
            left >>= 1
            right >>= 1
            indice.append(left)
            indice.append(right)

        indice = list(set(indice))
        indice.sort()
        return indice

    def propagates(self, begin, end):
        indice = self.calc_indice(begin, end)

        for index in indice:
            v = self.lazy[index]
            if v is not None:
                self.lazy[index << 1] = v
                self.lazy[index << 1 | 1] = v
                self.tree[index << 1] = self.operator(self.tree[index << 1], v)
                self.tree[index << 1 | 1] = self.operator(self.tree[index << 1 | 1], v)
                self.lazy[index] = None

    def update_node(self, index, val):
        cur_node = self.leaf_start_index + index
        self.tree[cur_node] = val

        while cur_node > 1:
            self.tree[cur_node >> 1] = self.operator(self.tree[cur_node], self.tree[cur_node ^ 1])
            cur_node >>= 1

    def update_range(self, begin, end, val):
        self.propagates(begin, end)
        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                self.lazy[left] = val
                self.tree[left] = self.operator(self.tree[left], val)
                left += 1

            if right & 1:
                right -= 1
                self.lazy[right] = val
                self.tree[right] = self.operator(self.tree[right], val)

            left >>= 1
            right >>= 1

    def query(self, begin, end):
        if begin < 0:
            begin = 0
        elif begin > self.array_size:
            return self.identity
        if end > self.array_size:
            end = self.array_size
        elif end < 1:
            return self.identity

        self.propagates(begin, end)
        res = self.identity

        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                res = self.operator(res, self.tree[left])
                left += 1

            if right & 1:
                right -= 1
                res = self.operator(res, self.tree[right])

            left >>= 1
            right >>= 1

        return res


def main():
    n, d, a = list(map(int, readline().split()))
    xh = [list(map(int, readline().split())) for _ in range(n)]

    from operator import itemgetter, add
    import bisect

    xh.sort(key=itemgetter(0))
    coordinate = [xh[i][0] for i in range(n)]
    hp = [xh[i][1] for i in range(n)]

    ans = 0

    seg = LazySegmentTree(hp, add, 0)

    for i in range(n):
        x = coordinate[i]
        h = seg.query(i, i + 1)

        if h > 0:
            num = (h + a - 1) // a
            ans += num
            dmg = a * num
            range_left = x
            range_right = x + 2 * d
            index_left = bisect.bisect_left(coordinate, range_left)
            index_right = bisect.bisect_right(coordinate, range_right)
            seg.update_range(index_left, index_right, -dmg)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
D2 = 2 * D
XH = [[0, 0] for _ in range(N)]
for i in range(N):
  XH[i][0], Hi = map(int, input().split())
  XH[i][1] = (Hi-1)//A + 1
  
XH.sort()
X = [i[0] for i in XH]
H = [i[1] for i in XH]
l = 0
r = bisect_right(X, X[0]+D2)
ans = 0
while r < N:
  Hl = H[l]
  ans += Hl
  first = True
  nxl = l
  for i in range(l, r):
    if H[i] > Hl:
      H[i] -= Hl
      if first:
        nxl = i
        first = False
  if nxl == l:
    l = r
  else:
    l = nxl
  r = bisect_right(X, X[l]+D2)

ans += max(H[l:])
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
D2 = 2 * D
XH = [[0, 0] for _ in range(N)]
for i in range(N):
  XH[i][0], Hi = map(int, input().split())
  XH[i][1] = (Hi-1)//A + 1
  
XH.sort()
X = [i[0] for i in XH]
H = [i[1] for i in XH]
l = 0
r = bisect_right(X, X[0]+D2)
ans = 0
while True:
  if r == N:
    ans += max(H[l:])
    print(ans)
    exit()
  ans += H[l]
  now = X[l]
  first = True
  nxl = l
  for i in range(l, r):
    if H[i] > H[l]:
      H[i] -= H[l]
      if first:
        nxl = i
        first = False
  if nxl == l:
    l = r
  else:
    l = nxl
  r = bisect_right(X, X[l]+D2)
print(ans)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

dic={}

ans=0
atk_cnt=0
while B:
    x,h=heappop(B)
    if h==-1:
        atk_cnt-=dic[x-1]
        continue
    if h<=A*atk_cnt:
        continue
    sup=x+2*D
    bomb=(h-1)//A+1
    ans+=bomb
    dic[sup]=bomb
    atk_cnt+=bomb
    heappush(B,(sup+1,-1))
    
print(ans)