Problem p03033 (python)

Fixed submission:
from bisect import bisect_left
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    nxt = [i+1 for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: x[2])
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_left(D, R+1)
        p = L_idx
        while p < R_idx:
            if ans[p] == -1:
                ans[p] = X
                uf.union(L_idx, p)
                nxt[p] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = nxt[par]
                uf.union(L_idx, par)
                par = uf.find(par)
                if nxt[par] < R_idx:
                    nxt[par] = R_idx
                if nxt[par] < p:
                    nxt[par] = p
    for i in range(Q):
        print(ans[i])

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        if uf.same(L_idx, R_idx):
            continue
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
                uf.union(L_idx, p)
                ans[p][1] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = ans[par][1]
                uf.union(L_idx, par)
                par = uf.find(par)
                if ans[par][1] < R_idx:
                    ans[par][1] = R_idx
                if ans[par][1] < p:
                    ans[par][1] = p
    for i in range(Q):
        print(ans[i][0])

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        if uf.same(L_idx, R_idx):
            continue
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
                uf.union(L_idx, p)
                ans[p][1] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = ans[par][1]
                uf.union(L_idx, par)
                par = uf.find(par)
                if ans[par][1] < R_idx:
                    ans[par][1] = R_idx
                if ans[par][1] < p:
                    ans[par][1] = p
    for i in range(Q):
        print(ans[i][0])

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
            pre = p
            p = ans[p][1]
            if not uf.same(L_idx, p):
                uf.union(L_idx, p)
                if ans[L_idx][1] < ans[p][1]:
                    ans[L_idx][1] = ans[p][1]
                else:
                    ans[p][1] = ans[L_idx][1]
            if ans[pre][1] < R_idx:
                ans[pre][1] = R_idx
    for i in range(Q):
        print(ans[i][0])


if __name__ == "__main__":
    main()