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:
N, D, A = map(int, input().split())
monsters = []
for _ in range(N):
    monsters.append(list(map(int, input().split())))

monsters.sort()
i = 0
ans = 0
while i < N:
    x = monsters[i][0] + D
    attack = monsters[i][1]
    ans += attack
    j = i
    flag = True
    while j < N and monsters[j][0] - D <= x:
        monsters[j][1] -= attack * A
        if monsters[j][1] > 0 and flag:
            i = j
            flag = False
        j += 1
    if flag:
        i = j + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
from math import ceil
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,D,A,*xh = map(int, read().split())
    XH = []
    for x, h in zip(*[iter(xh)] * 2):
        XH.append([x, ceil(h/A)])

    Xn = sorted(XH, key=lambda x:x[0])
    damage = [0]*(N+1)
    ans = 0

    for i in range(N):
        if damage[i] < Xn[i][1]:
            n = Xn[i][1] - damage[i]
            right_end = bisect.bisect_right(Xn, [Xn[i][0]+2*D, 0], lo=i)
            damage[i] += n
            damage[right_end] -= n
            ans += n

        damage[i+1] += damage[i]

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
q = []
index = 0
ans = 0
dmg = 0
for i in range(n):
    if l[i][1] > dmg:
        times = (l[i][1]-dmg)//a if (l[i][1]-dmg)%a == 0 else (l[i][1]-dmg)//a+1
        ans += times
        q.append((l[i][0]+2*d, a*times))
        dmg += a*times
    while index < len(q) and q[index][0] <= l[i][0]:
        dmg -= q[index][1]
        index += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
q = []
index = 0
ans = 0
dmg = 0
for i in range(n):
    if l[i][1] > dmg:
        times = (l[i][1]-dmg)//a if (l[i][1]-dmg)%a == 0 else math.ceil((l[i][1]-dmg)/a)
        ans += times
        q.append((l[i][0]+2*d, a*times))
        dmg += a*times
    if index < len(q) and q[index][0] == l[i][0]:
        dmg -= q[index][1]
        index += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n, d, a = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
q = []
index = 0
ans = 0
dmg = 0
for i in range(n):
    if l[i][1] > dmg:
        ans += math.ceil((l[i][1]-dmg)/a)
        q.append((l[i][0]+2*d, a*math.ceil((l[i][1]-dmg)/a)))
        dmg += a*math.ceil((l[i][1]-dmg)/a)
    if index < len(q) and q[index][0] == l[i][0]:
        dmg -= q[index][1]
        index += 1
print(ans)

Submission status: Wrong Answer

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

monsters.sort()
i = 0
ans = 0
while i < N:
    x = monsters[i][0] + D
    attack = monsters[i][1]
    ans += attack
    j = i
    flag = True
    while j < N and monsters[j][0] - D < x:
        monsters[j][1] -= attack * A
        if monsters[j][1] > 0 and flag:
            i = j
            flag = False
        j += 1
    if flag:
        i = j + 1
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	if (a[-1][0]-a[0][0] <= 2*D):
		max = a[0][1]
		for i in range(1,len(a)):
			if (max<a[i][1]):
				max = a[i][1]
		count = ceil(max/A)
		print (count)
		return
	elif (D==0):
		sum =0
		for i in range(len(a)):
			sum+=a[i][1]
		count = ceil(sum/A)
		print (count)
		return
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,len(a)):
			if (a[i][1]<=0):
				continue
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import math
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	k=0
	while (1):
		d = math.ceil(a[k][1]/A)
		count+=d
		found = 0
		for i in range(k,len(a)):
			if(a[i][0]<=(a[k][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found=1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import *
from heapq import *

N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda k: k[0])
pq = []
ans = 0
S = 0

for i in range(N):
    X, H = XH[i]
    
    while len(pq)>0:
        if pq[0][0]<X:
            t = heappop(pq)
            S -= t[1]
        else:
            break
        
    H -= S
    cnt = (H+A-1)//A
    ans += cnt
    heappush(pq, (X+2*D, cnt*A))
    S += cnt*A

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N,D,A = map(int, input().split())
    enemy = np.zeros((2,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h
    enemy = enemy[:, np.argsort(enemy[0,:])]

    damagemgr = np.zeros((1,2))
    ans = 0
    for i in range(N):
        x,h = map(int, enemy[:,i])
        #print("enm",x,h)

        rmnum = 0
        for dm in damagemgr:
            #print("dm",dm)
            if x > int(dm[1]) :
                h += int(dm[0])
            else:
                rmnum += 1
        damagemgr = damagemgr[rmnum:,:]

        #print(h)
        if h > 0:
            atack = int( (h + A - 1)/A )
            ans += atack
            damage = atack * A
            #print("atk",h,atack,damage)
            damagemgr = np.vstack( (damagemgr, [damage,x+2*D] ) )
            enemy[1,:] -= damage
        #print("")

    """
    while sum( (enemy[1,:]>0) )  :
        #print(enemy)
        atack = int( (enemy[1,0] + A - 1)/A )
        ans += atack
        damage = atack * A
        #print("damage",damage)
        for d_range in range(enemy.shape[1]):
            if enemy[0,d_range] > enemy[0,0] + 2*D : break
        if d_range == enemy.shape[1]-1 and enemy[0,-1] <= enemy[0,0] + 2*D : d_range += 1
        #print("d_range",d_range)
        enemy[1,:d_range] -= damage

        for survive in range(enemy.shape[1]):
            if enemy[1,survive] > 0: break
        enemy = enemy[:,survive:]
        #print("survive",survive,ans)
    """

    print(ans)
    return


"""
def old0208():
    N,D,A = map(int, input().split())
    enemy = np.zeros((3,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h, int(h/A) + (h%A>0)

    farest = int(enemy[0].max()+1)
    enemylist = [0]*farest
    for i in range(N):
        enemylist[ int(enemy[0,i]) ] = enemy[2,i]
    
    ans = 0
    while sum(enemylist)>0:
        pos = [0]*farest
        for i in range(farest):
            pos[i] = sum(enemylist[i-D:i+D+1])
        bestpos = pos.index(max(pos))
        for i in range(bestpos-D,bestpos+D+1):
            if enemylist[i]>0: enemylist[i] = enemylist[i]-1
        ans += 1

    print(ans)
    return
"""

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
XH=[]
for i in range(N):
    x,h=map(int,input().split())
    XH.append([x,h])
# 左側のモンスターを倒していきそのときになるべく右側のモンスターを倒すようにするのが正解？つまりこの場合，なるべく右で爆破すのが良いということ？

XH.sort(key=lambda x: x[0])
X=[x for x,h in (XH)]
H=[h for x,h in (XH)]

# X_l<x<X_l+2Dにダメージを与える．
import bisect
count=0
left = 0
import math
while left<=N-1:
    ind = bisect.bisect_right(X,X[left]+2*D) - 1
    del_ind=[]
    #　条件を満たす複数要素を削除する==条件を満たさない複数要素を残すということ
    # もうめんどくさいので残すことすらやめてしまったよ　
    # 左端が0になるまで減らす．
    attack_num = math.ceil(H[left]/A)
    attack_point = attack_num * A
    for i in range(left,ind+1):
        H[i]-=attack_point
        if H[i]<=0:
            left = i+1
    count+=attack_num
print(count)

Submission status: Wrong Answer

Solution code:
import math
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

xh.sort()

ans = 0
j = len(xh) - 2

for i in range(n):
    xh[i][1] = math.ceil(xh[i][1]/a)

while xh:
    x, h = xh.pop()
    if h <= 0:continue
    j = min(len(xh) - 1, j)
    if j < 0:
        ans += h
        continue
    while xh[j][0]>= x - 2 * d:
        xh[j][1] -= h
        if j<=0:break
        else:j -= 1
    ans += h
    
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

xh.sort()

ans = 0
j = len(xh) - 2

for i in range(n):
    xh[i][1] = math.ceil(xh[i][1]/a)

while xh:
    x, h = xh.pop()
    if h <= 0:continue
    j = min(len(xh) - 1, j)
    if j <= 0:
        ans += h
        continue
    while xh[j][0]>= x - 2 * d:
        xh[j][1] -= h
        if j<=0:break
        else:j -= 1
    ans += h
    
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from math import ceil
def main():
	N,D,A = map(int,input().split())
	XL = [[int(x) for x in input().split()] for _ in range(N)]
	XL = sorted(XL,key = lambda x:x[0])
	X = [XL[i][0] for i in range(N)]
	L = [XL[i][1] for i in range(N)]

	idx = [0 for _ in range(N)]
	for i in range(N):
		idx[i] = bisect_right(X,X[i]+2*D)
	
	ans = 0
	for i in range(N):
		if L[i] == 0:
			pass
		else:
			now = ceil(L[i]/A)
			ans += now
			for j in range(i,idx[i]):
				L[j] -= A*now
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = []
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            attack_count = H // -A * -1
            damege = A * attack_count
            ans += attack_count
            XHN[i][1] -= damege

            acc_damege += damege
            q.append((bomb_p, damege))

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,d,a = mi()
lis = []
for  i in range(n):
    x,h = mi()
    h = (h + a - 1) // a
    lis.append([x,h])

lis.sort()
dis = []
hp = []
for i in range(n):
    dis.append(lis[i][0])
    hp.append(lis[i][1])
#imos?
from collections import deque
hiku = deque()
sums = hp[0]
ans = hp[0]
hiku.append([dis[0] + 2 * d,hp[0]])
imadis,imahp = hiku.popleft()
for i in range(1,n):
    while True:
        if dis[i] >= imadis:
            break
        else:
            sums -= imahp
            if hiku:
                imadis,imahp = hiku.popleft()
            else:
                break
    diff = hp[i] - sums
    if diff > 0:
        ans += diff
        hiku.append([dis[i] + 2 * d,diff])

print(ans)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,d,a = mi()
lis = []
for  i in range(n):
    x,h = mi()
    h = (h + a - 1) // a
    lis.append([x,h])

lis.sort()
dis = []
hp = []
for i in range(n):
    dis.append(lis[i][0])
    hp.append(lis[i][1])
#imos?
from collections import deque
hiku = deque()
sums = hp[0]
ans = hp[0]
hiku.append([dis[0] + 2 * d,hp[0]])
imadis,imahp = hiku.popleft()
for i in range(1,n):
    while True:
        if dis[i] >= imadis:
            break
        else:
            if hiku:
                sums -= imahp
                imadis,imahp = hiku.popleft()
            else:
                break
    diff = hp[i] - sums
    if diff > 0:
        ans += diff
        hiku.append([dis[i] + 2 * d,diff])

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
# Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
from math import ceil
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = ceil(h / a)
    for j in range(i + 1, min(len(xh), x + 2 * d)):
        if xh[j][1] > 0:
            xh[j][1] -= num * a
    cnt += num
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect
from math import ceil


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

location = []
hp = []

for i in range(n):
    x, h = map(int, input().split())
    location.append(x)
    num = ceil(h/a)
    hp.append(num)

location, hp = zip(*sorted(zip(location, hp)))
location = np.array(location)
hp = np.array(hp)

def search_end(index):
    end_location = location[start] + (d * 2) + 1
    end_index = bisect.bisect_left(location, end_location, hi=n) - 1
    return end_index


ans = 0
start = 0
while np.any(hp > 0):
    end = search_end(start)
    if start == end:
        num = hp[start]
        hp[start] -= num
    else:
        num = hp[start]
        hp[start:end+1] -= num
    for i in range(n):
        if hp[start] == 0:
            start +=1
        else:
            break
        if start >= n:
            break
    ans += num

print(ans)

Submission status: Wrong Answer

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

limit = 0
for _ in range(n):
    x, h = map(int, input().split())
    bom.append([x, h])
    limit = max(limit, x)

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

cnt = 0
left = 0
while left < n:
    #print(bom)
    if bom[left][1] > 0:
        right = bom[left][0]+2*d+1
        if bom[left][1] % a != 0: tmp = bom[left][1] // a + 1 
        else: tmp = bom[left][1] // a
        cnt += tmp
        i = left
        #print(bom)
        if right > limit: right = limit
        while i < n and bom[i][0] <= right:
            #print('r', right, bom[i], i)
            bom[i][1] -= a * tmp
            i += 1
    left += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
spot = [0]*n
for i in range(n):
    x, h = map(int, input().split())
    spot[i] = [x, h]
spot.sort()
ans = 0
key = 0
for i in range(n):
    p = spot[i][0]
    if key > p:
        continue
    num_attack = (spot[i][1]-1)//a+1
    ans += num_attack
    damage = a*num_attack
    for j in range(i, n):
        if spot[j][0] <= p + d *2:
            spot[j][1] -= damage
    for j in range(i, n):
        if spot[j][1] <= 0:
            key += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  print(ds)
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import bisect

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*N
b = 0
Xs = [x for x, h in xh]
for i in range(N):
  x, h = xh[i]
  if ds[i]>=h:
    continue
  r = min(x+2*D, xh[-1][0])
  times = h//A if h%A==0 else h//A+1
  for j in range(x, (bisect.bisect_right(Xs, r))):
  	ds[j] += times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = h//A if h%A==0 else h//A+1
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
b = 0
damage_range = [0]*N
for i in range(N):
  x = xh[0][0]
  r = min(x+2*D, xh[-1, 0])
  damage_range[i] = bisect.bisect_right(xh[:, 0], r)
  
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  times = math.ceil(h/A)
  xh[:damage_range[i]] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = h // a
    if h % a != 0:
        num += 1
    xh[i][1] -= num * a
    for j in range(i + 1, len(xh)):
        if xh[j][0] <= x + 2 * d:
            break
        if xh[j][1] > 0:
            xh[j][1] -= num * a
    cnt += num
print(int(cnt))

Submission status: Wrong Answer

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

count = 0
damage_total = 0
q = deque([])

for i in range(n):
    x, h = map(int, input().split())
    while len(q) > 0 and q[0][0] < x:
        damage_total -= q[0][1]
        q.popleft()

    h -= damage_total
    if h > 0:
        count_now = (h + a - 1) // a
        count += count_now
        damage_now = a * count_now
        damage_total += damage_now
        q.append([x + d, damage_now])

print(count)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import math
from bisect import bisect

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = [i[0] for i in xh]
h = [i[1] for i in xh]
#h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h[i]<=0: continue
    h_int =  math.ceil(h[i]/A)
    cnt+=h_int
    r = bisect(x, x[i]+2*D)
    for j in range(i+1, r+1):
      if j>N-1:break
      h[j] = h[j]-h_int*A

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
damage = np.array([0]*N)
b = 0
for i in range(N):
  if damage[i]>=xh[i, 1]:
    continue
  x, h = xh[i]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  damage[:bisect.bisect_right(xh[:, 0], r, i, N)] += times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]))
b = 0
for i in range(N):
  if xh[-1, 1]<=0:
    if all(xh[:, 1]<=0):
    	break
  x, h = xh[i]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]))
b = 0
for _ in range(N):
  if xh[-1, 1]<=0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[1:]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]))
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:r, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, d, a = (int(x) for x in input().split())
xh = np.empty((0, 2))
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh = np.vstack((xh, np.array([x, h])))
xh = xh[np.argsort(xh[:, 0])]
cnt = 0
while True:
    if xh[xh[:, 1] > 0].size == 0:
        break
    xx, hh = xh[(xh[:, 1] > 0)][0]
    num = hh // a
    if hh % a != 0:
        num += 1
    xh[(xh[:, 0] >= xx) & (xh[:, 0] <= xx + 2 * d), 1] -= num * a
    cnt += num
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import bisect

N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]))
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[:bisect.bisect_right(xh[:, 0], r)] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]<=0: continue
    cnt+=h_int[i]
    h_int = np.where(x<x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]))
b = 0
for _ in range(N):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([tuple(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
leng = len(xh)
for _ in range(leng):
  if len(xh)==0:
    break
  x, h = xh[0]
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
leng = len(xh)
for _ in range(leng):
  if all(xh[:, 1]<=0):
    break
  x, h = xh[0]
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[xh[:, 1]>0]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]), dtype=np.int32)
b = 0
for _ in range(len(xh)):
  if all(xh[:, 1]<=0):
    break
  x, h = xh[0]
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[xh[:, 0]<=r] -= times*A
  xh = xh[1:]
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]==0: continue
    cnt+=h_int[i]
    h_int = np.where(x<x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
xh.sort(key=lambda x: x[0])
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if x[i]==0: continue
    cnt+=h_int[i]
    h_int = np.where(x<x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
xs = []
hs = []
for _ in range(N):
  x, h = map(int, input().split())
  xs.append(x)
  hs.append(h)
xs = np.array(xs)
hs = np.array(hs)
hs = hs[np.argsort(xs)]
xs = np.sort(xs)
b = 0
for i, x in enumerate(xs):
  if hs[i]<=0:
    continue
  r = min(x+2*D+1, xs[-1])
  times = math.ceil(hs[i]//A)
  hs[np.where(xs<=r, True, False)] -= times*A
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
N, D, A = map(int, input().split())
maps = {}
for _ in range(N):
  x, h = map(int, input().split())
  maps[x] = h
keys = sorted(maps.keys())
b = 0
for x in keys:
  if maps[x]<=0:
    continue
  r = min(x+2*D+1, keys[-1])
  times = math.ceil(maps[x]//A)
  for k in keys:
    if k<=r:
      maps[k] -= A*times
  b += times
print(b)

Submission status: Wrong Answer

Solution code:
from math import ceil

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

mx = {}
X = []
for i in range(n):
    x, h = map(int, input().split())
    if x in mx:
        mx[x] = max(h, mx[x])
    else:
        mx[x] = h
        X.append(x)
        
X = sorted(X)
ans = 0


for i in range(len(X)):
    if mx[X[i]] <= 0:
        continue
    t = ceil(mx[X[0]] / a)
    ans += t
    HIT = t * a
    D = X[i] + d * 2
    for j in range(i + 1, len(X)):
        if X[j] > D:
            break
        mx[X[j]] -= HIT
        
    
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

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

mx = {}
X = []
for i in range(n):
    x, h = map(int, input().split())
    if x in mx:
        mx[x] = max(h, mx[x])
    else:
        mx[x] = h
        X.append(x)
        
X = sorted(X)
ans = 0

for i in range(len(X)):
    if mx[X[i]] <= 0:
        continue
    t = ceil(mx[X[0]] / a)
    ans += t
    HIT = t * a
    D = X[i] + d * 2
    for j in range(i + 1, len(X)):
        if X[j] > D:
            break
        mx[X[j]] -= HIT
        
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]==0: continue
    cnt+=h_int[i]
    h_int = np.where(x<=x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if h_int[i]==0: continue
    cnt+=h_int[i]
    h_int = np.where(x<x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
x = np.array([i[0] for i in xh])
h = np.array([i[1] for i in xh])
h_int = np.ceil(h/A)

cnt=0
for i in range(len(x)):
    if x[i]==0: continue
    cnt+=h_int[i]
    h_int = np.where(x<x[i]+2*D, h_int-h_int[i], h_int)

print(int(cnt))

Submission status: Wrong Answer

Solution code:
N, D, A = map(int, input().split())
M = []
c = 0
for i in range(N):
    M.append([int(m) for m in input().split()])
for m in M:
    b = m[0]
    c += -(-m[1] // A) 
    for n in M:
        if n[0] >= b and n[0] <= b + 2 * D:
            n[1] -= A * -(-m[1] // A) 
print(c)

Submission status: Wrong Answer

Solution code:

import math

N, D, A = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(N)]
x = [i[0] for i in xh]
h = [i[1] for i in xh]
h_int = [math.ceil(i/A) for i in h]

cnt=0
for i in range(len(x)):
    if x[i]==0: continue
    cnt+=h_int[i]
    for j in range(1, 2*D+1):
        if i+j>len(x)-1:
            break
        
        if x[i+j]<=x[i]+2*D:
            if h_int[i+j]>=h_int[i]:
                h_int[i+j]-=h_int[i]
            else:
                h_int[i+j]=0
        else:
            break

print(cnt)