Problem p02852 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

def dijkstra_path(s, edges):
    dist = [INF for i in range(len(edges))]
    dist[s], h, p = 0, [], [-1]*len(edges)
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            tmp = dv+cost
            if tmp < dist[u]:
                dist[u] = tmp
                p[u] = v
                heappush(h, (tmp, u))
    return dist, p

N, M = map(int, input().split())
S = input()
ids = []
for i, x in enumerate(S):
    if x == '0':
        ids.append(-i)
ids = ids[::-1]
l = len(ids)
es = [[] for i in range(N+1)]
for i in range(N, 0, -1):
    es[i].append((-ids[min(l-1, bisect_right(ids, -i+M)-1)], 1))
d, p = dijkstra_path(N, es)
if d[0] == INF:
    print(-1)
    exit()
vs = []
v = 0
while v != -1:
    vs.append(v)
    v = p[v]
ans = [vs[i+1]-vs[i] for i in range(len(vs)-1)]
print(*ans, sep = ' ')

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# Range Minimum query
class SegmentTree:

    def __init__(self, N, INF = INF):
        self.N = 1
        while self.N < N:
            self.N <<= 1
        self.data = [INF for i in range((self.N<<1)-1)]

    def update(self, k, a):
        k += self.N-1
        self.data[k] = a
        while k > 0:
            k = (k-1)>>1
            self.data[k] = min(self.data[(k<<1)+1], self.data[(k<<1)+2])

    def RmQ(self, a, b, k=0, l=0, r=-1):
        if r == -1: r = self.N
        if r <= a or b <= l:
            return INF
        if a <= l and r <= b:
            return self.data[k]
        vl = self.RmQ(a, b, (k<<1)+1, l, (l+r)>>1)
        vr = self.RmQ(a, b, (k<<1)+2, (l+r)>>1, r)
        return min(vl, vr)

N, M = map(int, input().split())
S = input()
dp = SegmentTree(N+1)
dp.update(0, 0)
for i in range(1, N+1):
    if S[i] == '0':
        c = dp.RmQ(max(0, i-M), i)
        if c != INF:
            dp.update(i, c+1)
G = dp.RmQ(N, N+1)
if G == INF:
    print(-1)
    exit()
minv = [INF] * N
for i in range(N)[::-1]:
    if S[i] == '0':
        x = dp.RmQ(i, i+1)
        minv[x] = i
minv[G] = N
x = 0
vs = []
while x <= G:
    vs.append(minv[x])
    x += 1
vs = vs[::-1]
ans = [vs[i]-vs[i+1] for i in range(len(vs)-1)]
print(*ans[::-1], sep = ' ')

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# Range Minimum query
class SegmentTree:

    def __init__(self, N, INF = INF):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.data = [INF for i in range(self.N*2-1)]

    def update(self, k, a):
        k += self.N-1
        self.data[k] = a
        while k > 0:
            k = (k-1)//2
            self.data[k] = min(self.data[k*2+1], self.data[k*2+2])

    def RmQ(self, a, b, k=0, l=0, r=-1):
        if r == -1: r = self.N
        if r <= a or b <= l:
            return INF
        if a <= l and r <= b:
            return self.data[k]
        vl = self.RmQ(a, b, k*2+1, l, (l+r)>>1)
        vr = self.RmQ(a, b, k*2+2, (l+r)>>1, r)
        return min(vl, vr)

N, M = map(int, input().split())
S = input()
dp = SegmentTree(N+1)
dp.update(0, 0)
for i in range(1, N+1):
    if S[i] == '0':
        c = dp.RmQ(max(0, i-M), i)
        if c != INF:
            dp.update(i, c+1)
G = dp.RmQ(N, N+1)
if G == INF:
    print(-1)
    exit()
minv = [INF] * N
for i in range(N)[::-1]:
    if S[i] == '0':
        x = dp.RmQ(i, i+1)
        minv[x] = i
minv[G] = N
x = 0
vs = []
while x <= G:
    vs.append(minv[x])
    x += 1
vs = vs[::-1]
ans = [vs[i]-vs[i+1] for i in range(len(vs)-1)]
print(*ans[::-1], sep = ' ')