Problem p02680 (python)

Fixed submission:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    def fin():
        print("INF")
        exit()

    N, M = map(int, input().split())
    X = set()
    X.add(-10**9-1)
    X.add(0)
    X.add(10**9+1)
    Y = set()
    Y.add(-10**9-1)
    Y.add(0)
    Y.add(10**9+1)
    ABC = []
    DEF = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        ABC.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        DEF.append((d, e, f))
    X = sorted(list(X))
    Y = sorted(list(Y))
    x2i = {x: i for i, x in enumerate(X)}
    y2j = {y: j for j, y in enumerate(Y)}
    LX = len(X)
    LY = len(Y)
    ABCwall = [set() for _ in range(LY)]
    for a, b, c in ABC:
        i0 = x2i[a]
        i1 = x2i[b]
        j = y2j[c]
        for i in range(i0, i1):
            ABCwall[j].add(i)
    DEFwall = [set() for _ in range(LX)]
    for d, e, f in DEF:
        i = x2i[d]
        j0 = y2j[e]
        j1 = y2j[f]
        for j in range(j0, j1):
            DEFwall[i].add(j)

    ii = x2i[0]
    jj = y2j[0]
    que = deque()
    que.append((ii, jj))
    seen = [[0] * (LY-1) for _ in range(LX-1)]
    seen[ii][jj] = 1
    ans = 0
    while que:
        i, j = que.popleft()
        ans += (X[i+1] - X[i]) * (Y[j+1] - Y[j])

        # x inc
        if j not in DEFwall[i+1]:
            if i == LX - 2:
                fin()
            if not seen[i+1][j]:
                que.append((i+1, j))
                seen[i+1][j] = 1

        # x dec
        if j not in DEFwall[i]:
            if i == 1:
                fin()
            if not seen[i-1][j]:
                que.append((i-1, j))
                seen[i-1][j] = 1

        # y inc
        if i not in ABCwall[j+1]:
            if j == LY - 2:
                fin()
            if not seen[i][j+1]:
                que.append((i, j+1))
                seen[i][j+1] = 1

        # y dec
        if i not in ABCwall[j]:
            if j == 1:
                fin()
            if not seen[i][j-1]:
                que.append((i, j-1))
                seen[i][j-1] = 1
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from bisect import bisect_left
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    AB = {}
    C = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        C.append(c)
        if c in AB:
            AB[c].append((a, b))
        else:
            AB[c] = [(a, b)]
    DE = {}
    F = []
    for _ in range(M):
        f, d, e = map(int, input().split())
        F.append(f)
        if f in DE:
            DE[f].append((d, e))
        else:
            DE[f] = [(d, e)]

    C = list(set(C))
    F = list(set(F))
    C.sort()
    F.sort()
    if C[0] >= 0 or C[-1] <= 0 or F[0] >= 0 or F[-1] <= 0:
        print("INF")
        exit()
        
    # boundary
    A = {}
    B = {}
    for c in AB:
        ab_list = AB[c]
        if len(ab_list) >= 2:
            ab_list.sort(key=lambda x: x[0])
            st = []
            for a, b in ab_list:
                if not st:
                    st.append((a, b))
                else:
                    aa, bb = st[-1]
                    if bb >= a:
                        st.pop()
                        st.append((aa, max(bb, b)))
            A[c] = [ab[0] for ab in st]
            B[c] = [ab[1] for ab in st]
        else:
            A[c] = [ab[0] for ab in ab_list]
            B[c] = [ab[1] for ab in ab_list]

    D = {}
    E = {}
    for f in DE:
        de_list = DE[f]
        if len(de_list) >= 2:
            de_list.sort(key=lambda x: x[0])
            st = []
            for d, e in de_list:
                if not st:
                    st.append((d, e))
                else:
                    dd, ee = st[-1]
                    if ee >= d:
                        st.pop()
                        st.append((dd, max(ee, e)))
            D[f] = [de[0] for de in st]
            E[f] = [de[1] for de in st]
        else:
            D[f] = [de[0] for de in de_list]
            E[f] = [de[1] for de in de_list]

    for i in range(1, len(C)):
        if C[i] >= 0:
            c0 = i-1
            break
    for j in range(1, len(F)):
        if F[j] >= 0:
            f0 = j-1
            break
    
    que = deque()
    que.append((c0, f0))
    seen = set()
    seen.add(c0 * 1001 + f0)
    ans = 0
    while que:
        i0, j0 = que.popleft()
        c0 = C[i0]
        c1 = C[i0+1]
        f0 = F[j0]
        f1 = F[j0+1]
        ans += (c1-c0) * (f1-f0)

        # right
        if i0 * (N+1) + j0+1 not in seen:
            i = bisect_left(D[f1], c0+1)
            j = bisect_left(E[f1], c1)
            if i <= j:
                que.append((i0, j0+1))
                seen.add(i0 * (N+1) + j0+1)
                if j0 == len(F):
                    print("INF")
                    exit()

        #left
        if i0 * (N+1) + j0-1 not in seen:
            i = bisect_left(D[f0], c0 + 1)
            j = bisect_left(E[f0], c1)
            if i <= j:
                que.append((i0, j0 - 1))
                seen.add(i0 * (N+1) + j0-1)
                if j0 == 0:
                    print("INF")
                    exit()

        # down
        if (i0+1) * (N+1) + j0 not in seen:
            i = bisect_left(A[c1], f0 + 1)
            j = bisect_left(B[c1], f1)
            if i <= j:
                que.append((i0+1, j0))
                seen.add((i0+1) * (N+1) + j0)
                if i0 == len(C):
                    print("INF")
                    exit()

        # up
        if (i0-1) * (N+1) + j0 not in seen:
            i = bisect_left(A[c0], f0 + 1)
            j = bisect_left(B[c0], f1)
            if i <= j:
                que.append((i0-1, j0))
                seen.add((i0-1) * (N+1) + j0)
                if i0 == 0:
                    print("INF")
                    exit()
    print(ans)
        

if __name__ == '__main__':
    main()