Problem p02680 (python)

Fixed submission:
import sys
#import numpy as np
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2
    #print("grid size: (h,w)=({},{})".format(h, w))

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0 or start_x >= h - 1 or start_y >= w - 1:
        print("INF")
        return
    grid[start_x][start_y] = 1
    #print("start=({}, {})".format(start_x, start_y))
    #print(np.array(grid))

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    ans = 0
    q = deque([(start_x, start_y)])
    grid[start_x][start_y] = 1
    while q:
        x, y = q.popleft()
        #print("({}, {})".format(x, y))
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (nx == h - 2 and grid[nx][ny] == 0) or ny == w:
                print("INF")
                return
            if grid[nx][ny] != 0: continue
            nnx, nny = nx + dx[i], ny + dy[i]
            if nnx < 0 or nny < 0 or nnx == h - 1 or nny == w - 1:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue  # 既に訪れたか、柵に乗ったら無視
            grid[nnx][nny] = 1
            q.append((nnx, nny))
        #print(q)
        #print(np.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
#import numpy as np
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2
    #print("grid size: (h,w)=({},{})".format(h, w))

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0:
        print("INF")
        return
    grid[start_x][start_y] = 1
    #print("start=({}, {})".format(start_x, start_y))
    #print(np.array(grid))

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    ans = 0
    q = deque([(start_x, start_y)])
    grid[start_x][start_y] = 1
    while q:
        x, y = q.popleft()
        #print("({}, {})".format(x, y))
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (nx == 0 and grid[0][ny] == 0) or (ny == 0 and grid[nx][0] == 0):
                print("INF")
                return
            if (nx == h - 2 and grid[nx][ny] == 0) or (ny == w - 2 and grid[nx][ny] == 0):
                print("INF")
                return
            if grid[nx][ny] != 0: continue
            nnx, nny = nx + dx[i], ny + dy[i]
            if nnx < 0 or nny < 0 or nnx == h - 1 or nny == w - 1:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue  # 既に訪れたか、柵に乗ったら無視
            grid[nnx][nny] = 1
            q.append((nnx, nny))
        #print(q)
        #print(np.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
#import numpy as np
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2
    #print("grid size: (h,w)=({},{})".format(h, w))

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0:
        print("INF")
        return
    grid[start_x][start_y] = 1
    #print("start=({}, {})".format(start_x, start_y))
    #print(np.array(grid))

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    ans = 0
    q = deque([(start_x, start_y)])
    grid[start_x][start_y] = 1
    while q:
        x, y = q.popleft()
        #print("({}, {})".format(x, y))
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx == h or ny == w:
                print("INF")
                return
            if grid[nx][ny] != 0: continue
            nnx, nny = nx + dx[i], ny + dy[i]
            if nnx < 0 or nny < 0 or nnx == h - 1 or nny == w - 1:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue  # 既に訪れたか、柵に乗ったら無視
            grid[nnx][nny] = 1
            q.append((nnx, nny))
        #print(q)
        #print(np.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
#import numpy as np
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2
    #print("grid size: (h,w)=({},{})".format(h, w))

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0:
        print("INF")
        return
    grid[start_x][start_y] = 1
    #print("start=({}, {})".format(start_x, start_y))
    #print(np.array(grid))

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    ans = 0
    q = deque([(start_x, start_y)])
    grid[start_x][start_y] = 1
    while q:
        x, y = q.popleft()
        #print("({}, {})".format(x, y))
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx == h or ny == w:
                print("INF")
                return
            if grid[nx][ny] != 0: continue
            nnx, nny = nx + dx[i], ny + dy[i]
            if nnx < 0 or nny < 0:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue  # 既に訪れたか、柵に乗ったら無視
            grid[nnx][nny] = 1
            q.append((nnx, nny))
        #print(q)
        #print(np.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0 or start_x >= h // 2 or start_y >= w // 2:
        print("INF")
        return
    grid[start_x][start_y] = 1

    # BFS
    q = deque([(start_x, start_y)]) # 進入可能な領域がqには入る
    ans = 0
    while q:
        x, y = q.popleft()
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for xx, yy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = x + xx, y + yy
            if nx >= h or ny >= w: # or nx < 0 or ny < 0
                print("INF")
                return
            if grid[nx][ny] == -1: continue
            nnx, nny = nx + xx, ny + yy
            if nnx < 0 or nny < 0 or nnx >= h or nny >= w:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue
            grid[nnx][nny] = 1
            q.append((nnx, nny))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0 or start_x >= h // 2 or start_y >= w // 2:
        print("INF")
        return
    grid[start_x][start_y] = 1

    # BFS
    q = deque([(start_x, start_y)]) # 進入可能な領域がqには入る
    ans = 0
    while q:
        x, y = q.popleft()
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for xx, yy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx, ny = x + xx, y + yy
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                print("INF")
                return
            if grid[nx][ny] == -1: continue
            nnx, nny = nx + xx, ny + yy
            if nnx < 0 or nny < 0 or nnx >= h or nny >= w:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue
            grid[nnx][nny] = 1
            q.append((nnx, nny))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0:
        print("INF")
        return
    grid[start_x][start_y] = 1

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    q = deque([(start_x, start_y)]) # 進入可能な領域がqには入る
    ans = 0
    while q:
        x, y = q.popleft()
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for xx, yy in zip(dx, dy):
            nx, ny = x + xx, y + yy
            if nx >= h or ny >= w:
                print("INF")
                return
            if grid[nx][ny] == -1: continue
            nnx, nny = nx + xx, ny + yy
            if nnx < 0 or nny < 0 or nnx >= h or nny >= w:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue
            grid[nnx][nny] = 1
            q.append((nnx, nny))
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    # 座標圧縮とはすなわち左（下）から何番目かを求めることに他ならない
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    # 圧縮後の座標平面に対してグリッドを張るので、そのサイズを求めておく
    # 柵は偶数マス目に乗るようにするので２倍しておく
    h = len(mapX) * 2
    w = len(mapY) * 2

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0:
        print("INF")
        return
    grid[start_x][start_y] = 1

    # BFS
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    q = deque([(start_x, start_y)]) # 進入可能な領域がqには入る
    ans = 0
    while q:
        x, y = q.popleft()
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for xx, yy in zip(dx, dy):
            nx, ny = x + xx, y + yy
            if grid[nx][ny] == -1: continue
            nnx, nny = nx + xx, ny + yy
            if nnx < 0 or nny < 0 or nnx >= h or nny >= w:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue
            grid[nnx][nny] = 1
            q.append((nnx, nny))
    print(ans)


if __name__ == "__main__":
    main()