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:
import numpy as np
from numba import njit
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X)) 
@njit
def f(i,j):
    s = [(i,j)]
    v = set()
    r = 0
    while s:
        i, j = s.pop()
        if (i,j) in v:
            continue
        v.add((i,j))
        if not (0<=i<H and 0<=j<W):
            print('INF')
            break
        r += S[i][j]
        if U[i][j]:
            s.append((i-1,j))
        if U[i+1][j]:
            s.append((i+1,j))
        if L[i][j]:
            s.append((i,j-1))
        if L[i][j+1]:
            s.append((i,j+1))
    else:
        print(r)
f()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())

x_items = list(set(a+b+d+[0]))
y_items = list(set(c+e+f+[0]))

x_items.sort()
y_items.sort()
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1


h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2

for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2

q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
flug1 = True

grid[xo][yo] = 1
ans = 0
while q:
    x, y = q.popleft()
    if x%2 != 0 and y%2 != 0:
        xx = x_items[(x+1)//2] - x_items[(x-1)//2]
        yy = y_items[(y+1)//2] - y_items[(y-1)//2]
        ans = ans + xx*yy
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            flug1 = False
            break
        if ny < 0 or ny >= w:
            flug1 = False
            break
        if grid[x+dx[i]][y+dy[i]] == 0:           
            grid[x+dx[i]][y+dy[i]] = 1
            q.append((x+dx[i],y+dy[i]))
    if flug1 == False:
        ans = "INF"
        break

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())

x_items = list(set(a+b+d+[0]))
y_items = list(set(c+e+f+[0]))

x_items.sort()
y_items.sort()
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1


h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2

for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2

q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
flug1 = True

grid[xo][yo] = 1
ans = 0
while q:
    x, y = q.popleft()
    if x%2 != 0 and y%2 != 0:
        xx = x_items[x//2+1] - x_items[x//2]
        yy = y_items[y//2+1] - y_items[y//2]
        ans = ans + xx*yy
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            flug1 = False
            break
        if ny < 0 or ny >= w:
            flug1 = False
            break
        if grid[x+dx[i]][y+dy[i]] == 0:
            grid[x+dx[i]][y+dy[i]] = 1
            q.append((x+dx[i],y+dy[i]))
    if flug1 == False:
        ans = "INF"
        break

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())

x_items = list(set(a+b+d+[0]))
y_items = list(set(c+e+f+[0]))

x_items.sort()
y_items.sort()
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1


h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2

for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2

q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
flug1 = True

grid[xo][yo] = 1
#xx = x_items[xo//2+1] - x_items[xo//2]
#yy = y_items[yo//2+1] - y_items[yo//2]
#ans = xx*yy
ans = 0
while q:
    x, y = q.popleft()
    if x%2 != 0 and y%2 != 0:
        xx = x_items[x//2+1] - x_items[x//2]
        yy = y_items[y//2+1] - y_items[y//2]
        ans = ans + xx*yy
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            flug1 = False
            break
        if ny < 0 or ny >= w:
            flug1 = False
            break
        if grid[x+dx[i]][y+dy[i]] == 0:
            grid[x+dx[i]][y+dy[i]] = 1
            q.append((x+dx[i],y+dy[i]))
    if flug1 == False:
        ans = "INF"
        break

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from bisect import *
n, m = map(int, input().split())
a, b, c = zip(*(map(int, input().split()) for _ in range(n)))
d, e, f = zip(*(map(int, input().split()) for _ in range(m)))
x = sorted(set(c + e + f))
y = sorted(set(a + b + d))
h = len(y)-1
w = len(x)-1
def tx(i):
    return bisect(x, i)-1
def ty(i):
    return bisect(y, i)-1
u = np.ones((h+1, w))
for d, e, f in zip(d, e, f):
    d, e, f = ty(d), tx(e), tx(f)
    u[d, e:f] = false
l = np.ones((h, w+1))
for a ,b, c in zip(a, b, c):
    a, b, c = ty(a), ty(b), tx(c)
    l[a:b, c] = false
s = np.outer(np.diff(y), np.diff(x)) 
i = bisect(y, 0)-1
j = bisect(x, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<h and 0<=j<w):
        print('inf')
        break
    r += s[i][j]
    if u[i][j]:
        s.append((i-1,j))
    if u[i+1][j]:
        s.append((i+1,j))
    if l[i][j]:
        s.append((i,j-1))
    if l[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np
from bisect import *
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X)) 
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += S[i][j]
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(X)-1
W = len(Y)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(X), np.diff(Y)) 
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += S[i][j]
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(X), np.diff(Y)) 
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += S[i][j]
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Runtime Error

Solution code:
import numpy as np
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(X)-1
W = len(Y)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(X), np.diff(Y)) 
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += S[i][j]
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f

    # 1. 座圧
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    for a, b, c in zip(A, B, C):
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    for d, e, f in zip(D, E, F):
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    W, H = len(mx), len(my)

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(W*H)

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.unite(i+j*H, i+1+j*H)
            if j+1 < H and segx[i][j] == 0:
                uf.unite(i+(j+1)*H, i+j*H)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*H
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.root(i+j*H) == uf.root(ushi):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f

    # 1. 座圧
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    for a, b, c in zip(A, B, C):
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    for d, e, f in zip(D, E, F):
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    W, H = len(mx), len(my)

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(W*H)

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(W):
        for j in range(H):
            if i+1 < len(mx) and segy[i][j] == 0:
                uf.unite(i+j*H, i+1+j*H)
            if j+1 < len(my) and segx[i][j] == 0:
                uf.unite(i+(j+1)*H, i+j*H)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*H
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    ushi_area = uf.root(ushi)
    for i in range(W-1):
        for j in range(H-1):
            if uf.root(i+j*H) == ushi_area:
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f

    # 1. 座圧
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    for a, b, c in zip(A, B, C):
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    for d, e, f in zip(D, E, F):
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    W, H = len(x), len(y)

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(W*H)

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(W):
        for j in range(H):
            if i+1 < len(mx) and segy[i][j] == 0:
                uf.unite(i+j*H, i+1+j*H)
            if j+1 < len(my) and segx[i][j] == 0:
                uf.unite(i+(j+1)*H, i+j*H)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*H
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    ushi_area = uf.root(ushi)
    for i in range(W-1):
        for j in range(H-1):
            if uf.root(i+j*H) == ushi_area:
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    N, M = map(int, input().split())
    area = N+M

    mapX = dict()
    mapY = dict()

    lh = []
    lw = []
    for i in range(area):
        if i <= N-1:
            a, b, c = map(int, input().split())
            mapX[a] = 0
            mapX[b] = 0
            mapY[c] = 0
            lh.append({'a':a, 'b':b, 'c':c})
        else:
            c, a, b = map(int, input().split())
            mapY[a] = 0
            mapY[b] = 0
            mapX[c] = 0
            lw.append({'a':a, 'b':b, 'c':c})

    mapXs = dict(sorted(mapX.items()))
    mapYs = dict(sorted(mapY.items()))

    xg = list()
    yg = list()

    for k in mapXs:
        mapXs[k] = len(xg)
        xg.append(k)

    for k in mapYs:
        mapYs[k] = len(yg)
        yg.append(k)

    print(str(xg), '\n', str(yg))

    h = len(xg)*2
    w = len(yg)*2

    grid = np.zeros((h,w), int)

    for i in range(N):
        a = mapXs[lh[i]['a']]*2
        b = mapXs[lh[i]['b']]*2
        c = mapYs[lh[i]['c']]*2
        for j in range(a,b+1): grid[j][c] = -1

    for i in range(M):
        a = mapYs[lw[i]['a']]*2
        b = mapYs[lw[i]['b']]*2
        c = mapXs[lw[i]['c']]*2
        for j in range(a,b+1): grid[c][j] = -1

    print('befor BFS\n', str(grid))

    que = dict()
    cdX = mapXs[0]*2
    cdY = mapYs[0]*2

    grid[cdX][cdY] = 1
    que = [[cdX,cdY]]

    dx = [0,-1,0,1]
    dy = [-1,0,1,0]

    while len(que) != 0:
        q = que.pop(0)
        for i in range(4):
            currentX = q[0]+dx[i]
            currentY = q[1]+dy[i]
            if currentX < 0 or currentX >= h: continue
            if currentY < 0 or currentY >= w: continue
            if grid[currentX][currentY] != 0: continue

            grid[currentX][currentY]=1
            que.append([currentX,currentY])

    print('after BFS\n', str(grid))

    ans = 0
    for x in range(h):
        for y in range(w):
            if grid[x][y] != 1: continue
            if x%2 == 0 or y%2 == 0: continue
            if (x == 0 or x == h-1) or (y == 0 or y == w-1):
                print('INF')
                return
            
            ans += (xg[x%2+1]-xg[x%2])*(yg[y%2+1]-yg[y%2])

    print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def compress(set_):
    """座標圧縮した辞書を返す"""
    array2 = sorted(list(set_))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

def calc_s(hi, wj):
    """座標圧縮後の範囲hi <= i < hi + 1, wj <= j < wj + 1について、
    座標圧縮前の面積を求める
    """
    res = abs(h_rests[hi] - h_rests[hi + 1]) * abs(w_rests[wj] - w_rests[wj + 1]) 
    return res   

h, w = map(int, input().split())
info_h = [list(map(int, input().split())) for i in range(h)]
info_w = [list(map(int, input().split())) for i in range(w)]
INF = 10 ** 20

h_coords = set([-INF, 0, INF])
w_coords = set([-INF, 0, INF])

for h1, h2, w1 in info_h:
    h_coords.add(h1)
    h_coords.add(h2)
    w_coords.add(w1)
for h1, w1, w2 in info_w:
    h_coords.add(h1)
    w_coords.add(w1)
    w_coords.add(w2)


h_comps = compress(h_coords)
w_comps = compress(w_coords)

h_rests = {h_comps[index]: index for index in h_comps}
w_rests = {w_comps[index]: index for index in w_comps}


# いずれにも進める = 1
# 左右に進めない = 2
# 上下に進めない = 3
# 上下左右にも進めない = 6

# 半開区間の線分で管理
# 横線
# ●-●-●-●-○
# 縦線
# ○
# |
# ●
# |
# ●
# |
# ●

grid = [[1] * (3010) for i in range(3010)]
for h1, h2, w1 in info_h:
    h1, h2, w1 = h_comps[h1], h_comps[h2], w_comps[w1]
    for hi in range(h1 + 1, h2 + 1):
        grid[hi][w1] *= 2

for h1, w1, w2 in info_w:
    h1, w1, w2 = h_comps[h1], w_comps[w1], w_comps[w2]
    for wi in range(w1, w2):
        grid[h1][wi] *= 3


used = [[False] * (3010) for i in range(3010)]
si, sw = h_comps[0], w_comps[0]
stack = [(si, sw)]
ans = calc_s(si, sw)
used[si][sw] = True

while stack:
    i, j = stack.pop()
    # 上移動
    nxt_i, nxt_j = i - 1, j

    if grid[nxt_i][nxt_j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 上に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 下移動
    nxt_i, nxt_j = i + 1, j
    if grid[i][j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 下に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 右移動
    nxt_i, nxt_j = i, j + 1
    if grid[nxt_i][nxt_j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 右に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))
        
    # 左移動
    nxt_i, nxt_j = i, j - 1
    if grid[i][j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 左に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j)) 

    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)

Submission status: Runtime Error

Solution code:
def compress(set_):
    """座標圧縮した辞書を返す"""
    array2 = sorted(list(set_))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

def calc_s(hi, wj):
    """座標圧縮後の範囲hi <= i < hi + 1, wj <= j < wj + 1について、
    座標圧縮前の面積を求める
    """
    res = (h_rests[hi] - h_rests[hi + 1]) * (w_rests[wj] - w_rests[wj + 1]) 
    return res   

h, w = map(int, input().split())
info_h = [list(map(int, input().split())) for i in range(h)]
info_w = [list(map(int, input().split())) for i in range(w)]
INF = 10 ** 20

h_coords = set([-INF, 0, INF])
w_coords = set([-INF, 0, INF])

for h1, h2, w1 in info_h:
    h_coords.add(h1)
    h_coords.add(h2)
    w_coords.add(w1)
for h1, w1, w2 in info_w:
    h_coords.add(h1)
    w_coords.add(w1)
    w_coords.add(w2)


h_comps = compress(h_coords)
w_comps = compress(w_coords)

h_rests = {h_comps[index]: index for index in h_comps}
w_rests = {w_comps[index]: index for index in w_comps}


# いずれにも進める = 1
# 左右に進めない = 2
# 上下に進めない = 3
# 上下左右にも進めない = 6

# 半開区間の線分で管理
# 横線
# ●-●-●-●-○
# 縦線
# ●
# |
# ●
# |
# ●
# |
# ○

grid = [[1] * (3010) for i in range(3010)]
for h1, h2, w1 in info_h:
    h1, h2, w1 = h_comps[h1], h_comps[h2], w_comps[w1]
    for hi in range(h1, h2):
        grid[hi][w1] *= 2

for h1, w1, w2 in info_w:
    h1, w1, w2 = h_comps[h1], w_comps[w1], w_comps[w2]
    for wi in range(w1, w2):
        grid[h1][wi] *= 3


used = [[False] * (3010) for i in range(3010)]
si, sw = h_comps[0], w_comps[0]
stack = [(si, sw)]
ans = calc_s(si, sw)
used[si][sw] = True

while stack:
    i, j = stack.pop()
    # 上移動
    nxt_i, nxt_j = i - 1, j

    if grid[nxt_i][nxt_j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 上に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 下移動
    nxt_i, nxt_j = i + 1, j
    if grid[i][j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 下に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 右移動
    nxt_i, nxt_j = i, j + 1
    if grid[nxt_i][nxt_j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 右に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))
        
    # 左移動
    nxt_i, nxt_j = i, j - 1
    if grid[i][j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 左に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j)) 

    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)