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())
attack = [0 for _ in range(n)]
event = []
for i in range(n):
  x,h = map(int,input().split())
  h //= a
  event.append([x-d,0,h,i])
  event.append([x+d,1,h,i])
event.sort()
#print(event)
ans = 0
now = 0
for j in range(2*n):
  x,m,h,i = event[j]
  if m == 0:
    if h > now:
      attack[i] += h-now
      ans += h-now
      now = h
  else:
    now -= attack[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque 
n, d, a = map(int, input().split())
x, h = [0]*n, [0]*n
for i in range(n):
    x[i], h[i] = map(int, input().split())

x, h = zip(*sorted(list(zip(x, h))))
x, h = list(x), list(h)

l, r = 0, 1
m = [0] * n

while r < n:
    if x[r] - x[l] <= 2*d:
        r += 1
    else:
        m[l] = r-1
        l += 1
m[l:r] = [r-1]*(r-l)
m = deque(m)

l = 0
attcnt = deque([])
dam = 0
for i in range(n):
    if h[i] - dam < 1: 
        ac = 0
    else:
        if a == 1:
            ac = h[i] - dam
        else :
            ac = math.ceil(math.log(h[i]-dam, a))
        
    dam += ac * a
    attcnt.append(ac)
    
    while m and i == m[0]:
        m.popleft()
        dam -= attcnt[l]*a
        l += 1

print(sum(attcnt))

Submission status: Wrong Answer

Solution code:
class T:
    def __init__(self,X=0,H=0):
        self.X=X
        self.H=H
MAX = 200005
a = [T() for i in range(MAX+1)]


def usort(t,n):
    B = 8
    BMSK = 255
    tmp = [T() for i in range(n+1)]
    for k in range(4):
        t1 = [0]*(1 << B)
        t2 = [0]*(1 << B)
        for i in range(n):
            t1[(a[i].X >> k*B) & BMSK]+=1
        for i in range(BMSK):
            t1[i+1]+=t1[i]
        i = n
        while i:
            i-=1
            t1[(a[i].X >> k*B) & BMSK]-=1
            tmp[t1[(a[i].X >> k*B) & BMSK]] = a[i]
        k+=1
        for i in range(n):
            t2[(tmp[i].X >> k*B) & BMSK]+=1
        for i in range(BMSK):
            t2[i+1]+=t2[i]
        i = n
        while i:
            i-=1
            t2[(tmp[i].X >> k*B) & BMSK]-=1
            a[t2[(tmp[i].X >> k*B) & BMSK]] = tmp[i]
    del tmp, t1, t2
def bs(l, x):
    r = N + 1

    while (l<r):
        m = (l+r) >> 1
        if a[m].X <=x:
            l = m + 1
        else:
           r = m
    return l-1

imos = [0] * MAX

N, D, A = map(int, input().split())
D <<= 1
for i in range(N):
    a[i].X, a[i].H = map(int,input().split())
usort(a, N)

ans, j = 0,1
for i in range(N):
    imos[i] += imos[i-1]
    h = a[i].H - imos[i]
    if h>0:
        t = (h-1)//A + 1
        ans += t
        t *= A
        j = bs(j, a[i].X + D)
        imos[i] += t
        imos[j + 1] -= t
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n, d, a = map(int, input().split())
x, h = [0]*n, [0]*n
for i in range(n):
    x[i], h[i] = map(int, input().split())

x, h = zip(*sorted(list(zip(x, h))))
x, h = list(x), list(h)

l, r = 0, 1
m = [0] * n

while r < n:
    if x[r] - x[l] <= 2*d:
        r += 1
    else:
        m[l] = r-1
        l += 1
m[l:r] = [r-1]*(r-l)

dam = 0
ans = 0

for i in range(n):
    if h[i] - dam < 1: ac = 0
    else : 
        if a == 1:
            ac = h[i] - dam
        else :
            ac = math.ceil(math.log(h[i]-dam, a))
    ans += ac
    
    if i+1 <= m[i]:
        dam += ac * a

print(ans)

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()])
while len(M) > 0:
    b = M[0][0]
    c += 1
    for m in M[:]:
        if m[0] >= b and m[0] <= b + 2 * D:
            m[1] -= A
            if m[1] <= 0:
                M.remove(m)
print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = [tuple(map(int, input().split())) for _ in range(n)]
xh.sort()
x, h = zip(*xh)
h = list(map(lambda x: -(-x//a), h))

ends = [0] * n
cum, ans = 0, 0

for i in range(n):
    cum -= ends[i]
    add = h[i] - cum
    j = bisect_right(x, x[i]+d*2)
    if j < n: ends[j] += add
    cum += add
    ans += add

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_right

n, d, a = map(int, input().split())
xh = [tuple(map(int, input().split())) for _ in range(n)]
xh.sort()
x, h = zip(*xh)
h = list(map(lambda x: -(-x//a), h))

ends = [0] * n
cum, ans = 0, 0

for i in range(n):
    cum -= ends[i]
    add = h[i] - cum

    j = bisect_right(x, x[i]+d*2+1)
    if j < n: ends[j] += add

    cum += add
    ans += add

print(ans)

Submission status: Wrong Answer

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

D = True

pos = []
pos1 = []

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

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

bombs = 0
damage = 0
y, z = 0, 0


while y < n:
	x0 = pos[y][0]
	try:
		x1 = pos1[z][0]
	except IndexError:
		x1 = 1e16
	if x0 <= x1:
		health = pos[y][1]
		health -= damage
		number = (health-1) // a + 1
		bombs += number
		damage += number*a
		pos1.append((x0+2*d, number*a))
		y+=1
	else:
		damage -= pos1[z][1]
		z += 1
	

print(bombs)

Submission status: Wrong Answer

Solution code:
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]


d=2*d
i,ans,damages=0,0,[0]*n
while i<n:
  if i>0:
    damages[i]+=damages[i-1]
    s=hp[i]+damages[i]
  else:
    s=hp[i]
  cnt=(s+a-1)//a
  ans+=cnt
  damage=cnt*a
  damages[i]-=damage
  zone=bisect(r,r[i]+d)
  if zone<n:
    damages[zone]+=damage 
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n, d, a = map(int, input().split())
l = [[0, 0] for _ in range(n)]
for i in range(n):
  x, h = map(int, input().split())
  l[i][0] = x
  l[i][1] = h
  
l.sort()
print(l)
from collections import deque
d = 2*d
q = deque([])
total = 0

ans = 0
for i in range(n):
  x = l[i][0]
  h = l[i][1]
  if q:
    while q[0][0] < x:
      total -= q[0][1]
      q.popleft()
      if not q:
        break
  h -= total
  if h > 0:
    num = (h+a-1)//a
    ans += num
    damage = num*a
    total += damage
    q.append([x+d, damage])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, d, a = map(int, input().split())
xh = np.array(sorted(tuple(map(int, input().split())) for _ in range(n)))
x, h = xh[:, 0], xh[:, 1]

brange, r = [], 1
for l in range(n):
    while r < n and x[l]+2*d >= x[r]:
        r += 1
    brange.append((l,r-1))

bt, cumsum, imos = 0, 0, np.zeros(n, dtype=int)
for i in range(n):
    t = -int(-max(h[i]-cumsum, 0)) // a
    imos[brange[i][0]] += a*t
    imos[brange[i][1]] -= a*t
    cumsum += imos[i]
    bt += t

print(bt)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, d, a = map(int, input().split())
xh = np.array(sorted(tuple(map(int, input().split())) for _ in range(n)))
x, h = xh[:, 0], xh[:, 1]

brange, r = [], 1
for l in range(n):
    while r < n and x[l]+2*d >= x[r]:
        r += 1
    brange.append((l,r-1))

bt, cumsum, imos = 0, 0, np.zeros(n, dtype=int)
for i in range(n):
    t = -int(-h[i]+cumsum)//a
    imos[brange[i][0]] += a*t
    imos[brange[i][1]] -= a*t
    cumsum += imos[i]
    bt += t

print(bt)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, d, a = map(int, input().split())
xh = np.array(sorted(tuple(map(int, input().split())) for _ in range(n)))
x, h = xh[:, 0], xh[:, 1]

b, r = [], 1
for l in range(n):
    while r < n and x[l]+2*d >= x[r]:
        r += 1
    b.append((l,r-1))

bt, cumsum, imos = 0, 0, np.zeros(n, dtype=int)
for i in range(n):
    cumsum += imos[i-1]
    t = -int(-h[i]+cumsum)//a
    imos[b[i][0]] += a*t
    imos[b[i][1]] -= a*t
    bt += t

print(bt)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int, input().split())
ps = []
def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])

ps.sort()
damage = 0
cnt = 0
q = deque([])
for x,h in ps:
    while len(q) > 0 and q[0][0] < x:
        # 範囲外のものはダメージを与えられない
        _, d = q.popleft()
        damage -= d
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    num = ceil(h_rest, A)
    damage += num * A
    cnt += num
    r = x + 2*D
    q.append((r,damage))
print(int(cnt))

Submission status: Wrong Answer

Solution code:
from collections import deque
N,D,A = map(int, input().split())
ps = []
def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])

ps.sort()
damage = 0
cnt = 0
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        r, d = q.popleft()
        if r < x:
            damage -= d
        # 範囲内なのでもとに戻す
        else: 
            q.appendleft((r,d))
            break
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    num = ceil(h_rest, A)
    damage += num * A
    cnt += num
    r = x + 2*D
    q.append((r,damage))
print(int(cnt))

Submission status: Wrong Answer

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

ps = []
xs = []
def ceil(a,b):
    return -(-a//b)
    # return (a+b-1)//b

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])

ps.sort()
# その物体に与えうるダメージ
damage = 0
cnt = 0
from collections import deque
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        r, d = q.pop()
        if r < x:
            damage -= d
        # 範囲内なのでもとに戻す
        else: 
            q.appendleft((r,d))
            break
    # 残りダメージ
    h_rest = h - damage
    if h_rest > 0: 
        damage += ceil(h_rest, A) * A
        cnt += ceil(h_rest,A)
        r = x + 2*D
        q.append((r,damage))
print(int(cnt))

Submission status: Wrong Answer

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

ps = []
xs = []
def ceil(a,b):
    # return -(-a//b)
    return (a+b-1)//b

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])

ps.sort()
# その物体に与えうるダメージ
damage = 0
cnt = 0
from collections import deque
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        r, d = q.pop()
        if r < x:
            damage -= d
        # 範囲内なのでもとに戻す
        else: 
            q.appendleft((r,d))
            break
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    damage += ceil(h_rest, A) * A
    cnt += ceil(h_rest,A)
    r = x + 2*D
    q.append((r,damage))
print(cnt)

Submission status: Wrong Answer

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

ps = []
xs = []
def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])

ps.sort()
# その物体に与えうるダメージ
damage = 0
cnt = 0
from collections import deque
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        r, d = q.pop()
        if r < x:
            damage -= d
        # 範囲内なのでもとに戻す
        else: 
            q.appendleft((r,d))
            break
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    damage += ceil(h_rest, A) * A
    cnt += ceil(h_rest,A)
    r = x + 2*D
    q.append((r,damage))
print(cnt)

Submission status: Wrong Answer

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

ps = []
xs = []
def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])
    xs.append(x)

ps.sort()
xs.sort()
# その物体に与えうるダメージ
damage = 0
cnt = 0
from collections import deque
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        r, d = q.pop()
        if r < x:
            damage -= d
        else: 
            q.appendleft((r,d))
            break
    # 残りダメージ
    h_rest = h - damage
    if h_rest <= 0: continue
    damage += ceil(h_rest, A) * A
    cnt += ceil(h_rest,A)
    r = x + 2*D
    q.append((r,damage))
print(cnt)

Submission status: Wrong Answer

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

ps = []
xs = []
def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])
    xs.append(x)

ps.sort()
xs.sort()
# その物体に与えうるダメージ
damage = 0
cnt = 0
from collections import deque
q = deque([])
for x,h in ps:
    while len(q) > 0:
        # 範囲外のものはダメージを与えられない
        if q[0][0] < x:
            _, d = q.pop()
            damage -= d
        else: break
    # 残りダメージ
    h_rest = h - damage
    if h_rest < 0: continue
    damage += ceil(h_rest, A) * A
    cnt += ceil(h_rest,A)
    r = x + 2*D
    q.append((r,damage))
print(cnt)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,d,a = LI()
    xh = sorted([LI() for _ in range(n)])
    r = 0
    k = 0
    t = []
    ti = 0
    for x,h in xh:
        while len(t) > ti and t[ti][0] < x:
            k -= t[ti][1]
            ti += 1
        h -= k
        if h <= 0:
            continue
        u = (h+a-1) // a
        r += u
        k += u * d
        t.append((x+d*2, u*d))

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,d,a = LI()
    xh = sorted([LI() for _ in range(n)])
    r = 0
    k = 0
    t = []
    ti = 0
    for x,h in xh:
        while len(t) > ti and t[ti][0] < x:
            k -= t[ti][1]
            ti += 1
        h -= k
        u = (h+a-1) // a
        if u <= 0:
            continue
        r += u
        k += u * d
        t.append((x+d*2, u*d))

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,d,a = LI()
    xh = sorted([LI() for _ in range(n)])
    r = 0
    k = 0
    t = []
    ti = 0
    for x,h in xh:
        while len(t) > ti and t[ti][0] < x:
            k -= t[ti][1]
            ti += 1
        h -= k
        u = (h+a-1) // a
        if u <= 0:
            continue
        r += u
        k += u * d
        t.append((x+d*2+1, u*d))

    return r


print(main())

Submission status: Wrong Answer

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

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

ans=0
for i in range(len(XH)):
    if XH[i][1] <= 0:
        continue

    while XH[i][1] > 0:
        r = 2*D + 1   
        XH[i][1] -= A
        ans += 1
        for j in range(i+1, len(XH)):
            if XH[i][0] + r > XH[j][0]:
                XH[j][1] = -A
            else:
                break
        
print(ans)

Submission status: Wrong Answer

Solution code:
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def F_symulacja():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()
    wynik = 0
    while len(monstery) > 0:
        x, h = monstery[0]
        if h <= 0:
            monstery.pop(0)
            continue
        bomba_x = x + D
        wynik += 1
        for i in range(len(monstery)):
            x_i, h_i = monstery[i]
            if bomba_x - D <= x_i <= bomba_x + D:
                monstery[i] = (x_i, h_i - A)

    print(wynik)

def zabij(H, A):
    if H % A == 0:
        return H // A
    else:
        return H // A + 1

def F():
    N, D, A = wczytaj_liste()
    monstery = []
    for i in range(N):
        x, h = wczytaj_liste()
        monstery.append((x, h))
    monstery.sort()

    wynik = 0
    gdzie_sie_koncza_bomby = []
    skonczone = 0
    ile_tu_spadlo = 0
    for x, h in monstery:
        while len(gdzie_sie_koncza_bomby) > skonczone:
            bomby_do, ile_bomb = gdzie_sie_koncza_bomby[skonczone]
            if bomby_do < x:
                ile_tu_spadlo -= ile_bomb
                skonczone += 1
            else:
                break
        if h - ile_tu_spadlo * A > 0:
            zrzucam_tutaj = zabij(h - ile_tu_spadlo, A)
            wynik += zrzucam_tutaj
            ile_tu_spadlo += zrzucam_tutaj
            gdzie_sie_koncza_bomby.append((x + 2 * D, zrzucam_tutaj))
    print(wynik)

F()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

bit=[ 0 for _ in range(N+1) ]

#BIT 関数は全て1-indexed
def add(a,w):
    while a<=N:
        bit[a]+=w
        a+=a&-a

def sum(a):
    ret=0
    while 0<a:
        ret+=bit[a]
        a-=a&-a
    return ret

#区間[l,r]に一律wを加える
def range_add(l,r,w):
    add(l,w)
    add(r+1,w*-1)

#a番目のモンスターの体力を取得
def get_value(a):
    return sum(a)

X=[float("-inf")]
H=[float("-inf")]
for x,h in XH:
    X.append(x)
    H.append(h)

for i in range(1,N+1):
    if i==1:
        add(i,H[i])
    else:
        add(i,H[i]-H[i-1])  #区間に対する更新ができるBITを作成するために、値の差分をBITに持つ
    
ans=0

for i in range(1,N+1):
    h=get_value(i)
    if h<=0:    #モンスターの体力がゼロ以下だったら何もしない
        pass
    else:
        x=X[i]
        pos=bisect_right(X,i+2*D)-1 #攻撃範囲の一番右側を二分探索で決定
        if h%A==0:   #hがAで割り切れる場合
            cnt=h/A
            range_add(i,pos,A*cnt*-1)
        else:
            cnt=h/A+1   #hをAで割って余りが出る場合は攻撃回数を+１する
            range_add(i,pos,A*cnt*-1)
        ans+=cnt

print ans

Submission status: Wrong Answer

Solution code:
import bisect
n,d,a = map(int,input().split())
L = []
T = []
U = []
hitpoint = []
for i in range(n):
  p,q = map(int,input().split())
  L.append([p,q,0])
  T.append(p)
  U.append(p)
  hitpoint.append(q)
U.sort()
for i in range(n):
  k = bisect.bisect_right(U,T[i]+2*d)
  L[i][2] = k
L.sort()
start = 0
ans = 0
while start != n:
  t = hitpoint[start]//a
  if hitpoint[start]%a == 0:
    attack = t
  else:
    attack = t+1
  ans += attack
  cur = attack*a
  look = L[start][2]
  flag = False
  ne = 0
  for i in range(look-start):
    if start+i <= n-1:
      if (hitpoint[start+i] - cur <= 0):
        hitpoint[start+i] = 0
      else:
        if not flag:
          ne = i
          flag = True
        hitpoint[start+i] -= cur
  if ne == 0:
    start += 1
  else:
    start += ne
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

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

q=deque()   #（攻撃の終了座標、終了によって無効になる攻撃ポイント）

ans=0
attack_point=0  #攻撃で減らせるポイント

for i in range(N):
    x,h=X[i],H[i]
    while q:
        if x<q[0][0]:   #カレントの座標が、q[0][0]:攻撃終了の座標より小さい場合はどの攻撃も終了しない
            break
        end_x=q[0][0]
        end_x,end_p=q.popleft()
        attack_point-=end_p #終了する攻撃があれば、その分奪い取れるポイントは減る
    h-=attack_point #まずはモンスターの体力を減らせるだけ減らす  
    if h<=0:
        pass
    else:   #まだモンスター体力hがゼロより大きい場合は場合は追加の攻撃を行う
        if h%A==0:
            cnt=h/A
        else:
            cnt=h/A+1
        ans+=cnt
        atttack_end_x=bisect_right(X,x+2*D) #攻撃の終了座標
        atttack_add_p=A*cnt                 #新規攻撃に追加されたポイント
        attack_point+=atttack_add_p
        q.append((atttack_end_x,atttack_add_p))

print ans

Submission status: Wrong Answer

Solution code:
import bisect
N,D,A=map(int,input().split())
X=[0 for i in range(N)]
H=[0 for i in range(N)]
Monster=[]
for i in range(N):
    Monster.append(tuple(map(int,input().split())))
Monster.sort()
X=[Monster[i][0] for i in range(N)]
H=[Monster[i][1] for i in range(N)]
#print(X)
#print(H)
seq=[0 for i in range(N)]
#X[seq[i]]<=2D+X[i]
for i in range(N):
    seq[i]=bisect.bisect_left(X,2*D+1+X[i])
#print(seq)
#range(i,seq[i])
'''
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+H[i]
print(S)
'''
ans=-(-H[0])//A
S=[0 for i in range(N+1)]
K=[0 for i in range(N)]
S[0]+=H[0]
S[seq[0]]-=H[0]
tmp=0
#print(0,ans,S)
for i in range(1,N):
    tmp+=S[i-1]
    if H[i]>tmp:
        a=-((tmp-H[i])//A)
        ans+=a
        S[i]+=a*A
        S[seq[i]]-=a*A
    #print(i,ans,tmp,S)
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, D, A = LI()
    X_H = []
    for _ in range(N):
        x, h = LI()
        X_H.append((x, h))
    X_H = sorted(X_H, key=lambda x:x[0])
    X = [elem[0] for elem in X_H]
    kaihuku = [0 for _ in range(N)]
    cur_damage = 0
    n_attack = 0
    cnt = 0
    for i in range(N):
        x, tairyoku = X_H[i]
        cur_damage = cur_damage - kaihuku[i]
        tairyoku -= cur_damage
        tairyoku = max(tairyoku, 0)
        n_attack = tairyoku // A + (tairyoku % A > 0)

        cur_damage += n_attack * A
        ins_pos = bisect.bisect_right(X, x + 2*D)
        if ins_pos < N:
            kaihuku[ins_pos] = n_attack * A
        cnt += n_attack

    print(cnt)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque


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

m = []

for i in range(n) :
    m.append(list(map(int, input().split())))

m.sort()

#print(n, d, a)
#print(m)

tot = 0
d = 2*d
q = deque()
ans = 0

'''

def aprint() :
    global damage
    global tot
    global ans
    global q

    print("")

    print("damage", damage)
    print("tot", tot)
    print("ans", ans)
    print("q", q)

    print("")
'''



for i in range(n) :

    #print("i",i)

    x = m[i][0]
    h = m[i][1]

    while len(q) > 0 and q[-1][0] < x :
        tot -= q.pop()[1]

    h -= tot

    if h <= 0 :
        #aprint()
        continue

    c = (h+a-1)//a
    damage = c*a
    tot += damage
    q.append([x+d, damage])
    ans += c
    #aprint()

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from math import ceil

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


XH = []
for i in range(N):
    x, h = list(map(int, input().split()))
    XH.append((x, h))

XH.sort()
Xs = [x for (x,h) in XH]

D2 = D * 2
X_D2 = {}
for x,h in XH:
    idx = bisect.bisect_left(Xs, x + D2)
    X_D2[x] = idx

minusA = [0] * N

damage = 0
used = 0
for i, (x, h) in enumerate(XH):
    damage += minusA[i]
    h -= damage
    if h > 0:
        bomb = ceil(h / A)
        # print("Bomb at " + str(x) + ", count = " + str(bomb))
        damage += bomb * A
        if X_D2[x] < len(Xs):
            minusA[X_D2[x]] = -bomb * A
        used += bomb

# print(X_D2)
print(used)

Submission status: Wrong Answer

Solution code:
import bisect
from math import ceil

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


XH = []
Xs = []
for i in range(N):
    x, h = list(map(int, input().split()))
    XH.append((x, h))
    Xs.append(x)

XH.sort()
Xs.sort()

D2 = D * 2
X_D2 = {}
for x,h in XH:
    idx = bisect.bisect_right(Xs, x + D2)
    X_D2[x] = idx

minusA = [0] * N

damage = 0
used = 0
for i, (x, h) in enumerate(XH):
    damage += minusA[i]
    h -= damage
    if h > 0:
        bomb = ceil(h / A)
        # print("Bomb at " + str(x) + ", count = " + str(bomb))
        damage += bomb * A
        if X_D2[x] < len(Xs):
            minusA[X_D2[x]] = -bomb * A
        used += bomb

# print(X_D2)
print(used)

Submission status: Wrong Answer

Solution code:
import math

def unzip(li):
    return map(list, zip(*li))

N, D, A = (int(i) for i in input().split())
XH = [0]*N
for i in range(N):
    XH[i] = list(int(j) for j in input().split())
XH.sort()

X, H = unzip(XH)

BOMB = [0]*N
for i in range(N):
    boundary = X[i]+2*D
    for k in range(i, N):
        if X[k]> boundary:
            k = k-1
            break
    BOMB[i] = k
    
count = 0
for i in range(N):
    local_count = int(math.ceil(H[i]/A))
    count+=local_count
    for j in range(i, BOMB[i]+1):
        H[j] -= local_count*A
            
print(count)

Submission status: Wrong Answer

Solution code:
import math

N, D, A = (int(i) for i in input().split())
XH = [0]*N
for i in range(N):
    XH[i] = list(int(j) for j in input().split())
XH.sort()

BOMB = [0]*N
for i in range(N):
    for k in range(i, N):
        if XH[k][0]>XH[i][0]+2*D:
            k = k-1
            break
    BOMB[i] = k
    
count = 0
for i in range(N):
    local_count = int(math.ceil(XH[i][1]/A))
    count+=local_count
    for j in range(i, BOMB[i]+1):
        XH[j][1] -= local_count*A
            
print(count)

Submission status: Wrong Answer

Solution code:
import math

N, D, A = (int(i) for i in input().split())
XH = [0]*N
for i in range(N):
    XH[i] = list(int(j) for j in input().split())
XH.sort()

BOMB = [0]*N
for i in range(N):
    for k in range(i, N):
        if XH[k][0]>XH[i][0]+2*D:
            k = k-1
            break
    BOMB[i] = k
    
count = 0
for i in range(N):
    local_count = int(math.ceil(XH[i][1]/A))
    count+=local_count
    for j in range(i, BOMB[i]+1):
        XH[j][1] -= local_count
            
print(count)

Submission status: Wrong Answer

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

D = True

pos = []

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

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

bombs = 0

for i, (x, h) in enumerate(pos):
	if h <= 0:
		continue
	new_x = x + 2*d
	number = (h-1) // a + 1
	bombs += number
	destroy = number*a
	for j, (x1, h1) in enumerate(pos[i:]):
		if x1 > new_x:
			break
		pos[j] = (x1, max(0, h1-destroy))

print(bombs)

Submission status: Wrong Answer

Solution code:
import heapq
from bisect import bisect_left
from bisect import bisect_right

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

ps = []
xs = []


def ceil(a,b):
    return -(-a//b)

for i in range(N):
    x,h = map(int, input().split())
    ps.append([x,h])
    xs.append(x)

xs.sort()
ps.sort()

q = []
heapq.heappush(q,ps[0])
cnt = 0
while q:
    # 左端から出していく
    x, h = heapq.heappop(q)
    # 自分を左端として、2Dまでダメージあ与えられる
    r = x + 2*D
    damage = A*ceil(h,A)
    cnt += damage//A
    l_ind = bisect_left(xs, x)
    r_ind = bisect_left(xs, r)
    # print("l",l_ind,"r",r_ind,"damage",damage)
    # 範囲内に他のモンスターが見当たらない
    if r_ind == l_ind:
        if r_ind == N-1:
            break
        else:
            q.append(ps[r_ind+1])
        # print("aaa",ps[r_ind+1])
        continue
    for i in range(l_ind,r_ind):
        x_new,h_new = ps[i]
        ps[i][1] = h_new - damage
        if ps[i][1] > 0:
            heapq.heappush(q,ps[i])
    # print(x,h,damage)
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10**6)

n, d, a = list(map(int, input().split()))
xa = [[0, 0] for _ in range(n)]
for i in range(n):
    xa[i][0], xa[i][1] = list(map(int, input().split()))

xa.sort()
ans = 0
i = 0
while i < n:
    dmg = math.ceil(xa[i][1]/a)*a
    x = xa[i][0]
    ans += math.ceil(xa[i][1]/a)
    next = None
    for j in range(i, n):
        if xa[j][0] > x+2*d:
            break
        xa[j][1] -= dmg
        if next == None and xa[j][1] > 0:
            next = j
    if next != None:
        i = next
    elif xa[i][1] <= 0:
        i += 1
print(ans)