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.

Solution (Python):


import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
from bisect import bisect_left, bisect_right
INF = 10 **18

def resolve():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    b = [list(map(int, input().split())) for i in range(m)]
 
    X = {-INF, INF}
    Y = {-INF, INF}
    for i in a:
        Y.add(i[2])
    for i in b:
        X.add(i[0])
 
    X = list(sorted(X))
    Y = list(sorted(Y))
    n = len(X) - 1
    m = len(Y) - 1
    wallx = [[False] * m for i in range(n)]
    wally = [[False] * m for i in range(n)]
 
    for x1, x2, y1 in a:
        x1 = bisect_left(X, x1)
        y1 = bisect_left(Y, y1)
        x2 = bisect_right(X, x2) - 1
        for i in range(x1, x2):
            wally[i][y1] = True
 
    for x1, y1, y2 in b:
        x1 = bisect_left(X, x1)
        y1 = bisect_left(Y, y1)
        y2 = bisect_right(Y, y2) - 1
        for i in range(y1, y2):
            wallx[x1][i] = True
 
    cow = [[False] * m for i in range(n)]
    cx = bisect_right(X, 0) - 1
    cy = bisect_right(Y, 0) - 1
    cow[cx][cy] = True
    q = [(cx, cy)]
    ans = 0
 
    while q:
        x, y = q.pop()
        if not x or not y:
            print("INF")
            sys.exit()
        ans += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        if x and not wallx[x][y] and not cow[x - 1][y]:
            cow[x - 1][y] = True
            q.append((x - 1, y))
        if y and not wally[x][y] and not cow[x][y - 1]:
            cow[x][y - 1] = True
            q.append((x, y - 1))
        if x + 1 < n and not wallx[x + 1][y] and not cow[x + 1][y]:
            cow[x + 1][y] = True
            q.append((x + 1, y))
        if y + 1 < m and not wally[x][y + 1] and not cow[x][y + 1]:
            cow[x][y + 1] = True
            q.append((x, y + 1)) 
    print(ans)
resolve()

Solution (Python):
from collections import deque

def main():
    n, m = map(int, input().split())
    INF = 10**20
    mapX = {INF, -INF}
    mapY = {INF, -INF}
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    lh = [None]*n
    lv = [None]*m
    for i in range(n):
        a, b, c = map(int, input().split())
        mapX.add(a)
        mapX.add(b)
        mapY.add(c)
        lh[i] = [a, b, c]
    for i in range(m):
        d, e, f = map(int, input().split())
        mapX.add(d)
        mapY.add(e)
        mapY.add(f)
        lv[i] = [d, e, f]
        
    x_len = len(mapX)*2 - 1
    y_len = len(mapY)*2 - 1
    mapX, mapY = sorted(list(mapX)), sorted(list(mapY))
    mapXi, mapYi = {val:i for i, val in enumerate(mapX)}, {val:i for i, val in enumerate(mapY)}
    grid = [[0]*y_len for _ in range(x_len)]
    
    x_range = [0] * x_len
    y_range = [0] * y_len
    x_range[0] = x_range[-1] = INF
    y_range[0] = y_range[-1] = INF
    
    for i, (x1, x2) in enumerate(zip(mapX, mapX[1:])):
        x_range[i*2 + 1] = x2 - x1
        if x1 <= 0 <= x2:
            sx = i*2 + 1
    
    for i, (y1, y2) in enumerate(zip(mapY, mapY[1:])):
        y_range[i*2 + 1] = y2 - y1
        if y1 <= 0 <= y2:
            sy = i*2 + 1
    
    for a, b, c in lh:
        y = mapYi[c]*2
        for x in range(mapXi[a]*2+1, mapXi[b]*2+1, 2):
            grid[x][y] = 1
    for a, b, c in lv:
        x = mapXi[a]*2
        for y in range(mapYi[b]*2+1, mapYi[c]*2+1, 2):
            grid[x][y] = 1
    q = deque()
    grid[sx][sy] = 1
    q.appendleft([sx, sy])
    ans = x_range[sx] * y_range[sy]
    while q:
        x, y = q.pop()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if grid[nx][ny]:
                continue
            nx += dx[i]
            ny += dy[i]
            if grid[nx][ny]:
                continue
            grid[nx][ny] = 1
            q.appendleft([nx, ny])
            ans += x_range[nx]*y_range[ny]
            if ans >= INF:
                print("INF")
                return
    print(ans)
        
            
if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline
    
    from collections import deque
    from bisect import bisect_left

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

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

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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline
    
    from collections import deque
    from bisect import bisect_left

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

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

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

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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict

input = sys.stdin.readline
n, m = map(int, input().split())

xx = set([0]); yy = set([0]);
aa = []; bb = []; cc = []; dd = []; ee = []; ff = []; 
for _ in range(n):
    a, b, c = map(int, input().split())
    xx.add(a)
    xx.add(b)
    yy.add(c)
    aa.append(a); bb.append(b); cc.append(c); 
for _ in range(m):
    d, e, f = map(int, input().split())
    xx.add(d)
    yy.add(e)
    yy.add(f)
    dd.append(d); ee.append(e); ff.append(f); 
xx = sorted(list(xx))
yy = sorted(list(yy))
xp = defaultdict(int)
yp = defaultdict(int)

for i, v in enumerate(xx):
    xp[v] = i
for i, v in enumerate(yy):
    yp[v] = i

h = len(xx) - 1
w = len(yy) - 1
lx = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
ly = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(n):
    a, b, c = aa[i], bb[i], cc[i]
    for x in range(xp[a], xp[b]):
        lx[x][yp[c]] = 1

for i in range(m):
    d, e, f = dd[i], ee[i], ff[i]
    for y in range(yp[e], yp[f]):
        ly[xp[d]][y] = 1

visited = [[False for _ in range(w)] for _ in range(h)]
sx, sy = min(xp[0], h - 1), min(yp[0], w - 1)
visited[sx][sy] = True
q = [(sx, sy)]
ans = 0

while q:
    x, y = q.pop()
    ans += (xx[x + 1] - xx[x]) * (yy[y + 1] - yy[y])
    if ly[x][y] == 0:
        if x == 0:
            print('INF'); exit();
        if not visited[x - 1][y]:
            visited[x - 1][y] = True
            q.append((x - 1, y))
    if lx[x][y] == 0:
        if y == 0:
            print('INF'); exit();
        if not visited[x][y - 1]:
            visited[x][y - 1] = True
            q.append((x, y - 1))
    if ly[x + 1][y] == 0:
        if x == h - 1:
            print('INF'); exit();
        if not visited[x + 1][y]:
            visited[x + 1][y] = True
            q.append((x + 1, y))
    if lx[x][y + 1] == 0:
        if y == w - 1:
            print('INF'); exit();
        if not visited[x][y + 1]:
            visited[x][y + 1] = True
            q.append((x, y + 1))

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n, m = LI()
horizontal = []
vertical = []
x_co = {INF, -INF}
y_co = {INF, -INF}
for _ in range(n):
    a, b, c = LI()
    x_co.add(a)
    x_co.add(b)
    y_co.add(c)
    vertical += [(a, b, c)]

for _ in range(m):
    d, e, f = LI()
    x_co.add(d)
    y_co.add(e)
    y_co.add(f)
    horizontal += [(d, e, f)]

x_len = len(x_co) * 2 - 1
y_len = len(y_co) * 2 - 1
x_co = sorted(list(x_co))
y_co = sorted(list(y_co))
x_comp = {val:i for i, val in enumerate(x_co)}
y_comp = {val:i for i, val in enumerate(y_co)}
grid = [[0] * y_len for _ in range(x_len)]

x_range = [0] * x_len
y_range = [0] * y_len
x_range[0] = x_range[-1] = INF
y_range[0] = y_range[-1] = INF

for i, (x1, x2) in enumerate(zip(x_co, x_co[1:])):
    x_range[i * 2 + 1] = x2 - x1
    if x1 <= 0 <= x2:
        sx = i * 2 + 1

for i, (y1, y2) in enumerate(zip(y_co, y_co[1:])):
    y_range[i * 2 + 1] = y2 - y1
    if y1 <= 0 <= y2:
        sy = i * 2 + 1


for a, b, c in vertical:
    y = y_comp[c] * 2
    for x in range(x_comp[a] * 2 + 1, x_comp[b] * 2 + 1, 2):
        grid[x][y] = 1

for d, e, f in horizontal:
    x = x_comp[d] * 2
    for y in range(y_comp[e] * 2 + 1, y_comp[f] * 2 + 1, 2):
        grid[x][y] = 1

ans = 0
dq = deque([(sx, sy)])
grid[sx][sy] = 1
diff = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans += x_range[sx] * y_range[sy]
while dq:
    x, y = dq.popleft()
    for dx, dy in diff:
        nx, ny = dx + x, dy + y
        if grid[nx][ny]:
            continue
        nx += dx;
        ny += dy
        if grid[nx][ny]:
            continue
        grid[nx][ny] = 1
        dq.append((nx, ny))
        ans += x_range[nx] * y_range[ny]
        if ans >= INF:
            print("INF")
            exit()

print(ans)

Solution (Python):


from heapq import heappush, heappop
import sys
import numpy as np

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline

INF = 10 ** 9 + 1



def dp(*x):  
    print(*x)


try:
    profile
except:
    def profile(f): return f


@profile
def main(N, M, data):
    ABC = data[:3 * N]
    DEF = data[3 * N:]
    A, B, C = [ABC[i::3] for i in range(3)]
    D, E, F = [DEF[i::3] for i in range(3)]

    xticks = np.unique(np.concatenate((E, F, C, np.array([-INF, 0, INF]))))
    yticks = np.unique(np.concatenate((A, B, D, np.array([-INF, 0, INF]))))
    width = xticks[1:] - xticks[:-1]
    height = yticks[1:] - yticks[:-1]

    
    A = np.searchsorted(yticks, A).astype(np.int16)
    B = np.searchsorted(yticks, B).astype(np.int16)
    C = np.searchsorted(xticks, C).astype(np.int16)
    D = np.searchsorted(yticks, D).astype(np.int16)
    E = np.searchsorted(xticks, E).astype(np.int16)
    F = np.searchsorted(xticks, F).astype(np.int16)

    GRAPH_WIDTH = len(xticks)
    GRAPH_HEIGHT = len(yticks)
    NUM_VERTEXES = GRAPH_HEIGHT * GRAPH_WIDTH

    ng_edges = np.zeros((NUM_VERTEXES, 4), dtype=np.uint8)
    direction = (-1, +1, -GRAPH_WIDTH, +GRAPH_WIDTH)

    
    for i in range(N):
        x = C[i]
        for y in range(A[i], B[i]):
            pos = y * GRAPH_WIDTH + x
            ng_edges[pos, 0] = 1  
            ng_edges[pos - 1, 1] = 1  
    A = B = C = 0

    
    for i in range(M):
        y = D[i]
        for x in range(E[i], F[i]):
            pos = y * GRAPH_WIDTH + x
            ng_edges[pos, 2] = 1
            ng_edges[pos - GRAPH_WIDTH, 3] = 1
    D = E = F = 0

    total_area = 0
    visited = np.zeros(NUM_VERTEXES)

    x = np.searchsorted(xticks, 0)
    y = np.searchsorted(yticks, 0)
    start = y * GRAPH_WIDTH + x
    to_visit = [start]

    while to_visit:
        pos = to_visit.pop()
        y, x = divmod(pos, GRAPH_WIDTH)
        if visited[pos]:
            continue
        if y == 0 or y == GRAPH_HEIGHT - 1 or x == 0 or x == GRAPH_WIDTH - 1:
            print("INF")
            break

        total_area += width[x] * height[y]
        visited[pos] = 1
        
        for i in range(4):
            if not ng_edges[pos][i]:
                next = pos + direction[i]
                if visited[next]:
                    continue
                to_visit.append(next)
    else:
        print(total_area)


if sys.argv[-1] == 'ONLINE_JUDGE' or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export(
        'main',
        "void(i4, i4, i4[:])"
    )(main)
    
    cc.compile()
    exit()
else:
    if sys.argv[-1] != '-p':
        
        
        from my_module import main  

    
    import numba
    N, M = map(int, input().split())
    data = np.int32(sys.stdin.read().split())
    main(N, M, data)

Solution (Python):


from heapq import heappush, heappop
import sys
import numpy as np

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline

INF = 10 ** 9 + 1



def dp(*x):  
    print(*x)


try:
    profile
except:
    def profile(f): return f


@profile
def main(N, M, data):
    ABC = data[:3 * N]
    DEF = data[3 * N:]
    A, B, C = [ABC[i::3] for i in range(3)]
    D, E, F = [DEF[i::3] for i in range(3)]

    xticks = np.unique(np.concatenate((E, F, C, np.array([-INF, 0, INF]))))
    yticks = np.unique(np.concatenate((A, B, D, np.array([-INF, 0, INF]))))
    width = xticks[1:] - xticks[:-1]
    height = yticks[1:] - yticks[:-1]

    
    A = np.searchsorted(yticks, A).astype(np.int16)
    B = np.searchsorted(yticks, B).astype(np.int16)
    C = np.searchsorted(xticks, C).astype(np.int16)
    D = np.searchsorted(yticks, D).astype(np.int16)
    E = np.searchsorted(xticks, E).astype(np.int16)
    F = np.searchsorted(xticks, F).astype(np.int16)

    GRAPH_WIDTH = len(xticks)
    GRAPH_HEIGHT = len(yticks)
    NUM_VERTEXES = GRAPH_HEIGHT * GRAPH_WIDTH


    if 0:
        direction = (-1, +1, -GRAPH_WIDTH, +GRAPH_WIDTH)

        ng_edges = np.zeros(NUM_VERTEXES, dtype=np.uint8)

        
        
        
        for i in range(N):
            x = C[i]
            for y in range(A[i], B[i]):
                pos = y * GRAPH_WIDTH + x
                
                
                ng_edges[pos] |= 0b0001  
                ng_edges[pos - 1] |= 0b0010  
        A = B = C = 0

        
        for i in range(M):
            y = D[i]
            for x in range(E[i], F[i]):
                pos = y * GRAPH_WIDTH + x
                ng_edges[pos] |= 0b0100
                ng_edges[pos - GRAPH_WIDTH] |= 0b1000
        D = E = F = 0
    else:
        direction = (1, -1, GRAPH_WIDTH, -GRAPH_WIDTH)

        def set_ng(A, B, C, D, E, F, H, W):
            ng = np.zeros((H * W, 4), np.bool_)

            for i in range(len(A)):
                for x in range(A[i], B[i]):
                    v = x * W + C[i]
                    ng[v][1] = 1
                    ng[v - 1][0] = 1

            for i in range(len(D)):
                for y in range(E[i], F[i]):
                    v = D[i] * W + y
                    ng[v][3] = 1
                    ng[v - W][2] = 1
            return ng

        ng_edges = set_ng(A, B, C, D, E, F, GRAPH_HEIGHT, GRAPH_WIDTH)
    total_area = 0
    visited = np.zeros(NUM_VERTEXES)
    

    x = np.searchsorted(xticks, 0)
    y = np.searchsorted(yticks, 0)
    start = y * GRAPH_WIDTH + x
    to_visit = [start]

    stack = np.empty(NUM_VERTEXES, np.int32)
    p = 0

    def push(x):
        nonlocal p
        stack[p] = x
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return stack[p]

    push(start)
    MASK = np.array([0b0001, 0b0010, 0b0100, 0b1000], dtype=np.uint8)
    
    while p:
        
        pos = pop()
        y, x = divmod(pos, GRAPH_WIDTH)
        if visited[pos]:
            continue
        if y == 0 or y == GRAPH_HEIGHT - 1 or x == 0 or x == GRAPH_WIDTH - 1:
            print("INF")
            break

        total_area += width[x] * height[y]
        
        visited[pos] = 1
        
        for i in range(4):
            
            if not ng_edges[pos][i]:
                next = pos + direction[i]
                if visited[next]:
                    continue
                
                push(next)
    else:
        print(total_area)


if sys.argv[-1] == 'ONLINE_JUDGE' or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export(
        'main',
        "void(i4, i4, i4[:])"
    )(main)
    
    cc.compile()
    exit()
else:
    if sys.argv[-1] != '-p':
        
        
        from my_module import main  

    
    import numba
    N, M = map(int, input().split())
    data = np.int32(sys.stdin.read().split())
    main(N, M, data)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=key, reverse=reverse)):
        zipped[xi] = i
        unzipped[i] = xi
    return zipped, unzipped


n, m = map(int, input().split())
line_v = [tuple(map(int, input().split())) for _ in range(n)]
line_h = [tuple(map(int, input().split())) for _ in range(m)]

INF = 10**9 + 10
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]

x_list = [-INF, 0, INF]
y_list = [-INF, 0, INF]
for x1, x2, y in line_v:
    
    x_list.append(x1)
    x_list.append(x2)
    y_list.append(y)
for x, y1, y2 in line_h:
    
    x_list.append(x)
    y_list.append(y1)
    y_list.append(y2)

x_zipped, x_unzipped = compress_coordinate(x_list)
y_zipped, y_unzipped = compress_coordinate(y_list)

nx = len(x_zipped)
ny = len(y_zipped)

v_ng = [[0] * (ny + 1) for _ in range(nx + 1)]
h_ng = [[0] * (ny + 1) for _ in range(nx + 1)]
for x1, x2, y in line_v:
    x1 = x_zipped[x1]
    x2 = x_zipped[x2]
    y = y_zipped[y]
    v_ng[x1][y] += 1
    v_ng[x2][y] -= 1
for x, y1, y2 in line_h:
    x = x_zipped[x]
    y1 = y_zipped[y1]
    y2 = y_zipped[y2]
    h_ng[x][y1] += 1
    h_ng[x][y2] -= 1

for x in range(nx):
    for y in range(ny):
        v_ng[x + 1][y] += v_ng[x][y]
        h_ng[x][y + 1] += h_ng[x][y]


grid = [[False] * (ny + 1) for _ in range(nx + 1)]
q = deque([(x_zipped[0], y_zipped[0])])
while q:
    x0, y0 = q.popleft()
    if grid[x0][y0]:
        continue
    grid[x0][y0] = True
    for k in range(4):
        x1 = x0 + dx[k]
        y1 = y0 + dy[k]
        if x1 < 0 or x1 >= nx or y1 < 0 or y1 >= ny:
            continue
        if grid[x1][y1]:
            continue

        if k == 0 and h_ng[x1][y1] == 0:
            
            q.append((x1, y1))
        elif k == 2 and h_ng[x0][y0] == 0:
            
            q.append((x1, y1))
        elif k == 1 and v_ng[x1][y1] == 0:
            
            q.append((x1, y1))
        elif k == 3 and v_ng[x0][y0] == 0:
            
            q.append((x1, y1))


if grid[0][0]:
    ans = 'INF'
else:
    ans = 0
    for x in range(nx):
        for y in range(ny):
            if grid[x][y]:
                ans += (x_unzipped[x + 1] -
                        x_unzipped[x]) * (y_unzipped[y + 1] - y_unzipped[y])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.par = [-1] * n

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])  
            return self.par[x]

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

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

    def size(self, x):
        return -self.par[self.root(x)]


def compress_coordinate(x: list, key=None, reverse=False):
    zipped = {}
    unzipped = {}
    for i, xi in enumerate(sorted(set(x), key=key, reverse=reverse)):
        zipped[xi] = i
        unzipped[i] = xi
    return zipped, unzipped


n, m = map(int, input().split())
line_v = [tuple(map(int, input().split())) for _ in range(n)]
line_h = [tuple(map(int, input().split())) for _ in range(m)]

INF = 10**9 + 10
x_list = [-INF, 0, INF]
y_list = [-INF, 0, INF]
for x1, x2, y in line_v:
    
    x_list.append(x1)
    x_list.append(x2)
    y_list.append(y)
for x, y1, y2 in line_h:
    
    x_list.append(x)
    y_list.append(y1)
    y_list.append(y2)

x_zipped, x_unzipped = compress_coordinate(x_list)
y_zipped, y_unzipped = compress_coordinate(y_list)

nx = len(x_zipped)
ny = len(y_zipped)

v_ng = [[0] * (ny + 1) for _ in range(nx + 1)]
h_ng = [[0] * (ny + 1) for _ in range(nx + 1)]
for x1, x2, y in line_v:
    x1 = x_zipped[x1]
    x2 = x_zipped[x2]
    y = y_zipped[y]
    v_ng[x1][y] += 1
    v_ng[x2][y] -= 1
for x, y1, y2 in line_h:
    x = x_zipped[x]
    y1 = y_zipped[y1]
    y2 = y_zipped[y2]
    h_ng[x][y1] += 1
    h_ng[x][y2] -= 1

for x in range(nx):
    for y in range(ny):
        v_ng[x + 1][y] += v_ng[x][y]
        h_ng[x][y + 1] += h_ng[x][y]


uf = UnionFind(nx * ny)
for x in range(nx):
    for y in range(ny):
        c0 = x * ny + y
        
        if y + 1 < ny and v_ng[x][y + 1] == 0:
            c1 = x * ny + (y + 1)
            uf.unite(c0, c1)
        if x + 1 < nx and h_ng[x + 1][y] == 0:
            c2 = (x + 1) * ny + y
            uf.unite(c0, c2)

c_start = x_zipped[0] * ny + y_zipped[0]
if uf.same(c_start, 0):
    ans = 'INF'
else:
    ans = 0
    for x in range(nx):
        for y in range(ny):
            if uf.same(c_start, x * ny + y):
                ans += (x_unzipped[x + 1] -
                        x_unzipped[x]) * (y_unzipped[y + 1] - y_unzipped[y])

print(ans)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from bisect import bisect_left, bisect_right

    INF = 10**18

    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    b = [list(map(int, input().split())) for i in range(m)]

    X = {-INF, INF}
    Y = {-INF, INF}
    for i in a:
        Y.add(i[2])
    for i in b:
        X.add(i[0])

    X = list(sorted(X))
    Y = list(sorted(Y))
    n = len(X) - 1
    m = len(Y) - 1
    wallx = [[False] * m for i in range(n)]
    wally = [[False] * m for i in range(n)]

    for x1, x2, y1 in a:
        x1 = bisect_left(X, x1)
        y1 = bisect_left(Y, y1)
        x2 = bisect_right(X, x2) - 1
        for i in range(x1, x2):
            wally[i][y1] = True

    for x1, y1, y2 in b:
        x1 = bisect_left(X, x1)
        y1 = bisect_left(Y, y1)
        y2 = bisect_right(Y, y2) - 1
        for i in range(y1, y2):
            wallx[x1][i] = True

    cow = [[False] * m for i in range(n)]
    cx = bisect_right(X, 0) - 1
    cy = bisect_right(Y, 0) - 1
    cow[cx][cy] = True
    q = [(cx, cy)]
    ans = 0

    while q:
        x, y = q.pop()
        if not x or not y:
            print("INF")
            sys.exit()
        ans += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        if x and not wallx[x][y] and not cow[x - 1][y]:
            cow[x - 1][y] = True
            q.append((x - 1, y))
        if y and not wally[x][y] and not cow[x][y - 1]:
            cow[x][y - 1] = True
            q.append((x, y - 1))
        if x + 1 < n and not wallx[x + 1][y] and not cow[x + 1][y]:
            cow[x + 1][y] = True
            q.append((x + 1, y))
        if y + 1 < m and not wally[x][y + 1] and not cow[x][y + 1]:
            cow[x][y + 1] = True
            q.append((x, y + 1))

    print(ans)

main()

Solution (Python):
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))
Y = sorted(set(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 = TY(d)
    e = bisect_left(X, e)
    f = bisect_right(X, f)-1
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    
    c = TX(c)
    a = bisect_left(Y, a)
    b = bisect_right(Y, b)-1
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X))
@njit
def dfs(i, j):
    s = [(i,j)]
    v = np.zeros((H,W))
    r = 0
    while s:
        i, j = s.pop()
        if not (0<=i<H and 0<=j<W):
            return -1
        if v[i,j]:
            continue
        v[i,j] = True
        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))
    return r
r = dfs(TY(0), TX(0))
print('INF' if r<0 else r)

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
INF = 10**20 

n, m = map(int, input().split())
xseen = set()
xseen.add(INF); xseen.add(-INF)
yseen = set()
yseen.add(INF); yseen.add(-INF)
a_b_c = []
for _ in range(n):
    a, b, c = map(int, input().split())
    xseen.add(a)
    xseen.add(b)
    yseen.add(c)
    a_b_c.append((a, b, c))
d_e_f = []
for _ in range(m):
    d, e, f = map(int, input().split())
    xseen.add(d)
    yseen.add(e)
    yseen.add(f)
    d_e_f.append((d, e, f))

xlen = len(xseen) * 2 - 1
ylen = len(yseen) * 2 - 1

xseen = sorted(list(xseen))
xcomp = {val:i for i, val in enumerate(xseen)}
yseen = sorted(list(yseen))
ycomp = {val:i for i, val in enumerate(yseen)}

field = [[0] * ylen for _ in range(xlen)]
x_range = [0] * xlen
y_range = [0] * ylen
x_range[0] = x_range[-1] = INF
y_range[0] = y_range[-1] = INF
for i, (x1, x2) in enumerate(zip(xseen, xseen[1:])):
    x_range[i * 2 + 1] = x2 - x1
    if x1 <= 0 <= x2:
        sx = i * 2 + 1
for i, (y1, y2) in enumerate(zip(yseen, yseen[1:])):
    y_range[i * 2 + 1] = y2 - y1
    if y1 <= 0 <= y2:
        sy = i * 2 + 1


for a, b, c in a_b_c:
    y = ycomp[c] * 2
    for x in range(xcomp[a] * 2 + 1, xcomp[b] * 2 + 1, 2):
        field[x][y] = 1 

for d, e, f in d_e_f:
    x = xcomp[d] * 2
    for y in range(ycomp[e] * 2 + 1, ycomp[f] * 2 + 1, 2):
        field[x][y] = 1 




diff = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

dq = deque([(sx, sy)])
field[sx][sy] = 1 
ans += x_range[sx] * y_range[sy]
while dq:
    x, y = dq.popleft()
    for dx, dy in diff:
        nx, ny = dx + x, dy + y
        if field[nx][ny]:
            continue
        nx += dx; ny += dy
        if field[nx][ny]:
            continue
        field[nx][ny] = 1 
        dq.append((nx, ny))
        ans += x_range[nx] * y_range[ny] 
        if ans >= INF:
            print("INF")
            exit()

print(ans)