Problem p02680 (python)

Fixed submission:
#!/usr/bin/env python3

from heapq import heappush, heappop
import sys
import numpy as np

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 9 + 1
# INF = float("inf")


def dp(*x):  # debugprint
    print(*x)


try:
    profile
except:
    def profile(f): return f


@profile
def main(N, M, data):
    ABC = data[:3 * N]
    DEF = data[3 * N:]
    A, B, C = [ABC[i::3] for i in range(3)]
    D, E, F = [DEF[i::3] for i in range(3)]

    xticks = np.unique(np.concatenate((E, F, C, np.array([-INF, 0, INF]))))
    yticks = np.unique(np.concatenate((A, B, D, np.array([-INF, 0, INF]))))
    width = xticks[1:] - xticks[:-1]
    height = yticks[1:] - yticks[:-1]

    # compress
    A = np.searchsorted(yticks, A).astype(np.int16)
    B = np.searchsorted(yticks, B).astype(np.int16)
    C = np.searchsorted(xticks, C).astype(np.int16)
    D = np.searchsorted(yticks, D).astype(np.int16)
    E = np.searchsorted(xticks, E).astype(np.int16)
    F = np.searchsorted(xticks, F).astype(np.int16)

    GRAPH_WIDTH = len(xticks)
    GRAPH_HEIGHT = len(yticks)
    NUM_VERTEXES = GRAPH_HEIGHT * GRAPH_WIDTH

#    ng_egdes = np.zeros((NUM_VERTEXES, 4), dtype=np.uint8)
    if 0:
        direction = (-1, +1, -GRAPH_WIDTH, +GRAPH_WIDTH)

        ng_edges = np.zeros(NUM_VERTEXES, dtype=np.uint8)

        # dp(": NUM_VERTEX", NUM_VERTEXES)
        # dp(": N,M", N, M)
        # vertical lines A,C-B,C
        for i in range(N):
            x = C[i]
            for y in range(A[i], B[i]):
                pos = y * GRAPH_WIDTH + x
                # ng_egdes[pos, 0] = 1  # left
                # ng_egdes[pos - 1, 1] = 1  # right
                ng_edges[pos] |= 0b0001  # left
                ng_edges[pos - 1] |= 0b0010  # right
        A = B = C = 0

        # horizontal lines D,E-D,F
        for i in range(M):
            y = D[i]
            for x in range(E[i], F[i]):
                pos = y * GRAPH_WIDTH + x
                ng_edges[pos] |= 0b0100
                ng_edges[pos - GRAPH_WIDTH] |= 0b1000
        D = E = F = 0
    else:
        direction = (1, -1, GRAPH_WIDTH, -GRAPH_WIDTH)

        def set_ng(A, B, C, D, E, F, H, W):
            ng = np.zeros((H * W, 4), np.bool_)

            for i in range(len(A)):
                for x in range(A[i], B[i]):
                    v = x * W + C[i]
                    ng[v][1] = 1
                    ng[v - 1][0] = 1

            for i in range(len(D)):
                for y in range(E[i], F[i]):
                    v = D[i] * W + y
                    ng[v][3] = 1
                    ng[v - W][2] = 1
            return ng

        ng_edges = set_ng(A, B, C, D, E, F, GRAPH_HEIGHT, GRAPH_WIDTH)
    total_area = 0
    visited = np.zeros(NUM_VERTEXES)
    #visited = set()

    x = np.searchsorted(xticks, 0)
    y = np.searchsorted(yticks, 0)
    start = y * GRAPH_WIDTH + x
    to_visit = [start]

    stack = np.empty(NUM_VERTEXES, np.int32)
    p = 0

    def push(x):
        nonlocal p
        stack[p] = x
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return stack[p]

    push(start)
    MASK = np.array([0b0001, 0b0010, 0b0100, 0b1000], dtype=np.uint8)
    # while to_visit:
    while p:
        #pos = to_visit.pop()
        pos = pop()
        y, x = divmod(pos, GRAPH_WIDTH)
        if visited[pos]:
            continue
        if y == 0 or y == GRAPH_HEIGHT - 1 or x == 0 or x == GRAPH_WIDTH - 1:
            print("INF")
            break

        total_area += width[x] * height[y]
        # visited.add(pos)
        visited[pos] = 1
        # plan to visit neighbors
        for i in range(4):
            # if not (ng_edges[pos] & MASK[i]):
            if not ng_edges[pos][i]:
                next = pos + direction[i]
                if visited[next]:
                    continue
                # to_visit.append(next)
                push(next)
    else:
        print(total_area)


if sys.argv[-1] == 'ONLINE_JUDGE' or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export(
        'main',
        "void(i4, i4, i4[:])"
    )(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    if sys.argv[-1] != '-p':
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import main  # pylint: disable=all

    # read parameter
    import numba
    N, M = map(int, input().split())
    data = np.int32(sys.stdin.read().split())
    main(N, M, data)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import numba

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")


def dp(*x):  # debugprint
    print(*x)


try:
    profile
except:
    def profile(f): return f


@numba.jit
def bisect_left(a, x):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if x < a[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo


def main(vticks, hticks, vlines, hlines):

    total_area = 0
    visited = set()

    maxH = len(hticks) - 2
    maxV = len(vticks) - 2
    # dp(": maxH, maxV", maxH, maxV)
    i = bisect_left(hticks, 0)
    j = bisect_left(vticks, 0)
    to_visit = [(i, j)]

    while to_visit:
        i, j = to_visit.pop()
        # dp(": (i,j)", (i, j))
        if i == 0 or i == maxH or j == 0 or j == maxV:
            print("INF")
            break

        if (i, j) in visited:
            continue

        # dp("visit: (i,j)", (i, j))
        x = hticks[i]
        y = vticks[j]
        width = hticks[i + 1] - hticks[i]
        height = vticks[j + 1] - vticks[j]
        total_area += width * height
        visited.add((i, j))
        # visit neighbors
        l = i - 1
        if (l, j) not in visited:
            for a, b in vlines[x]:
                if a <= y < b:
                    # blocked
                    break
            else:
                # can move left
                to_visit.append((l, j))

        u = j - 1
        if (i, u) not in visited:
            for a, b in hlines[y]:
                if a <= x < b:
                    # blocked
                    break
            else:
                # can move up
                to_visit.append((i, u))

        r = i + 1
        if (r, j) not in visited:
            for a, b in vlines[hticks[r]]:
                if a <= y < b:
                    # blocked
                    break
            else:
                # can move left
                to_visit.append((r, j))

        d = j + 1
        if (i, d) not in visited:
            for a, b in hlines[vticks[d]]:
                if a <= x < b:
                    # blocked
                    break
            else:
                # can move up
                to_visit.append((i, d))

        # dp(": to_visit", to_visit)
    else:
        print(total_area)


if sys.argv[-1] == 'ONLINE_JUDGE' or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export(
        'main',
        "void(i8[:], i8[:], "
        "DictType(int64,ListType(UniTuple(int64,2))),"
        "DictType(int64,ListType(UniTuple(int64,2))))")(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    if sys.argv[-1] != '-p':
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import main

    # read parameter
    import numba
    N, M = map(int, input().split())

    vlines = defaultdict(lambda: [(0, 0)])
    hlines = defaultdict(lambda: [(0, 0)])
    vticks = {0}
    hticks = {0}

    for i in range(N):
        A, B, C = map(int, input().split())
        vlines[C].append((A, B))
        hticks.add(C)
        vticks.update((A, B))

    for i in range(M):
        D, E, F = map(int, input().split())
        hlines[D].append((E, F))
        vticks.add(D)
        hticks.update((E, F))

    vticks = [-INF] + list(sorted(vticks)) + [INF, INF]
    hticks = [-INF] + list(sorted(hticks)) + [INF, INF]

    d = numba.typed.Dict()
    for k in hticks:
        d[k] = numba.typed.List(vlines[k])
    vlines = d

    d = numba.typed.Dict()
    for k in vticks:
        d[k] = numba.typed.List(hlines[k])
    hlines = d

    main(
        np.array(vticks), np.array(hticks),
        vlines, hlines
    )

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import bisect

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")


def dp(*x):  # debugprint
    print(*x)


# f = open(sys.argv[1])
# input = f.buffer.readline

N, M = map(int, input().split())
vlines = defaultdict(list)
hlines = defaultdict(list)
vticks = {0}
hticks = {0}

for i in range(N):
    A, B, C = map(int, input().split())
    vlines[C].append((A, B))
    hticks.add(C)
    vticks.update((A, B))

for i in range(M):
    D, E, F = map(int, input().split())
    hlines[D].append((E, F))
    vticks.add(D)
    hticks.update((E, F))

vticks = [-INF] + list(sorted(vticks)) + [INF]
hticks = [-INF] + list(sorted(hticks)) + [INF]


def up(y):
    return vticks[bisect.bisect_left(vticks, y) - 1]


def down(y):
    return vticks[bisect.bisect_left(vticks, y) + 1]


def left(x):
    return hticks[bisect.bisect_left(hticks, x) - 1]


def right(x):
    return hticks[bisect.bisect_left(hticks, x) + 1]


def area(i, j):
    width = hticks[i + 1] - hticks[i]
    height = vticks[j + 1] - vticks[j]
    return width * height


total_area = 0
visited = set()


def visit(i, j):
    global total_area
    if (i, j) in visited:
        return
    # dp("visit: (i,j)", (i, j))
    x = vticks[i]
    y = hticks[j]
    a = area(i, j)
    total_area += a
    visited.add((i, j))
    # visit neighbors
    l = i - 1
    if (l, j) not in visited:
        for a, b in vlines[x]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((l, j))

    u = j - 1
    if (i, u) not in visited:
        for a, b in hlines[y]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((i, u))

    r = i + 1
    if (r, j) not in visited:
        for a, b in vlines[hticks[r]]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((r, j))

    d = j + 1
    if (i, d) not in visited:
        for a, b in hlines[vticks[d]]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((i, d))


maxH = len(hticks) - 2
maxV = len(vticks) - 2
# dp(": maxH, maxV", maxH, maxV)
i = bisect.bisect_left(hticks, 0)
j = bisect.bisect_left(vticks, 0)
to_visit = [(i, j)]

while to_visit:
    i, j = to_visit.pop()
    # dp(": (i,j)", (i, j))
    if i == 0 or i == maxH or j == 0 or j == maxV:
        print("INF")
        break
    visit(i, j)
    # dp(": to_visit", to_visit)
else:
    print(total_area)


def _test():
    import doctest
    doctest.testmod()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import bisect

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")


def dp(*x):  # debugprint
    print(*x)


f = open(sys.argv[1])
input = f.buffer.readline

N, M = map(int, input().split())
vlines = defaultdict(list)
hlines = defaultdict(list)
vticks = {0}
hticks = {0}

for i in range(N):
    A, B, C = map(int, input().split())
    vlines[C].append((A, B))
    hticks.add(C)
    vticks.update((A, B))

for i in range(M):
    D, E, F = map(int, input().split())
    hlines[D].append((E, F))
    vticks.add(D)
    hticks.update((E, F))

vticks = [-INF] + list(sorted(vticks)) + [INF, INF]
hticks = [-INF] + list(sorted(hticks)) + [INF, INF]


def up(y):
    return vticks[bisect.bisect_left(vticks, y) - 1]


def down(y):
    return vticks[bisect.bisect_left(vticks, y) + 1]


def left(x):
    return hticks[bisect.bisect_left(hticks, x) - 1]


def right(x):
    return hticks[bisect.bisect_left(hticks, x) + 1]


def area(x, y):
    i = bisect.bisect_left(hticks, x)
    width = hticks[i + 1] - hticks[i]
    j = bisect.bisect_left(vticks, y)
    height = vticks[j + 1] - vticks[j]
    return width * height


total_area = 0
visited = set()


def visit(x, y):
    global total_area
    if (x, y) in visited:
        return
    # dp("visited: x,y", x, y)
    a = area(x, y)
    total_area += a
    visited.add((x, y))
    # visit neighbors
    l = left(x)
    if (l, y) not in visited:
        for a, b in vlines[x]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((l, y))

    u = up(y)
    if (x, u) not in visited:
        for a, b in hlines[y]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((x, u))

    r = right(x)
    if (r, y) not in visited:
        for a, b in vlines[r]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((r, y))

    d = down(y)
    if (x, d) not in visited:
        for a, b in hlines[d]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((x, d))


# for y in [up(0), 0]:
#     for x in [left(0), 0]:
#         visit(x, y)
# print(total_area)
to_visit = [(0, 0)]
while to_visit:
    x, y = to_visit.pop()
    if x == INF or x == -INF or y == INF or y == -INF:
        print("INF")
        break
    visit(x, y)
else:
    print(total_area)


def _test():
    import doctest
    doctest.testmod()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import bisect

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")


def dp(*x):  # debugprint
    print(*x)


f = open(sys.argv[1])
input = f.buffer.readline

N, M = map(int, input().split())
vlines = defaultdict(list)
hlines = defaultdict(list)
vticks = {0}
hticks = {0}

for i in range(N):
    A, B, C = map(int, input().split())
    vlines[C].append((A, B))
    hticks.add(C)
    vticks.update((A, B))

for i in range(M):
    D, E, F = map(int, input().split())
    hlines[D].append((E, F))
    vticks.add(D)
    hticks.update((E, F))

vticks = [-INF] + list(sorted(vticks)) + [INF]
hticks = [-INF] + list(sorted(hticks)) + [INF]


def up(y):
    return vticks[bisect.bisect_left(vticks, y) - 1]


def down(y):
    return vticks[bisect.bisect_left(vticks, y) + 1]


def left(x):
    return hticks[bisect.bisect_left(hticks, x) - 1]


def right(x):
    return hticks[bisect.bisect_left(hticks, x) + 1]


def area(x, y):
    i = bisect.bisect_left(hticks, x)
    width = hticks[i + 1] - hticks[i]
    j = bisect.bisect_left(vticks, y)
    height = vticks[j + 1] - vticks[j]
    return width * height


total_area = 0
visited = set()


def visit(x, y):
    global total_area
    if (x, y) in visited:
        return
    # dp("visited: x,y", x, y)
    a = area(x, y)
    total_area += a
    visited.add((x, y))
    # visit neighbors
    l = left(x)
    if (l, y) not in visited:
        for a, b in vlines[x]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((l, y))

    u = up(y)
    if (x, u) not in visited:
        for a, b in hlines[y]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((x, u))

    r = right(x)
    if (r, y) not in visited:
        for a, b in vlines[r]:
            if a <= y < b:
                # blocked
                break
        else:
            # can move left
            to_visit.append((r, y))

    d = down(y)
    if (x, d) not in visited:
        for a, b in hlines[d]:
            if a <= x < b:
                # blocked
                break
        else:
            # can move up
            to_visit.append((x, d))


# for y in [up(0), 0]:
#     for x in [left(0), 0]:
#         visit(x, y)
# print(total_area)
to_visit = [(0, 0)]
while to_visit:
    x, y = to_visit.pop()
    if x == INF or x == -INF or y == INF or y == -INF:
        print("INF")
        break
    visit(x, y)
else:
    print(total_area)


def _test():
    import doctest
    doctest.testmod()