Problem:


Score: 600 points

Problem Statement

There is a grass field that stretches infinitely.

In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0).

There are also N north-south lines and M east-west lines drawn on the field. The i-th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i), and the j-th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j).

What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF instead.

Constraints

All values in input are integers between -10^9 and 10^9  (inclusive).

1 \leq N, M \leq 1000

A_i < B_i\ (1 \leq i \leq N)

E_j < F_j\ (1 \leq j \leq M)

The point (0, 0) does not lie on any of the given segments.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
:
A_N B_N C_N
D_1 E_1 F_1
:
D_M E_M F_M

Output

If the area of the region the cow can reach is infinite, print INF; otherwise, print an integer representing the area in \mathrm{cm^2}.

(Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)

Sample Input 1

5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4

Sample Output 1

13

The area of the region the cow can reach is 13\ \mathrm{cm^2}.

Sample Input 2

6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4

Sample Output 2

INF

The area of the region the cow can reach is infinite.



Sample input:
5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4


Sample output:
13

Submission status: Runtime Error

Solution code:
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())

Submission status: Runtime Error

Solution code:
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())

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def compress(S):
    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(S)):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

def bfs(grid, src):
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    visited = list2d(H, W, 0)
    que = deque()
    for h, w in src:
        que.append((h, w))
        visited[h][w] = 1
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == -1:
                print('INF')
                exit()
            if grid[h2][w2] == 1:
                continue
            if visited[h2][w2]:
                continue
            visited[h2][w2] = 1
            que.append((h2, w2))
    return visited

N, M = MAP()
vert = []
horz = []
S1 = set([0])
S2 = set([0])
for i in range(N):
    h1, h2, w = MAP()
    h1 *= 2
    h2 *= 2
    w *= 2
    vert.append((h1, h2, w))
    S1.add(h1)
    S1.add(h1-1)
    S1.add(h1+1)
    S1.add(h2)
    S1.add(h2-1)
    S1.add(h2+1)
    S2.add(w)
for i in range(M):
    h, w1, w2 = MAP()
    h *= 2
    w1 *= 2
    w2 *= 2
    horz.append((h, w1, w2))
    S1.add(h)
    S1.add(h-1)
    S1.add(h+1)
    S2.add(w1)
    S2.add(w1-1)
    S2.add(w1+1)
    S2.add(w2)
    S2.add(w2-1)
    S2.add(w2+1)

zph, unzph = compress(S1)
zpw, unzpw = compress(S2)
H, W = len(zph), len(zpw)

grid = list2d(H, W, -1)
for i in range(1, H-1):
    for j in range(1, W-1):
        grid[i][j] = 0
for i in range(N):
    h1, h2, w = vert[i]
    w = zpw[w]
    for h in range(zph[h1], zph[h2]+1):
        grid[h][w] = 1
for i in range(M):
    h, w1, w2 = horz[i]
    h = zph[h]
    for w in range(zpw[w1], zpw[w2]+1):
        grid[h][w] = 1

res = bfs(grid, [(zph[0], zpw[0])])
# for row in res:
#     print(row)

ans = 0
sh, sw = 1 - zph[0]&1, 1 - zpw[0]&1
for i in range(sh, H-1, 2):
    for j in range(sw, W-1, 2):
        if res[i][j]:
            hln = unzph[i+2] - unzph[i]
            wln = unzpw[j+2] - unzpw[j]
            ans += hln * wln
print(ans//4)

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def compress(S):
    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(S)):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

def bfs(grid, src):
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    visited = list2d(H, W, 0)
    que = deque()
    for h, w in src:
        que.append((h, w))
        visited[h][w] = 1
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == -1:
                print('INF')
                exit()
            if grid[h2][w2] == 1:
                continue
            if visited[h2][w2]:
                continue
            visited[h2][w2] = 1
            que.append((h2, w2))
    return visited

N, M = MAP()
vert = []
horz = []
S1 = set([0])
S2 = set([0])
for i in range(N):
    h1, h2, w = MAP()
    h1 *= 2
    h2 *= 2
    w *= 2
    vert.append((h1, h2, w))
    S1.add(h1)
    S1.add(h1-1)
    S1.add(h1+1)
    S1.add(h2)
    S1.add(h2-1)
    S1.add(h2+1)
    S2.add(w)
for i in range(M):
    h, w1, w2 = MAP()
    h *= 2
    w1 *= 2
    w2 *= 2
    horz.append((h, w1, w2))
    S1.add(h)
    S1.add(h-1)
    S1.add(h+1)
    S2.add(w1)
    S2.add(w1-1)
    S2.add(w1+1)
    S2.add(w2)
    S2.add(w2-1)
    S2.add(w2+1)

zph, unzph = compress(S1)
zpw, unzpw = compress(S2)
H, W = len(zph), len(zpw)

grid = list2d(H, W, -1)
for i in range(1, H-1):
    for j in range(1, W-1):
        grid[i][j] = 0
for i in range(N):
    h1, h2, w = vert[i]
    w = zpw[w]
    for h in range(zph[h1], zph[h2]+1):
        grid[h][w] = 1
for i in range(M):
    h, w1, w2 = horz[i]
    h = zph[h]
    for w in range(zpw[w1], zpw[w2]+1):
        grid[h][w] = 1

res = bfs(grid, [(zph[0], zpw[0])])
# for row in res:
#     print(row)

ans = 0
sh, sw = 1 - zph[0]&1, 1 - zpw[0]&1
for i in range(sh, H-1, 2):
    for j in range(sw, W-1, 2):
        if res[i][j]:
            hln = unzph[i+1] - unzph[i-1]
            wln = unzpw[j+1] - unzpw[j-1]
            ans += hln * wln
print(ans//4)

Submission status: Runtime Error

Solution code:
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())

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def compress(S):
    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(S)):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

def bfs(grid, src):
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    visited = list2d(H, W, 0)
    que = deque()
    for h, w in src:
        que.append((h, w))
        visited[h][w] = 1
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == -1:
                print('INF')
                exit()
            if grid[h2][w2] == 1:
                continue
            if visited[h2][w2]:
                continue
            visited[h2][w2] = 1
            que.append((h2, w2))
    return visited

N, M = MAP()
vert = []
horz = []
S1 = set([0])
S2 = set([0])
for i in range(N):
    h1, h2, w = MAP()
    h1 *= 2
    h2 *= 2
    w *= 2
    vert.append((h1, h2, w))
    S1.add(h1)
    S1.add(h1-1)
    S1.add(h1+1)
    S1.add(h2)
    S1.add(h2-1)
    S1.add(h2+1)
    S2.add(w)
for i in range(M):
    h, w1, w2 = MAP()
    h *= 2
    w1 *= 2
    w2 *= 2
    horz.append((h, w1, w2))
    S1.add(h)
    S1.add(h-1)
    S1.add(h+1)
    S2.add(w1)
    S2.add(w1-1)
    S2.add(w1+1)
    S2.add(w2)
    S2.add(w2-1)
    S2.add(w2+1)

zph, unzph = compress(S1)
zpw, unzpw = compress(S2)
H, W = len(zph), len(zpw)

grid = list2d(H, W, -1)
for i in range(1, H-1):
    for j in range(1, W-1):
        grid[i][j] = 0
for i in range(N):
    h1, h2, w = vert[i]
    w = zpw[w]
    for h in range(zph[h1], zph[h2]+1):
        grid[h][w] = 1
for i in range(M):
    h, w1, w2 = horz[i]
    h = zph[h]
    for w in range(zpw[w1], zpw[w2]+1):
        grid[h][w] = 1

res = bfs(grid, [(zph[0], zpw[0])])
# for row in res:
#     print(row)

ans = 0
sh, sw = 1 - zph[0]&1, 1 - zpw[0]&1
for i in range(sh, H-1, 2):
    for j in range(sw, W-1, 2):
        if res[i][j]:
            hln = unzph[i+1] - unzph[i]
            wln = unzpw[j+1] - unzpw[j]
            ans += hln * wln
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,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 for _ in range(len(UY)*2)]
    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 not 2<=nny<len(UY)*2-2 or not 2<=nnx<len(UX)*2-2:
            print('INF')
            exit()
        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 ny==0 or ny==len(UY)*2-1 or nx==0 or nx==len(UX)*2-1:
                    print('INF')
                    exit()
                if not used[nny][nnx]:
                    que.append((nny,nnx))
                    used[nny][nnx]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,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 for _ in range(len(UY)*2)]
    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):
        ny,nx=dicty[0]+dy[k],dictx[0]+dx[k]
        if not 1<=ny<len(UY)*2-1 or not 1<=nx<len(UX)*2-1:
            print('INF')
            exit()
        que.append((ny,nx))
        used[ny][nx]=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]
            if c[ny][nx]==0:
                if not 1<=ny<len(UY)*2-1 or not 1<=nx<len(UX)*2-1:
                    print('INF')
                    exit()
                if not used[ny+dy[k]][nx+dx[k]]:
                    que.append((ny+dy[k],nx+dx[k]))
                    used[ny+dy[k]][nx+dx[k]]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,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 for _ in range(len(UY)*2)]
    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):
        ny,nx=dicty[0]+dy[k],dictx[0]+dx[k]
        if not 0<=ny<len(UY)*2 or not 0<=nx<len(UX)*2:
            print('INF')
            exit()
        que.append((ny,nx))
        used[ny][nx]=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]
            if c[ny][nx]==0:
                if not 0<=ny<len(UY)*2 or not 0<=nx<len(UX)*2:
                    print('INF')
                    exit()
                if not used[ny+dy[k]][nx+dx[k]]:
                    que.append((ny+dy[k],nx+dx[k]))
                    used[ny+dy[k]][nx+dx[k]]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,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 for _ in range(len(UY)*2)]
    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):
        ny,nx=dicty[0]+dy[k],dictx[0]+dx[k]
        que.append((ny,nx))
        used[ny][nx]=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]
            if c[ny][nx]==0:
                if ny==0 or ny==len(UY)*2-1 or nx==0 or nx==len(UX)*2-1:
                    print('INF')
                    exit()
                if not used[ny+dy[k]][nx+dx[k]]:
                    que.append((ny+dy[k],nx+dx[k]))
                    used[ny+dy[k]][nx+dx[k]]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,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 for _ in range(len(UY)*2)]
    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):
        ny,nx=dicty[0]+dy[k],dictx[0]+dx[k]
        que.append((ny,nx))
        used[ny][nx]=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]
            if c[ny][nx]==0 and not used[ny+dy[k]][nx+dx[k]]:
                if ny==0 or ny==len(UY)*2-1 or nx==0 or nx==len(UX)*2-1:
                    print('INF')
                    exit()
                que.append((ny+dy[k],nx+dx[k]))
                used[ny+dy[k]][nx+dx[k]]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

h_lines = {}
v_lines = {}

for _ in range(N):
	a, b, c = map(int, input().split())
	if c in v_lines:
		v_lines[c].append((a, b))
	else:
		v_lines[c] = [(a, b)]

for _ in range(M):
	d, e, f = map(int, input().split())
	if d in h_lines:
		h_lines[d].append((e, f))
	else:
		h_lines[d] = [(e, f)]

h_lines = list(h_lines.items())
v_lines = list(v_lines.items())

h_lines.sort()
v_lines.sort()

rows = len(v_lines) - 1
cols = len(h_lines) - 1

rows = cols = max(rows, cols) + 1


h_walls = [[False] * rows for _ in range(cols + 1)]
v_walls = [[False] * (rows + 1) for _ in range(cols)]

for i, (y, l) in enumerate(h_lines):
	for x1, x2 in l:
		j = 0
		while j < rows:
			if x1 <= v_lines[j][0]:
				break
			j += 1
		while j < rows:
			if x2 < v_lines[j + 1][0]:
				break
			h_walls[i][j] = True
			j += 1

for j, (x, l) in enumerate(v_lines):
	for y1, y2 in l:
		i = 0
		while i < cols:
			if y1 <= h_lines[i][0]:
				break
			i += 1
		while i < cols:
			if y2 < h_lines[i + 1][0]:
				break
			v_walls[i][j] = True
			i += 1

#for i in range(cols + 1):
#	print("+" + "+".join("--" if f else "  " for f in h_walls[i]) + "+")
#	if i < cols:
#		print("  ".join("|" if f else " " for f in v_walls[i]))

def find_initial_pos():
	for i in range(cols):
		if h_lines[i][0] <= 0 and 0 <= h_lines[i + 1][0]:
			for j in range(rows):
				if v_lines[j][0] <= 0 and 0 <= v_lines[j + 1][0]:
					return (i, j)
	return None

def calc_area():
	cur = find_initial_pos()
	if cur == None:
		return "INF"
	stack = [cur]
	area = 0
	visited = [[False] * rows for _ in range(cols)]
	visited[cur[0]][cur[1]] = True
	
	search = (
		( 1,  0, lambda y, x: not h_walls[y + 1][x]),
		(-1,  0, lambda y, x: not h_walls[y][x]),
		( 0,  1, lambda y, x: not v_walls[y][x + 1]),
		( 0, -1, lambda y, x: not v_walls[y][x]),
	)
	
	while stack:
		y, x = stack.pop()
		area += (h_lines[y + 1][0] - h_lines[y][0]) * (v_lines[x + 1][0] - v_lines[x][0])
#		print(area, y, x)
		for dy, dx, check in search:
			if check(y, x):
				ny = y + dy
				nx = x + dx
#				print(">", ny, nx)
				if not visited[ny][nx]:
					if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
						return "INF"
					stack.append((ny, nx))
					visited[ny][nx] = True
	
	return str(area)

print(calc_area())