Problem p02680 (python)

Fixed submission:
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    wall = [[15] * W for _ in range(H)]

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            wall[i][jc - 1] &= 15 - (1 << 1)
            wall[i][jc] &= 15 - (1 << 3)
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            wall[i_d - 1][j] &= 15 - (1 << 2)
            wall[i_d][j] &= 15 - (1 << 0)

    q = deque()
    x0 = bisect_left(X, 0) - (0 not in ix)
    y0 = bisect_left(Y, 0) - (0 not in jy)
    if x0 == H - 1 or y0 == W - 1:
        print('INF')
        exit()

    path = [True] * (W * H)
    path[x0 * W + y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if wall[x][y] & (1 << i):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx * W + ny]:
                        path[nx * W + ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    wall = [[15] * W for _ in range(H)]

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            wall[i][jc - 1] &= 15 - (1 << 1)
            wall[i][jc] &= 15 - (1 << 3)
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            wall[i_d - 1][j] &= 15 - (1 << 2)
            wall[i_d][j] &= 15 - (1 << 0)

    q = deque()
    x0 = max(0, bisect_left(X, 0) - (0 not in ix))
    y0 = max(0, bisect_left(Y, 0) - (0 not in jy))
    path = [True] * (W * H)
    path[x0 * W + y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if wall[x][y] & (1 << i):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx * W + ny]:
                        path[nx * W + ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    grid = [[15] * W for _ in range(H)]

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            grid[i][jc - 1] &= 15 - (1 << 1)
            grid[i][jc] &= 15 - (1 << 3)
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            grid[i_d - 1][j] &= 15 - (1 << 2)
            grid[i_d][j] &= 15 - (1 << 0)

    q = deque()
    x0 = bisect_left(X, 0) - (0 not in ix)
    y0 = bisect_left(Y, 0) - (0 not in jy)
    path = [True] * (W * H)
    path[x0 * W + y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if grid[x][y] & (1 << i):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx * W + ny]:
                        path[nx * W + ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    grid = [[15] * W for _ in range(H)]

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            grid[i][jc - 1] &= 15 - (1 << 1)
            grid[i][jc] &= 15 - (1 << 3)
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            grid[i_d - 1][j] &= 15 - (1 << 2)
            grid[i_d][j] &= 15 - (1 << 0)

    q = deque()
    x0 = bisect_left(X, 0) - (0 not in ix)
    y0 = bisect_left(Y, 0) - (0 not in jy)
    path = [True] * (W * H)
    path[x0 * H + y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if grid[x][y] & (1 << i):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx * H + ny]:
                        path[nx * H + ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    grid = [[15] * W for _ in range(H)]

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            grid[i][jc - 1] &= 15 - (1 << 1)
            grid[i][jc] &= 15 - (1 << 3)
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            grid[i_d - 1][j] &= 15 - (1 << 2)
            grid[i_d][j] &= 15 - (1 << 0)

    q = deque()
    x0 = bisect_left(X, 0) - (0 not in ix)
    y0 = bisect_left(Y, 0) - (0 not in jy)
    path = [[True] * W for _ in range(H)]
    path[x0][y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if grid[x][y] & (1 << i):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx][ny]:
                        path[nx][ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from collections import deque
    from bisect import bisect_left

    N, M = map(int, input().split())
    tate = []
    yoko = []
    X = set()
    Y = set()
    for _ in range(N):
        A, B, C = map(int, readline().split())
        X.add(A)
        X.add(B)
        Y.add(C)
        tate.append((C, A, B))
    for _ in range(M):
        D, E, F = map(int, readline().split())
        X.add(D)
        Y.add(E)
        Y.add(F)
        yoko.append((D, E, F))

    X = sorted(list(X))
    Y = sorted(list(Y))
    H = len(X)
    W = len(Y)
    # tate.sort()
    # yoko.sort()
    grid = [[[True] * 4 for _ in range(W)] for _ in range(H)]

    ix = {}
    for i, x in enumerate(X):
        ix[x] = i
    jy = {}
    for j, y in enumerate(Y):
        jy[y] = j

    for c, a, b in tate:
        ia = ix[a]
        ib = ix[b]
        jc = jy[c]
        for i in range(ia, ib):
            if jc - 1 >= 0:
                grid[i][jc - 1][1] = 0
            grid[i][jc][3] = 0
    for d, e, f in yoko:
        i_d = ix[d]
        je = jy[e]
        jf = jy[f]
        for j in range(je, jf):
            if i_d - 1 >= 0:
                grid[i_d - 1][j][2] = 0
            grid[i_d][j][0] = 0

    q = deque()
    x0 = bisect_left(X, 0) - (0 not in ix)
    y0 = bisect_left(Y, 0) - (0 not in jy)
    path = [[True] * W for _ in range(H)]
    path[x0][y0] = False
    q.append((x0, y0))
    direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
    cnt = 0
    while q:
        x, y = q.popleft()
        cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        for i, (dx, dy) in enumerate(direction):
            if grid[x][y][i]:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                    if path[nx][ny]:
                        path[nx][ny] = False
                        q.append((nx, ny))
                else:
                    print('INF')
                    exit()
    print(cnt)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left


N, M = map(int, input().split())
tate = []
yoko = []
X = set()
Y = set()
for _ in range(N):
    A, B, C = map(int, input().split())
    X.add(A)
    X.add(B)
    Y.add(C)
    tate.append((C, A, B))
for _ in range(M):
    D, E, F = map(int, input().split())
    X.add(D)
    Y.add(E)
    Y.add(F)
    yoko.append((D, E, F))

X = sorted(list(X))
Y = sorted(list(Y))
H = len(X)
W = len(Y)
tate.sort()
yoko.sort()
grid = [[[1] * 4 for _ in range(W)] for _ in range(H)]

ix = {}
for i, x in enumerate(X):
    ix[x] = i
jy = {}
for j, y in enumerate(Y):
    jy[y] = j

for c, a, b in tate:
    ia = ix[a]
    ib = ix[b]
    jc = jy[c]
    for i in range(ia, ib):
        if jc - 1 >= 0:
            grid[i][jc - 1][1] = 0
        grid[i][jc][3] = 0
for d, e, f in yoko:
    i_d = ix[d]
    je = jy[e]
    jf = jy[f]
    for j in range(je, jf):
        if i_d - 1 >= 0:
            grid[i_d - 1][j][2] = 0
        grid[i_d][j][0] = 0

q = deque()
x0 = bisect_left(X, 0) - (0 not in ix)
y0 = bisect_left(Y, 0) - (0 not in jy)
path = [[1] * W for _ in range(H)]
path[x0][y0] = 0
q.append((x0, y0))
direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
cnt = 0
while q:
    x, y = q.popleft()
    cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
    for i, (dx, dy) in enumerate(direction):
        if grid[x][y][i]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                if path[nx][ny]:
                    path[nx][ny] = 0
                    q.append((nx, ny))
            else:
                print('INF')
                exit()
print(cnt)

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left


N, M = map(int, input().split())
tate = []
yoko = []
X = set()
Y = set()
for _ in range(N):
    A, B, C = map(int, input().split())
    X.add(A)
    X.add(B)
    Y.add(C)
    tate.append((C, A, B))
for _ in range(M):
    D, E, F = map(int, input().split())
    X.add(D)
    Y.add(E)
    Y.add(F)
    yoko.append((D, E, F))

X = sorted(list(X))
Y = sorted(list(Y))
H = len(X)
W = len(Y)
tate.sort()
yoko.sort()
grid = [[[1] * 4 for _ in range(W)] for _ in range(H)]

ix = {}
for i, x in enumerate(X):
    ix[x] = i
jy = {}
for j, y in enumerate(Y):
    jy[y] = j

for c, a, b in tate:
    ia = ix[a]
    ib = ix[b]
    jc = jy[c]
    for i in range(ia, ib):
        if jc - 1 >= 0:
            grid[i][jc - 1][1] = 0
        grid[i][jc][3] = 0
for d, e, f in yoko:
    i_d = ix[d]
    je = jy[e]
    jf = jy[f]
    for j in range(je, jf):
        if i_d - 1 >= 0:
            grid[i_d - 1][j][2] = 0
        grid[i_d][j][0] = 0

q = deque()
x0 = bisect_left(X, 0)
y0 = bisect_left(Y, 0)
path = [[1] * W for _ in range(H)]
path[x0][y0] = 0
q.append((x0, y0))
direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
cnt = 0
while q:
    x, y = q.popleft()
    cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
    for i, (dx, dy) in enumerate(direction):
        if grid[x][y][i]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                if path[nx][ny]:
                    path[nx][ny] = 0
                    q.append((nx, ny))
            else:
                print('INF')
                exit()
print(cnt)

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right, bisect_left

N, M = map(int, input().split())
tate = []
yoko = []
X = set()
Y = set()
for _ in range(N):
    A, B, C = map(int, input().split())
    X.add(A)
    X.add(B)
    Y.add(C)
    tate.append((C, A, B))
for _ in range(M):
    D, E, F = map(int, input().split())
    X.add(D)
    Y.add(E)
    Y.add(F)
    yoko.append((D, E, F))

X = sorted(list(X))
Y = sorted(list(Y))
H = len(X)
W = len(Y)
tate.sort()
yoko.sort()
grid = [[[1] * 4 for _ in range(W)] for _ in range(H)]

for c, a, b in tate:
    ia = bisect_left(X, a)
    ib = bisect_left(X, b)
    jc = bisect_left(Y, c)
    for i in range(ia, ib):
        if jc - 1 >= 0:
            grid[i][jc - 1][1] = 0
        grid[i][jc][3] = 0
for d, e, f in yoko:
    i_d = bisect_left(X, d)
    je = bisect_left(Y, e)
    jf = bisect_left(Y, f)
    for j in range(je, jf):
        if i_d - 1 >= 0:
            grid[i_d - 1][j][2] = 0
        grid[i_d][j][0] = 0

q = deque()
x0 = bisect_right(X, 0) - 1
y0 = bisect_right(Y, 0) - 1
path = [[1] * W for _ in range(H)]
path[x0][y0] = 0
q.append((x0, y0))
direction = ((-1, 0), (0, 1), (1, 0), (0, -1))
cnt = 0
while q:
    x, y = q.popleft()
    cnt += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
    for i, (dx, dy) in enumerate(direction):
        if grid[x][y][i]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H - 1 and 0 <= ny < W - 1:
                if path[nx][ny]:
                    path[nx][ny] = 0
                    q.append((nx, ny))
            else:
                print('INF')
                exit()
print(cnt)