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
import bisect
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
x_list = [x for x, h in xh]

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    cnt = -(-h//a)
    ans += cnt
    damage[i] += cnt*a
    end_idx = bisect.bisect_right(x_list, x+2*d)
    damage[end_idx] -= cnt*a
    damage[i+1] += damage[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    while effective_bomb_idx < len(bomb_list):
        area, damage = bomb_list[effective_bomb_idx]
        if x <= area:
            h -= damage
            if h <= 0:
                break
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
li = [0] * N
li2 = [-1] *N
S = [0] * (N+1)
for i in range(N):
    u = N
    l = i
    while u - l > 1:
        m = (u+l)//2
        if X[m] - X[i] > 2*D:
            u = m
        else:
            l = m
    li[i] = l
    if li2[l] < 0:
        li2[l] = i
ans = 0
for i in range(N):
    x = X[i]
    m = max(0,-(-(d[x]-(S[i]-max(S[max(0,li2[i])], 0))*A)//A))
    ans += m
    S[i+1] = S[i] + m
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
li = [0] * N
li2 = [-1] *N
S = [0] * (N+1)
for i in range(N):
    u = N
    l = i
    while u - l > 1:
        m = (u+l)//2
        if X[m] - X[i] > 2*D:
            u = m
        else:
            l = m
    li[i] = l
    if li2[l] < 0:
        li2[l] = i
ans = 0
for i in range(N):
    x = X[i]
    m = max(0,-(-d[x]//A)-(S[i]-max(S[max(0,li2[i])], 0)))
    ans += m
    S[i+1] = S[i] + m
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, D, A = map(int, input().split())
mons = []
for _ in range(N):
    X, H = map(int, input().split())
    mons.append((X, (H + A - 1) // A))
mons.sort()

ans = 0
q = deque([])
tot = 0
for x, h in mons:
    while q:
        x0, h0 = next(iter(q))
        if x - 2 * D <= x0:
            break
        tot -= h0
        q.popleft()
    ans += max(0, h - tot)
    tot += h
    q.append((x, h))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0

for x,h in xh:
    if currentX < x:
        currentX = x+2*d+1
        currentH = h
        res += h
    else:
        if h <= currentH:
            pass
        else:
            currentX = x+2*d
            currentH = h - currentH
            res += currentH

print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
    
n,d,a = l_in()
xh = []
for _ in range(n):
    x,h=l_in()
    xh.append((x,math.ceil(h/a)))

xh.sort()
res = 0
currentX = -1
currentH = 0

for x,h in xh:
    if currentX < x:
        currentX = x+2*d+1
        currentH = h
        res += h
    else:
        if h <= currentH:
            pass
        else:
            currentX = x+2*d+1
            currentH = h - currentH
            res += currentH

print(res)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil
from bisect import bisect_right

n, d, a = map(int, readline().split())
xh = [list(map(int, readline().split())) for i in range(n)]
xh.sort()
imos = [0] * (n + 1)
cnt = 0
ans = 0
x = []
for i in range(n):
    xh[i][1] = ceil(xh[i][1] / a)
    x.append(xh[i][0])
for i in range(n):
    cnt += imos[i]
    n_h = xh[i][1] - cnt
    if n_h > 0:
        cnt += ceil(n_h / a)
        ans += ceil(n_h / a)
        imos[bisect_right(x, x[i] + 2 * d)] -= ceil(n_h / a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import ceil
from bisect import bisect_right

n, d, a = map(int, readline().split())
xh = [list(map(int, readline().split())) for i in range(n)]
xh.sort()
imos = [0] * (n + 1)
cnt = 0
ans = 0
x = []
for i in range(n):
    xh[i][1] = ceil(xh[i][1] / a)
    x.append(xh[i][0])
for i in range(n):
    cnt += imos[i]
    n_h = xh[i][1] - cnt * a
    if n_h > 0:
        cnt += ceil(n_h / a)
        ans += ceil(n_h / a)
        imos[bisect_right(x, x[i] + 2 * d)] -= ceil(n_h / a)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt
		S[i+1] += tmp
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]

cnt = 0
for i in range(N):
	if H[i] > 0:
		atack = -(-H[i]//A)
		cnt += atack
		s = X[i]
		f = X[i]+L
		H[s:f+1] -= atack*A

print(cnt)

Submission status: Wrong Answer

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

size = 1
while size <= n + 1:
    size *= 2

segment_tree = [0] * (2 * size - 1)
lazy = [False] * (2 * size - 1)


def lazy_add_query(k, x, segment_tree, lazy):
    if 0 <= k < size - 1:
        lazy_item = segment_tree[k]
        segment_tree[k] = 0 #初期化
        lazy[k] = False
        segment_tree[k * 2 + 1] += lazy_item
        lazy[k * 2 + 1] = True
        segment_tree[k * 2 + 2] += lazy_item
        lazy[k * 2 + 2] = True


def add_query(s, t, k, l, r, x, segment_tree, lazy):
    if lazy[k]:
        lazy_add_query(k, x, segment_tree, lazy)
    if r <= s or t <= l:
        return
    if s <= l and r <= t:
        segment_tree[k] += x
        lazy[k] = True
    else:
        add_query(s, t, k * 2 + 1, l, (l + r) // 2, x, segment_tree, lazy)
        add_query(s, t, k * 2 + 2, (l + r) // 2, r, x, segment_tree, lazy)

def get_query(i, segment_tree, lazy):
    i += size - 1
    ans = segment_tree[i]
    while i > 0:
        i = (i - 1) // 2
        if lazy[i]:
            ans += segment_tree[i]
    return ans

monster = []
for _ in range(n):
    x, h = map(int, input().split())
    monster.append((x, h))
monster.append((monster[-1][0], 0))
monster.sort(key=lambda x: x[0])

# init
for i in range(len(monster)):
    _, h = monster[i]
    add_query(i, i + 1, 0, 0, size, h, segment_tree, lazy)

ans = 0
D = 2 * d
left = 0
for i in range(len(monster)):
    x, h = monster[i]
    if left <= x <= left + D:
        continue
    else:
        hp = get_query(left, segment_tree, lazy)
        if hp > 0:
            if hp % a == 0:
                t = hp // a
            else:
                t = hp // a + 1
            ans += t
            damage = a * hp
            add_query(left, i, 0, 0, size, -1 * damage, segment_tree, lazy)
        left = i
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import bisect
from collections import deque
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, math.ceil(h/A)))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 # 有効なダメージ合計
for i in range(N):
    x, h = data[i]

    # 爆破範囲が届いていなければ削除していく
    while damage_que and damage_que[0][0] < x:
        x, a = damage_que.popleft()
        attack -= a
    
    # 有効な過去の爆破攻撃を受ける
    remain = max(h - attack, 0)

    # 0になるまで爆破    
    attack += remain
    c += remain
    

    # 爆破回数追加    
    damage_que.append([x+2*D, remain])

print(c)

Submission status: Wrong Answer

Solution code:
import math
import bisect
from collections import deque
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 # 有効なダメージ合計
for i in range(N):
    x, h = data[i]

    # 爆破範囲が届いていなければ削除していく
    while damage_que and damage_que[0][0] < x:
        x, a = damage_que.popleft()
        attack -= a
    
    # 有効な過去の爆破攻撃を受ける
    remain = h - attack
    if remain > 0:
        # 0になるまで爆破
        a = math.ceil(remain/A)
        attack += a * A
        c += a
    else:
        a = 0        

    # 爆破回数追加    
    damage_que.append([x+2*D, attack])

print(c)

Submission status: Wrong Answer

Solution code:
import math
import bisect
from collections import deque
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
damage_que = deque()
attack = 0 # 有効なダメージ合計
for i in range(N):
    x, h = data[i]

    # 爆破範囲が届いていなければ削除していく
    while damage_que and damage_que[0][0] < x:
        x, a = damage_que.popleft()
        attack -= a
    
    # 有効な過去の爆破攻撃を受ける
    remain = h - attack

    # 0になるまで爆破
    a = math.ceil(remain/A)

    # 爆破回数追加
    c += a
    attack += a * A
    damage_que.append([x+2*D, attack])

print(c)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
for i in range(N):
    x, h = data[i]
    if h <= 0:
        continue

    # 爆破回数
    attack = math.floor(h / A)
    c += attack

    # 爆破場所
    # x + D
    for j in range(i+1, N):
        _x, _h = data[j]        
        if _x <= x + D + D:
            _h -= A * attack
            data[j] = (_x, _h)
        else:
            break

print(c)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
for i in range(N):
    x, h = data[i]
    if h <= 0:
        continue

    # 爆破回数
    attack = math.floor(h / A)
    c += attack

    # 爆破場所
    # x + D
    for j in range(i, N):
        _x, _h = data[j]        
        if _x <= x + D + D:
            _h -= A * attack
            data[j] = (_x, _h)
        else:
            break

print(c)

Submission status: Wrong Answer

Solution code:
import math
N, D, A = list(map(int, input().split()))
data = []
for _ in range(N):
    x, h = list(map(int, input().split()))
    data.append((x, h))
data = sorted(data, key=lambda x: x[0])

c = 0
for i in range(N):
    x, h = data[i]
    if h <= 0:
        continue

    # 爆破回数
    attack = math.floor(h / A)
    c += attack

    # 爆破場所
    # x + D
    for j in range(i, N):
        _x, _h = data[j]
        if _x <= x + D + D:
            _h -= A * attack
            data[j] = (_x, _h)

print(c)

Submission status: Wrong Answer

Solution code:
from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])

POS = [v[0] for v in L]
ES = [0]*(N+1)
ans, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > A*c:
        t = L[i][1]-A*c
        ans += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
POS = [v[0] for v in L]
ES = [0]*(N+1)
a, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > A*c:
        t = L[i][1]
        a += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(a)

Submission status: Wrong Answer

Solution code:
from math import ceil
import bisect

# ref http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3986599#1


class Lazy_SegTree:
    """
    Lazy Segment Tree
        * handle range update
    """

    def __init__(self, n, func, init=float('inf')):
        """__init__
        :param
            n: size of node
            func: merge func
            init: initial value of each nde
        """
        self._n = n
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.lazy = [None]*(2*self.n)
        self.func = func

    def set(self, pos, val):
        """set

        :param pos: position of value
        :param val: set value
        """
        self.data[pos+self.n-1] = val

    def build(self):
        """build
            called after set, build initial seg tree
        """
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def _update_range(self, l, r):
        """_update_range
            get range of updated nodes

        :param l:
        :param r:
        """
        L = l+self.n
        R = r+self.n

        lm = (L//(L & -L)) >> 1
        rm = (R//(R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def _propagates(self, *ids):
        """_propagates
            propagete lazy-value

        :param *ids:
        """
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = \
                self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """update
            update values [l,r) with x
        :param l: left index
        :param r: right index
        :param x: value
        """
        *ids, = self._update_range(l, r)
        self._propagates(*ids)
        L = l+self.n
        R = r + self.n
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """query
            return value [l,r)
        :param l: left index
        :param r: right index
        """
        self._propagates(*self._update_range(l, r))
        L = l + self.n
        R = r + self.n
        ret = self.init

        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

    def print_tree(self):
        print(" ".join(map(str, [self.data[i+self.n-1]
                                 for i in range(self._n)])))


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
cnt = 0

Seg = Lazy_SegTree(N, lambda x, y: x+y, init=0)
Seg.build()

for i in range(N):
    already = Seg.query(i, i+1)
    left_pos, hp = L[i]
    if hp-already <= 0:
        continue

    cnt += (hp-already)
    right_ind = bisect.bisect_right([v[0] for v in L], left_pos+2*D)
    Seg.update(i, right_ind, hp-already)
print(cnt)

Submission status: Wrong Answer

Solution code:
from math import ceil
import bisect


class Lazy_SegTree:
    """
    Lazy Segment Tree
        * handle range update
    """

    def __init__(self, n, func, init=float('inf')):
        """__init__

        :param
            n: size of node
            func: merge func
            init: initial value of each nde
        """
        self._n = n
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.lazy = [None]*(2*self.n)
        self.func = func

    def set(self, pos, val):
        """set

        :param pos: position of value
        :param val: set value
        """
        self.data[pos+self.n-1] = val

    def build(self):
        """build
            called after set, build initial seg tree
        """
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def _update_range(self, l, r):
        """_update_range
            get range of updated nodes

        :param l:
        :param r:
        """
        L = (l+self.n*2) >> 1
        R = (r+self.n*2) >> 2

        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.n):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1

    def _propagates(self, *ids):
        """_propagates
            propagete lazy-value

        :param *ids:
        """
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i -
                                         1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """update
            update values [l,r) with x
        :param l: left index
        :param r: right index
        :param x: value
        """
        * ids, = self._update_range(l, r)
        self._propagates(*ids)
        L = l+self.n
        R = r + self.n
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """query
            return value [l,r)
        :param l: left index
        :param r: right index
        """
        L = l + self.n
        R = r + self.n
        ret = self.init

        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

    def print_tree(self):
        print(" ".join(map(str, [self.data[i+self.n-1]
                                 for i in range(self._n)])))


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
cnt = 0

Seg = Lazy_SegTree(N, lambda x, y: x+y, init=0)
Seg.build()

for i in range(N):
    already = Seg.query(i, i+1)
    left_pos, hp = L[i]
    if hp-already <= 0:
        continue

    cnt += (hp-already)
    right_ind = bisect.bisect_right([v[0] for v in L], left_pos+2*D)
    Seg.update(i, right_ind, hp-already)
print(cnt)

Submission status: Wrong Answer

Solution code:
from math import ceil
import bisect


class Lazy_SegTree:
    """
    Lazy Segment Tree
        * handle range update
    """

    def __init__(self, n, func, init=float('inf')):
        """__init__

        :param
            n: size of node
            func: merge func
            init: initial value of each nde
        """
        self._n = n
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, pos, val):
        """set

        :param pos: position of value
        :param val: set value
        """
        self.data[pos+self.n-1] = val

    def build(self):
        """build
            called after set, build initial seg tree
        """
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, l, r, x):
        """update
            update values [l,r) with x
        :param l: left index
        :param r: right index
        :param x: value
        """
        if r <= l:
            return self.init

        l += self.n-1
        r += self.n-2
        while r-l > 1:
            if l & 1 == 0:
                self.data[l] = self.func(self.data[l], x)
            if r & 1 == 0:
                self.data[r] = self.func(self.data[r], x)
                r -= 1
            l //= 2
            r = (r-1)//2

        if r == l:
            self.data[r] = self.func(self.data[r], x)
        else:
            self.data[l] = self.func(self.data[l], x)
            self.data[r] = self.func(self.data[r], x)

    def query(self, l, r):
        """query
            return value [l,r)
        :param l: left index
        :param r: right index
        """
        L = l + self.n
        R = r + self.n
        ret = self.init

        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

    def print_tree(self):
        print(" ".join(map(str, [self.data[i+self.n-1]
                                 for i in range(self._n)])))


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
cnt = 0

Seg = Lazy_SegTree(N, lambda x, y: x+y, init=0)
Seg.build()

for i in range(N):
    already = Seg.query(i, i+1)
    left_pos, hp = L[i]
    if hp-already <= 0:
        continue

    cnt += (hp-already)
    right_ind = bisect.bisect_right([v[0] for v in L], left_pos+2*D)
    Seg.update(i, right_ind, hp-already)
print(cnt)

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

x=[m[i][0] for i in range(N)]
h=[m[i][1] for i in range(N)]

def main():
  c,l=0,0
  while l<N:
    p=(h[l]+A-1)//A
    h[l],n,r,c=0,0,l+1,c+p
    while r<N and x[l]+2*D>x[r]:
      if h[r]>A*p:
        h[r]-=A*p
        if n==0:
          n=r
      elif h[r]!=0:
        h[r]=0
      r+=1
    else:
      l=n if n!=0 else r

  print(c)

main()

Submission status: Wrong Answer

Solution code:
def main():
  N,D,A=map(int,input().split())
  m=sorted([[int(j) for j in input().split()] for i in range(N)],reverse=True)

  c=0
  while len(m)>0:
    rx,rh=m.pop()
    e=list()
    a=(rh+A-1)//A
    c+=a
    while len(m)>0:
      x,h=m.pop()
      if x<=rx+2*D:
        if h>a*A:
          e.append([x,h-a*A])
      else:
        m.append([x,h])
        while len(e)>0:
          x,h=e.pop()
          m.append([x,h])
        break
  print(c)

main()

Submission status: Wrong Answer

Solution code:
def main():
  N,D,A=map(int,input().split())
  m=sorted([[int(j) for j in input().split()] for i in range(N)],reverse=True)

  c=0
  while len(m)>0:
    rx,rh=m.pop()
    e=list()
    a=(rh+A-1)//A
    c+=a
    while len(m)>0:
      x,h=m.pop()
      if x<=rx+2*D:
        if h>a*D:
          e.append([x,h-a*D])
      else:
        m.append([x,h])
        while len(e)>0:
          x,h=e.pop()
          m.append([x,h])
        break
  print(c)

main()

Submission status: Wrong Answer

Solution code:
def main():
  N,D,A=map(int,input().split())
  m=sorted([[int(j) for j in input().split()] for i in range(N)],reverse=True)

  c=0
  while len(m)>0:
    rx,rh=m.pop()
    e=list()
    a=(rh+A-1)//A
    c+=a
    while len(m)>0:
      x,h=m.pop()
      if x<=rx+2*D:
        if h>a*D:
          e.append([x,h-a*D])
      else:
        m.append([x,h])
        while len(e)>0:
          x,h=e.pop()
          m.append([x,h])
        break
    else:
      print(c)
      break

main()

Submission status: Wrong Answer

Solution code:
N,D,A=map(int,input().split())
m=sorted([int(j) for j in input().split()] for i in range(N))

def main():
  c,l,r=0,0,1
  while l<N:
    p=(m[l][1]+A-1)//A
    m[l][1],l,r,c=0,0,l+1,c+p
    while r<N and m[l][0]+2*D>=m[r][0]:
      if m[r][1]==0:
        pass
      elif m[r][1]>A*p:
        m[r][1]-=A*p
        l=r
      else:
        m[r][1]=0
      r+=1
    else:
      if l==0:
        l=r
  print(c)

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    left = M[0]
    result = 0
    attackCount = math.ceil(M[0][1]/A)
    damage = attackCount*A
    next = 0
    while next <= N-1:
        hasNonZero = False
        breaken = False
        left = M[next]
        attackCount = math.ceil(left[1]/A)
        damage = attackCount*A
        result += attackCount
        for i in range(next, N):
            if M[i][0] <= left[0]+DD:
                M[i] = (M[i][0], max(0, M[i][1]-damage))
                if not hasNonZero and M[i][1] != 0:
                    hasNonZero = True
                    next = i
            else:
                if not hasNonZero:
                    next = i
                breaken = True
                break
        if not breaken:
            next = N
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import bisect

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

log = []
loc = []
ene = []

for _ in range(N):
    X, H = map(int, input().split())
    log.append([X, H])

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

for X, H in log:
    loc.append(X)
    ene.append(H)

syokan = [0] * N

power = 0
for i in range(N):
    temp = max(((ene[i] - power) // A), 0) * A
    power += temp

    rng = bisect.bisect_right(loc, loc[i] + 2 * D)
    syokan[min(rng - 1, N - 1)] += temp

    power -= syokan[i]
    # print(syokan)
# print(syokan)
print(sum(syokan) // A)

Submission status: Wrong Answer

Solution code:
import numpy as np

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


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

lis.sort()
for x,h in lis:
    xs.append(x)
    hs.append(h)

xs = np.array(xs)
hs = np.array(hs)
ans = 0

for i in range(len(hs)):
    idx = np.searchsorted(xs, xs[i]+2*d)
    sub = hs[i] // a if hs[i] % a == 0 else (hs[i] // a) + 1
    hs[i:idx+1] = np.maximum(0, hs[i:idx+1]-(a * sub))

    ans += sub
    if hs[len(hs)-1] == 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
n,d,a = map(int,input().split())
lis = []
for i in range(n):
    x, h = map(int, input().split())
    lis.append([x, h])
xs = []
hs = []

lis.sort()
for x,h in lis:
    xs.append(x)
    hs.append(h)
xs = np.array(xs)
hs = np.array(hs)

ans = 0
for i in range(len(hs)):
    idx = min(np.searchsorted(xs, xs[i]+2*d), len(hs)-1)
    sub = hs[i] // a if hs[i] % a == 0 else hs[i] // a + 1

    hs[i:idx+1] = np.maximum(0, hs[i:idx+1]-(a * sub))

    ans += sub

print(ans)