Problem p02852 (python)

Fixed submission:
# https://atcoder.jp/contests/abc146/submissions/8617148

def solve(N, M, S):
    from collections import namedtuple
    from heapq import heappop, heappush

    INF = N * 2
    V = namedtuple('V', 'cnt index')

    cnt_from_N = [INF] * (N + 1)
    cnt_from_N[N] = 0

    parent = [0] * (N + 1)

    h = [V(cnt=0, index=N)]

    for j in range(N - 1, -1, -1):
        # S[j]に到達する最小回数とその経路を求める
        if S[j]:
            continue

        while h:
            cnt, par = h[0]
            if par > j + M:
                # jまで移動できない(距離>M)
                heappop(h)
                continue
            break
            # jまで最小回数で到達できる頂点par
            # parまでの回数cnt

        if not h:
            return -1,
            # jまで到達できる頂点がない

        cnt_from_N[j] = cnt + 1
        parent[j] = par

        heappush(h, V(cnt=cnt + 1, index=j))

    ret = []
    curr = 0
    while curr < N:
        par = parent[curr]
        ret.append(par - curr)
        curr = par

    return ret


def main():
    N, M = map(int, input().split())
    *S, = map(int, input())
    print(*solve(N, M, S))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def solve():
    import sys

    input = sys.stdin.readline

    # seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
    class SegmentTreeClass:
        # original: @solzard_
        # https://twitter.com/solzard_/status/1180263831596982273
        def __init__(self,
                     init_val: 'initial value: iterable',
                     segfunc: 'operation unique in case',
                     ide_ele: 'identity element corresponding init_val' = 0,
                     ):
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.size = 1 << (len(init_val) - 1).bit_length()
            self.tree = self._build(init_val)

        def _build(self, init_val) -> 'tree':
            segfunc = self.segfunc

            tree = [self.ide_ele] * (self.size * 2 - 1)

            for idx, val in enumerate(init_val, self.size - 1):  # set
                # modify val if needed (e.g. str -> ord())
                tree[idx] = val

            for idx in range(self.size - 2, -1, -1):  # build
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

            return tree

        def update(self, idx: int, val) -> None:
            tree = self.tree
            segfunc = self.segfunc

            idx += self.size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        def query(self, left: int, right: int) -> 'result':
            left += self.size
            right += self.size
            ret = self.ide_ele  # left >= right: return self.ide_ele
            segfunc = self.segfunc
            tree = self.tree
            while left < right:  # どの段も奇偶...順
                if left & 1:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right & 1:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left >>= 1
                right >>= 1
            return ret

    n, m = map(int, input().split())
    s = tuple(map(int, input().rstrip()))

    inf = 10 ** 5 + 10
    dp = [inf] * (n + 1)
    dp[0] = 0
    # dp[x]:=xへの最小到達回数

    seg = SegmentTreeClass(init_val=dp, segfunc=min, ide_ele=inf)

    for j, s_ in enumerate(s[1:], 1):
        if s_:
            continue
        seg.update(j, seg.query(j - m, j) + 1)

    if seg.tree[seg.size - 1 + n] >= inf:
        print(-1)
        return

    order = []
    cf = seg.tree[seg.size - 1 + n] - 1
    cand = inf
    p = seg.size - 1 + n
    for idx in range(seg.size - 1 + n - 1, seg.size - 1 - 1, -1):
        if seg.tree[idx] == cf:
            cand = min(cand, idx)
        elif seg.tree[idx] < cf:
            order.append(p - cand)
            p = cand
            cf -= 1
    order.append(p - idx)

    order.reverse()

    print(*order)
    return


solve()

Buggy submission (verdict: Runtime Error):
def solve():
    from bisect import bisect_left
    import sys

    input = sys.stdin.readline

    # seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
    class SegmentTreeClass:
        # original: @solzard_
        # https://twitter.com/solzard_/status/1180263831596982273
        def __init__(self,
                     init_val: 'initial value: iterable',
                     segfunc: 'operation unique in case',
                     ide_ele: 'identity element corresponding init_val' = 0,
                     ):
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.size = 1 << (len(init_val) - 1).bit_length()
            self.tree = self._build(init_val)

        def _build(self, init_val) -> 'tree':
            segfunc = self.segfunc

            tree = [self.ide_ele] * (self.size * 2 - 1)

            for idx, val in enumerate(init_val, self.size - 1):  # set
                # modify val if needed (e.g. str -> ord())
                tree[idx] = val

            for idx in range(self.size - 2, -1, -1):  # build
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

            return tree

        def update(self, idx: int, val) -> None:
            tree = self.tree
            segfunc = self.segfunc

            idx += self.size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        def query(self, left: int, right: int) -> 'result':
            left += self.size
            right += self.size
            ret = self.ide_ele  # left >= right: return self.ide_ele
            segfunc = self.segfunc
            tree = self.tree
            while left < right:  # どの段も奇偶...順
                if left & 1:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right & 1:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left >>= 1
                right >>= 1
            return ret

    n, m = map(int, input().split())
    s = tuple(map(int, input().rstrip()))

    inf = 10 ** 5 + 10
    dp = [inf] * (n + 1)
    dp[0] = 0
    # dp[x]:=xへの最小到達回数

    seg = SegmentTreeClass(init_val=dp, segfunc=min, ide_ele=inf)

    for j, s_ in enumerate(s[1:], 1):
        if s_:
            continue
        seg.update(j, seg.query(j - m, j) + 1)

    if seg.tree[seg.size - 1 + n] >= inf:
        print(-1)
        return

    dp = []
    for i, x in enumerate(seg.tree[seg.size - 1:]):
        if x >= inf:
            dp.append(dp[i - 1])
        else:
            dp.append((x, i))

    order = []
    p = 0
    cf = 1
    while p < n:
        if dp[n][0] == cf:
            order.append(n - p)
            break

        idx = bisect_left(dp, (cf, p))
        order.append(dp[idx][1] - p)
        p = idx
        cf += 1

    print(*order)
    return


solve()