Problem p02680 (python)

Fixed submission:
def f_single_dot():
    # https://atcoder.jp/contests/abc168/submissions/13368489
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    X, Y = set([0]), set([0])
    A, B, C = [0] * N, [0] * N, [0] * N
    for i in range(N):
        A[i], B[i], C[i] = map(int, input().split())
        X.add(A[i])
        X.add(B[i])
        Y.add(C[i])
    D, E, F = [0] * M, [0] * M, [0] * M
    for i in range(M):
        D[i], E[i], F[i] = map(int, input().split())
        X.add(D[i])
        Y.add(E[i])
        Y.add(F[i])
    UX = list(X)
    UY = list(Y)
    UX.sort()
    UY.sort()
    dictx, dicty = {n: i * 2 for i, n in enumerate(UX)}, {n: i * 2 for i, n in enumerate(UY)}
    LX = [UX[i // 2 + 1] - UX[i // 2] if i % 2 else 0 for i in range(len(UX) * 2 - 1)]
    LY = [UY[i // 2 + 1] - UY[i // 2] if i % 2 else 0 for i in range(len(UY) * 2 - 1)]
    c = [[0] * (len(UX) * 2 - 1) for _ in range(len(UY) * 2 - 1)]
    for i in range(N):
        y = dicty[C[i]]
        for x in range(dictx[A[i]], dictx[B[i]] + 1):
            c[y][x] = 1
    for i in range(M):
        x = dictx[D[i]]
        for y in range(dicty[E[i]], dicty[F[i]] + 1):
            c[y][x] = 1
    que = deque()
    used = [[0] * len(UX) * 2 for _ in range(len(UY) * 2)]
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    for k in range(4):
        nny, nnx = dicty[0] + dy[k], dictx[0] + dx[k]
        if 1 <= nny < len(UY) * 2 - 1 and 1 <= nnx < len(UX) * 2 - 1:
            que.append((nny, nnx))
            used[nny][nnx] = 1
    ans = 0
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    while que:
        y, x = que.popleft()
        if y % 2 and x % 2:
            ans += LY[y] * LX[x]
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            nny, nnx = ny + dy[k], nx + dx[k]
            if c[ny][nx] == 0:
                if nny < 0 or nny >= len(UY) * 2 - 1 or nnx < 0 or nnx >= len(UX) * 2 - 1:
                    return 'INF'
                if not used[nny][nnx]:
                    que.append((nny, nnx))
                    used[nny][nnx] = 1
    return ans

print(f_single_dot())

Buggy submission (verdict: Runtime Error):
def f_single_dot():
    # https://atcoder.jp/contests/abc168/submissions/13368489
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    x_set, y_set = set([0]), set([0])  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)

    vertical_lines = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        vertical_lines.append((a, b, c))
        x_set |= {a, b}
        y_set |= {c}

    horizontal_lines = []
    for _ in range(M):
        d, e, f = map(int, input().split())
        horizontal_lines.append((d, e, f))
        x_set |= {d}
        y_set |= {e, f}

    x_set = sorted(x_set)
    y_set = sorted(y_set)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_encoded = {n: i * 2 for i, n in enumerate(x_set)}
    y_encoded = {n: i * 2 for i, n in enumerate(y_set)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    x_length = [x_set[i // 2 + 1] - x_set[i // 2] if i %
                2 else 0 for i in range(len(x_set) * 2 - 1)]
    y_length = [y_set[i // 2 + 1] - y_set[i // 2] if i %
                2 else 0 for i in range(len(y_set) * 2 - 1)]

    grid = [[0] * (len(y_set) * 2 - 1) for _ in range(len(x_set) * 2 - 1)]
    for a, b, c in vertical_lines:
        a, b, c = x_encoded[a], x_encoded[b], y_encoded[c]
        for x in range(a, b + 1):
            grid[x][c] = 1
    for d, e, f in horizontal_lines:
        d, e, f = x_encoded[d], y_encoded[e], y_encoded[f]
        for y in range(e, f + 1):
            grid[d][y] = 1

    que = deque()
    used = [[0] * len(y_set) * 2 for _ in range(len(x_set) * 2)]
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    for k in range(4):
        nny, nnx = y_encoded[0] + dy[k], x_encoded[0] + dx[k]
        if 1 <= nny < len(y_set) * 2 - 1 and 1 <= nnx < len(x_set) * 2 - 1:
            que.append((nny, nnx))
            used[nnx][nny] = 1
    ans = 0
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        if x % 2 and y % 2:
            ans += x_length[x] * y_length[y]
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            nnx, nny = nx + dx[k], ny + dy[k]
            if grid[nx][ny] == 0:
                if nnx < 0 or nnx >= len(x_set) * 2 - 1 or nny < 0 or nny >= len(y_set) * 2 - 1:
                    return 'INF'
                if not used[nnx][nny]:
                    que.append((nnx, nny))
                    used[nnx][nny] = 1
    return ans

print(f_single_dot())

Buggy submission (verdict: Runtime Error):
def f_single_dot():
    # https://atcoder.jp/contests/abc168/submissions/13368489
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    x_set, y_set = set([0]), set([0])  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)

    vertical_lines = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        vertical_lines.append((a, b, c))
        x_set |= {a, b}
        y_set |= {c}

    horizontal_lines = []
    for _ in range(M):
        d, e, f = map(int, input().split())
        horizontal_lines.append((d, e, f))
        x_set |= {d}
        y_set |= {e, f}

    x_set = sorted(x_set)
    y_set = sorted(y_set)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_encoded = {n: i * 2 for i, n in enumerate(x_set)}
    y_encoded = {n: i * 2 for i, n in enumerate(y_set)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    x_length = [x_set[i // 2 + 1] - x_set[i // 2] if i %
                2 else 0 for i in range(len(x_set) * 2 - 1)]
    y_length = [y_set[i // 2 + 1] - y_set[i // 2] if i %
                2 else 0 for i in range(len(y_set) * 2 - 1)]

    # 壁を埋めていく (累積和を用いていない)
    x_size, y_size = 2 * len(x_set) - 1, 2 * len(y_set) - 1
    grid = [[0] * y_size for _ in range(x_size)]
    for a, b, c in vertical_lines:
        a, b, c = x_encoded[a], x_encoded[b], y_encoded[c]
        for x in range(a, b + 1):
            grid[x][c] = 1
    for d, e, f in horizontal_lines:
        d, e, f = x_encoded[d], y_encoded[e], y_encoded[f]
        for y in range(e, f + 1):
            grid[d][y] = 1

    que = deque()
    used = [[0] * (y_size + 1) for _ in range(x_size + 1)]
    dy = [1, 1, -1, -1]
    dx = [1, -1, 1, -1]
    for k in range(4):
        nny, nnx = y_encoded[0] + dy[k], x_encoded[0] + dx[k]
        if 1 <= nny < len(y_set) * 2 - 1 and 1 <= nnx < len(x_set) * 2 - 1:
            que.append((nny, nnx))
            used[nny][nnx] = 1
    ans = 0
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        if x % 2 and y % 2:
            ans += x_length[x] * y_length[y]
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]
            nny, nnx = ny + dy[k], nx + dx[k]
            if grid[nx][ny] == 0:
                if nnx < 0 or nnx >= y_size or nnx < 0 or nnx >= x_size:
                    return 'INF'
                if not used[nnx][nny]:
                    que.append((nnx, nny))
                    used[nnx][nny] = 1
    return ans

print(f_single_dot())

Buggy submission (verdict: Runtime Error):
def f_single_dot():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, M = [int(i) for i in input().split()]

    x, y = {0}, {0}  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)
    A, B, C = [0] * N, [0] * N, [0] * N
    for i in range(N):
        A[i], B[i], C[i] = [int(i) for i in input().split()]
        x.add(A[i])
        x.add(B[i])
        y.add(C[i])
    D, E, F = [0] * M, [0] * M, [0] * M
    for i in range(M):
        D[i], E[i], F[i] = [int(i) for i in input().split()]
        x.add(D[i])
        y.add(E[i])
        y.add(F[i])
    x = sorted(x)
    y = sorted(y)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_comp = {x: 2 * k for k, x in enumerate(x)}
    y_comp = {y: 2 * k for k, y in enumerate(y)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    length_x = [x[i // 2 + 1] - x[i // 2] if i % 2 else 0 for i in range(len(x) * 2 - 1)]
    length_y = [y[i // 2 + 1] - y[i // 2] if i % 2 else 0 for i in range(len(y) * 2 - 1)]

    x_size, y_size = 2 * len(x) - 1, 2 * len(y) - 1
    grid = [[0] * y_size for _ in range(x_size)]

    # 壁を埋めていく
    for i in range(N):
        a, b, c = x_comp[A[i]], x_comp[B[i]], y_comp[C[i]]
        for x in range(a, b + 1):
            grid[x][c] = 1
    for i in range(M):
        d, e, f = x_comp[D[i]], y_comp[E[i]], y_comp[F[i]]
        for y in range(e, f + 1):
            grid[d][y] = 1

    ans = 0
    diff = ((-1, 0), (1, 0), (0, -1), (0, 1))
    start_x, start_y = x_comp[0], y_comp[0]
    is_visited = [[False] * (y_size + 1) for _ in range(x_size + 1)]
    queue = deque([(start_x, start_y)])
    while queue:
        x, y = queue.pop()
        is_visited[x][y] = True
        if (x % 2) & (y % 2):
            ans += length_x[x] * length_y[y]  # 今いるマスの面積
        for dx, dy in diff:
            nx, ny = x + dx, y + dy
            if not ((0 <= x < x_size) and (0 <= y < y_size)):
                return 'INF'  # グリッドの外へ出た ⇔ 囲いになっていない
            if (not is_visited[nx][ny]) and (grid[nx][ny] == 0):
                queue.appendleft((nx, ny))
                is_visited[nx][ny] = True
    return ans

print(f_single_dot())

Buggy submission (verdict: Runtime Error):
def f_single_dot():
    from collections import deque
    N, M = [int(i) for i in input().split()]

    x, y = {0}, {0}  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)
    A, B, C = [0] * N, [0] * N, [0] * N
    for i in range(N):
        A[i], B[i], C[i] = [int(i) for i in input().split()]
        x.add(A[i])
        x.add(B[i])
        y.add(C[i])
    D, E, F = [0] * M, [0] * M, [0] * M
    for i in range(M):
        D[i], E[i], F[i] = [int(i) for i in input().split()]
        x.add(D[i])
        y.add(E[i])
        y.add(F[i])
    x = sorted(x)
    y = sorted(y)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_comp = {x: 2 * k for k, x in enumerate(x)}
    y_comp = {y: 2 * k for k, y in enumerate(y)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    length_x = [x[i // 2 + 1] - x[i // 2] if i % 2 else 0 for i in range(len(x) * 2 - 1)]
    length_y = [y[i // 2 + 1] - y[i // 2] if i % 2 else 0 for i in range(len(y) * 2 - 1)]

    x_size, y_size = 2 * len(x) - 1, 2 * len(y) - 1
    grid = [[0] * y_size for _ in range(x_size)]

    # 壁を埋めていく
    for i in range(N):
        a, b, c = x_comp[A[i]], x_comp[B[i]], y_comp[C[i]]
        for x in range(a, b + 1):
            grid[x][c] = 1
    for i in range(M):
        d, e, f = x_comp[D[i]], y_comp[E[i]], y_comp[F[i]]
        for y in range(e, f + 1):
            grid[d][y] = 1

    ans = 0
    diff = ((-1, 0), (1, 0), (0, -1), (0, 1))
    start_x, start_y = x_comp[0], y_comp[0]
    is_visited = [[False] * y_size for _ in range(x_size)]
    queue = deque([(start_x, start_y)])
    while queue:
        x, y = queue.pop()
        is_visited[x][y] = True
        if (x % 2) & (y % 2):
            ans += length_x[x] * length_y[y]  # 今いるマスの面積
        for dx, dy in diff:
            nx, ny = x + dx, y + dy
            if not ((0 <= x < x_size) and (0 <= y < y_size)):
                return 'INF'  # グリッドの外へ出た ⇔ 囲いになっていない
            if (not is_visited[nx][ny]) and (grid[nx][ny] == 0):
                queue.appendleft((nx, ny))
                is_visited[nx][ny] = True
    return ans

print(f_single_dot())

Buggy submission (verdict: Runtime Error):
def f_single_dot():
    from collections import deque
    N, M = [int(i) for i in input().split()]

    x, y = {0}, {0}  # 重複を除いた xy 座標の一覧 (座標圧縮に必要)
    vertical_lines = []
    horizontal_lines = []
    for _ in range(N):
        a, b, c = [int(i) for i in input().split()]
        vertical_lines.append((a, b, c))
        x |= {a, b}
        y |= {c}
    for _ in range(M):
        d, e, f = [int(i) for i in input().split()]
        horizontal_lines.append((d, e, f))
        x |= {d}
        y |= {e, f}
    x = sorted(x)
    y = sorted(y)

    # 座標圧縮 (壁も配列に格納するので、2 倍している)
    x_comp = {x: 2 * k for k, x in enumerate(x)}
    y_comp = {y: 2 * k for k, y in enumerate(y)}
    # 座標圧縮されたグリッドで縦横に 1 マス分進むことは実際にはどれくらい進んだことなのか
    length_x = [x[i // 2 + 1] - x[i // 2] if i % 2 else 0 for i in range(len(x) * 2 - 1)]
    length_y = [y[i // 2 + 1] - y[i // 2] if i % 2 else 0 for i in range(len(y) * 2 - 1)]

    x_size, y_size = 2 * len(x) - 1, 2 * len(y) - 1
    grid = [[0] * y_size for _ in range(x_size)]

    wall_vertical = [[0] * (y_size + 1) for _ in range(x_size + 1)]
    wall_horizontal = [[0] * (y_size + 1) for _ in range(x_size + 1)]
    # 壁を埋めていく
    for a, b, c in vertical_lines:
        a, b, c = x_comp[a], x_comp[b], y_comp[c]
        wall_vertical[a][c] += 1
        wall_vertical[b + 1][c] -= 1
    for y in range(y_size):
        for x in range(x_size):
            wall_vertical[x + 1][y] += wall_vertical[x][y]
    for d, e, f in horizontal_lines:
        d, e, f = x_comp[d], y_comp[e], y_comp[f]
        wall_horizontal[d][e] += 1
        wall_horizontal[d][f + 1] -= 1
    for x in range(x_size):
        for y in range(y_size):
            wall_horizontal[x][y + 1] += wall_horizontal[x][y]
    for x in range(x_size):
        for y in range(y_size):
            grid[x][y] = (wall_vertical[x][y] | wall_horizontal[x][y] >= 1) & 1

    ans = 0
    diff = ((-1, 0), (1, 0), (0, -1), (0, 1))
    start_x, start_y = x_comp[0], y_comp[0]
    is_visited = [[False] * y_size for _ in range(x_size)]
    queue = deque([(start_x, start_y)])
    while queue:
        x, y = queue.pop()
        is_visited[x][y] = True
        if (x % 2) & (y % 2):
            ans += length_x[x] * length_y[y]  # 今いるマスの面積
        for dx, dy in diff:
            nx, ny = x + dx, y + dy
            if not ((0 <= x < x_size) and (0 <= y < y_size)):
                return 'INF'  # グリッドの外へ出た ⇔ 囲いになっていない
            if (not is_visited[nx][ny]) and (grid[nx][ny] == 0):
                queue.appendleft((nx, ny))
                is_visited[nx][ny] = True
    return ans

print(f_single_dot())