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):
n,m,*l = map(int, open(0).read().split())
l=iter(l)
l=list(zip(l,l,l))
l1=l[:n]
l2=l[-m:]

V=set([float('inf'),-float('inf')])
H=set([float('inf'),-float('inf')])

for a,b,c in l1:
    V.add(c)
    H.add(a)
    H.add(b)
for c,a,b in l2:
    H.add(c)
    V.add(a)
    V.add(b)

V=sorted(list(V))
H=sorted(list(H))
Vdic={}
Hdic={}
for i,v in enumerate(V):
    Vdic[v]=i
for i,h in enumerate(H):
    Hdic[h]=i

checkv=[[0]*3001 for i in range(3001)]
checkh=[[0]*3001 for i in range(3001)]
check=[[0]*3001 for i in range(3001)]

for a,b,c in l1:
    c=Vdic[c]
    for i in range(Hdic[a],Hdic[b]):
        checkh[c][i]=1
for c,a,b in l2:
    c=Hdic[c]
    for i in range(Vdic[a],Vdic[b]):
        checkv[i][c]=1

from bisect import bisect_left
pv=bisect_left(V,0)-1
ph=bisect_left(H,0)-1

ans=0

stack=[(pv,ph)]
check[pv][ph]=1

while stack:
    v,h=stack.pop()
    ans+=(V[v+1]-V[v])*(H[h+1]-H[h])
    if h!=0 and checkv[v][h]==0 and check[v][h-1]==0:
        stack.append((v,h-1))
        check[v][h-1]=1
    if h!=len(H)-2 and checkv[v][h+1]==0 and check[v][h+1]==0:
        stack.append((v,h+1))
        check[v][h+1]=1
    if v!=0 and checkh[v][h]==0 and check[v-1][h]==0:
        stack.append((v-1,h))
        check[v-1][h]=1
    if v!=len(V)-2 and checkh[v+1][h]==0 and check[v+1][h]==0:
        stack.append((v+1,h))
        check[v+1][h]=1

print("INF" if ans==float('inf') else ans)

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 10**9 + 1

N, M = map(int, readline().split())
data = np.array(read().split(), np.int64)
A = data[::3]
B = data[1::3]
C = data[2::3]

D = A[N:]
E = B[N:]
F = C[N:]
A = A[:N]
B = B[:N]
C = C[:N]

X = np.unique(np.concatenate([A, B, D, [0, -INF, INF]]))
Y = np.unique(np.concatenate([C, E, F, [0, -INF, INF]]))
DX = X[1:] - X[:-1]
DY = Y[1:] - Y[:-1]

A = np.searchsorted(X, A)
B = np.searchsorted(X, B)
C = np.searchsorted(Y, C)
D = np.searchsorted(X, D)
E = np.searchsorted(Y, E)
F = np.searchsorted(Y, F)

H, W = len(X), len(Y)
N = H * W

@njit
def set_ng(A, B, C, D, E, F):
    ng = np.zeros((N, 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 = set_ng(A, B, C, D, E, F)

x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
v0 = x0 * W + y0

@njit
def solve():
    visited = np.zeros(N, np.bool_)
    visited[v0] = 1
    stack = np.empty(N, np.int32)
    p = 0
    ret = 0

    def area(x):
        x, y = divmod(x, W)
        return DX[x] * DY[y]

    def push(x):
        nonlocal p, ret
        stack[p] = x
        visited[x] = 1
        ret += area(x)
        p += 1

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

    push(v0)
    move = (1, -1, W, -W)
    while p:
        v = pop()
        for i in range(4):
            if ng[v][i]:
                continue
            w = v + move[i]
            if visited[w]:
                continue
            x, y = divmod(w, W)
            if x == 0 or x == H - 1 or y == 0 or y == W - 1:
                return 0
            push(w)
    return ret

x = solve()
if x == 0:
    print('INF')
else:
    print(x)

Solution (Python):

import sys
import bisect
from collections import deque
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

M = 3*10**9+1
M2 = (M-10**9)**2
n,m = LI()
p = LIR(n)
q = LIR(m)
fx = set([-M,0,M])
fy = set([-M,0,M])
for i in range(n):
    p[i][0] <<= 1
    p[i][1] <<= 1
    p[i][2] <<= 1
    a,b,c = p[i]
    fy.add(a)
    fy.add(b)
    fy.add(b+1)
    fx.add(c)
    fx.add(c+1)

for i in range(m):
    q[i][0] <<= 1
    q[i][1] <<= 1
    q[i][2] <<= 1
    d,e,f = q[i]
    fy.add(d)
    fy.add(d+1)
    fx.add(e)
    fx.add(f)
    fx.add(f+1)
fy = list(fy)
fx = list(fx)
fy.sort()
fx.sort()
s = [0]*len(fx)*len(fy)
for a,b,c in p:
    ai = bisect.bisect_left(fy,a)
    bi = bisect.bisect_left(fy,b)
    ci = bisect.bisect_left(fx,c)
    ka = ai*len(fx)
    kb = (bi+1)*len(fx)
    s[ka+ci] += 1
    s[kb+ci] -= 1
    s[ka+ci+1] -= 1
    s[kb+ci+1] += 1
for d,e,f in q:
    di = bisect.bisect_left(fy,d)
    ei = bisect.bisect_left(fx,e)
    fi = bisect.bisect_left(fx,f)
    kd = di*len(fx)
    kdd = kd+len(fx)
    s[kd+ei] += 1
    s[kd+fi+1] -= 1
    s[kdd+ei] -= 1
    s[kdd+fi+1] += 1
for i in range(len(fy)):
    k = i*len(fx)
    for j in range(len(fx)-1):
        ind = k+j
        s[ind+1] += s[ind]
for i in range(len(fy)-1):
    k = i*len(fx)
    for j in range(len(fx)-1):
        ind = k+j
        s[ind+len(fx)] += s[ind]
sx = bisect.bisect_left(fx,0)
sy = bisect.bisect_left(fy,0)
nh,nw = len(fy)-1,len(fx)-1
for i in range(nw-1):
    fx[i+1] >>= 1
    fx[i] = fx[i+1]-fx[i]
for i in range(nh-1):
    fy[i+1] >>= 1
    fy[i] = fy[i+1]-fy[i]
ans = fx[sx]*fy[sy]
q = deque()
q.append((sy,sx))
f = [1]*nh*nw
f[sy*nw+sx] = 0
d = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
    y,x = q.popleft()
    for dy,dx in d:
        ny,nx = y+dy,x+dx
        if 0 <= ny < nh and 0 <= nx < nw:
            ind = ny*nw+nx
            if f[ind] and not s[ind+ny]:
                if ny < 1 or nx < 1 or ny+1 >= nh or nx+1 >= nw:
                    print("INF")
                    quit()
                ans += fx[nx]*fy[ny]
                f[ind] = 0
                q.append((ny,nx))
print(ans)

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

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N, M = map(int, readline().split())
INF = 10**9+7

Wp = [tuple(map(int, readline().split())) for _ in range(N)]
Hp = [tuple(map(int, readline().split())) for _ in range(M)]


epx = [0, INF, -INF]
epy = [0, INF, -INF]

for X, st, en in Hp:
    epx.append(X)
    epy.append(st)
    epy.append(en)

for st, en, Y in Wp:
    epy.append(Y)
    epx.append(st)
    epx.append(en)
    

Elx, Cex = compress(epx)
Ely, Cey = compress(epy)
Lx = len(Elx)
Ly = len(Ely)


UD = [[0]*(Lx+1) for _ in range(Ly+1)]
LR = [[0]*(Lx+1) for _ in range(Ly+1)]
for X, st, en in Hp:
    LR[Cey[st]][Cex[X]] += 1
    LR[Cey[en]][Cex[X]] -= 1
for st, en, Y in Wp:
    UD[Cey[Y]][Cex[st]] += 1
    UD[Cey[Y]][Cex[en]] -= 1

for x in range(1, Lx):
    for y in range(Ly):
        UD[y][x] += UD[y][x-1]

for y in range(1, Ly):
    for x in range(Lx):
        LR[y][x] += LR[y-1][x]
      
ed = set()
for i in range(Lx):
    ed.add((i, 0))
    ed.add((i, Ly-1))
for j in range(Ly):
    ed.add((0, j))
    ed.add((Lx-1, j))

geta = Ly
st = Cex[0]*geta + Cey[0]
stack = [st]
used = [False]*(Lx*Ly)
used[st] = True
ans = 'INF'
area = 0
while stack:
    vx, vy = divmod(stack.pop(), geta)
    if (vx, vy) in ed:
        break
    area += (Elx[vx+1]-Elx[vx])*(Ely[vy+1]-Ely[vy])
    if not UD[vy+1][vx] and not used[vx*geta+vy+1]:
        used[vx*geta+vy+1] = True
        stack.append(vx*geta+vy+1)
    if not UD[vy][vx] and not used[vx*geta+vy-1]:
        used[vx*geta+vy-1] = True
        stack.append(vx*geta+vy-1)
    if not LR[vy][vx+1] and not used[(vx+1)*geta+vy]:
        used[(vx+1)*geta+vy] = True
        stack.append((vx+1)*geta+vy)
    if not LR[vy][vx] and not used[(vx-1)*geta+vy]:
        used[(vx-1)*geta+vy] = True
        stack.append((vx-1)*geta+vy)

else:
    ans = area
print(ans)

Solution (Python):
import sys



n, m, *abcdef = map(int, sys.stdin.buffer.read().split())

ver_lines = []
hor_lines = []
x_list = set()
y_list = set()
n3 = n * 3
for a, b, c in zip(abcdef[0:n3:3], abcdef[1:n3:3], abcdef[2:n3:3]):
    y_list.add(a)
    y_list.add(b)
    x_list.add(c)
    ver_lines.append((a, b, c))

for d, e, f in zip(abcdef[n3 + 0::3], abcdef[n3 + 1::3], abcdef[n3 + 2::3]):
    y_list.add(d)
    x_list.add(e)
    x_list.add(f)
    hor_lines.append((d, e, f))
x_list.add(0)
y_list.add(0)

x_list = sorted(x_list)
y_list = sorted(y_list)
x_dict = {x: i for i, x in enumerate(x_list, start=1)}
y_dict = {y: i for i, y in enumerate(y_list, start=1)}
row_real = len(x_list)
col_real = len(y_list)
row = row_real + 2
col = col_real + 2

banned_up = [0] * (row * col)
banned_down = [0] * (row * col)
banned_left = [0] * (row * col)
banned_right = [0] * (row * col)
for a, b, c in ver_lines:
    if a > b:
        a, b = b, a
    ai = y_dict[a] * row
    bi = y_dict[b] * row
    j = x_dict[c]
    banned_left[ai + j] += 1
    banned_left[bi + j] -= 1
    banned_right[ai + j - 1] += 1
    banned_right[bi + j - 1] -= 1
for d, e, f in hor_lines:
    if e > f:
        e, f = f, e
    ri = y_dict[d] * row
    ej = x_dict[e]
    fj = x_dict[f]
    banned_up[ri + ej] += 1
    banned_up[ri + fj] -= 1
    banned_down[ri - row + ej] += 1
    banned_down[ri - row + fj] -= 1

for i in range(1, col):
    ri0 = row * (i - 1)
    ri1 = row * i
    for j in range(1, row):
        banned_up[ri1 + j] += banned_up[ri1 + j - 1]
        banned_down[ri1 + j] += banned_down[ri1 + j - 1]
        banned_left[ri1 + j] += banned_left[ri0 + j]
        banned_right[ri1 + j] += banned_right[ri0 + j]









s = row * y_dict[0] + x_dict[0]
enable = [-1] * row + ([-1] + [0] * (row - 2) + [-1]) * (col - 2) + [-1] * row




q = [s]
moves = [(-row, banned_up), (-1, banned_left), (1, banned_right), (row, banned_down)]
while q:
    c = q.pop()
    if enable[c] == 1:
        continue
    elif enable[c] == -1:
        print('INF')
        exit()
    enable[c] = 1
    for dc, banned in moves:
        if banned[c]:
            continue
        nc = c + dc
        if enable[nc] == 1:
            continue
        q.append(nc)




ans = 0
for i in range(col):
    ri = i * row
    for j in range(row):
        if enable[ri + j] != 1:
            continue
        t = y_list[i - 1]
        b = y_list[i]
        l = x_list[j - 1]
        r = x_list[j]
        ans += (b - t) * (r - l)
print(ans)

Solution (Python):
import sys


n, m, *abcdef = map(int, sys.stdin.buffer.read().split())

ver_lines = []
hor_lines = []
x_list = set()
y_list = set()
n3 = n * 3
for a, b, c in zip(abcdef[0:n3:3], abcdef[1:n3:3], abcdef[2:n3:3]):
    y_list.add(a)
    y_list.add(b)
    x_list.add(c)
    ver_lines.append((a, b, c))

for d, e, f in zip(abcdef[n3 + 0::3], abcdef[n3 + 1::3], abcdef[n3 + 2::3]):
    y_list.add(d)
    x_list.add(e)
    x_list.add(f)
    hor_lines.append((d, e, f))
x_list.add(0)
y_list.add(0)

x_list = sorted(x_list)
y_list = sorted(y_list)
x_dict = {x: i for i, x in enumerate(x_list, start=1)}
y_dict = {y: i for i, y in enumerate(y_list, start=1)}
row_real = len(x_list)
col_real = len(y_list)
row = row_real + 2
col = col_real + 2
banned_up_ij = [[0] * row for _ in range(col)]
banned_down_ij = [[0] * row for _ in range(col)]
banned_left_ij = [[0] * col for _ in range(row)]
banned_right_ij = [[0] * col for _ in range(row)]
for a, b, c in ver_lines:
    if a > b:
        a, b = b, a
    ai = y_dict[a]
    bi = y_dict[b]
    j = x_dict[c]
    banned_left_ij[j][ai] += 1
    banned_left_ij[j][bi] -= 1
    banned_right_ij[j - 1][ai] += 1
    banned_right_ij[j - 1][bi] -= 1
for d, e, f in hor_lines:
    if e > f:
        e, f = f, e
    i = y_dict[d]
    ej = x_dict[e]
    fj = x_dict[f]
    banned_up_ij[i][ej] += 1
    banned_up_ij[i][fj] -= 1
    banned_down_ij[i - 1][ej] += 1
    banned_down_ij[i - 1][fj] -= 1

banned_up = [0] * (row * col)
banned_down = [0] * (row * col)
banned_left = [0] * (row * col)
banned_right = [0] * (row * col)
for i in range(col):
    ru = banned_up_ij[i]
    rd = banned_down_ij[i]
    ri = row * i
    banned_up[ri] = ru[0]
    banned_down[ri] = rd[0]
    for j in range(1, row):
        banned_up[ri + j] = banned_up[ri + j - 1] + ru[j]
        banned_down[ri + j] = banned_down[ri + j - 1] + rd[j]
for j in range(row):
    rl = banned_left_ij[j]
    rr = banned_right_ij[j]
    banned_left[j] = rl[0]
    banned_right[j] = rr[0]
    for i in range(1, col):
        ri0 = (i - 1) * row
        ri1 = i * row
        banned_left[ri1 + j] = banned_left[ri0 + j] + rl[i]
        banned_right[ri1 + j] = banned_right[ri0 + j] + rr[i]









s = row * y_dict[0] + x_dict[0]
enable = [-1] * row + ([-1] + [0] * (row - 2) + [-1]) * (col - 2) + [-1] * row




q = [s]
moves = [(-row, banned_up), (-1, banned_left), (1, banned_right), (row, banned_down)]
while q:
    c = q.pop()
    if enable[c] == 1:
        continue
    elif enable[c] == -1:
        print('INF')
        exit()
    enable[c] = 1
    for dc, banned in moves:
        if banned[c]:
            continue
        nc = c + dc
        if enable[nc] == 1:
            continue
        q.append(nc)




ans = 0
for i in range(col):
    ri = i * row
    for j in range(row):
        if enable[ri + j] != 1:
            continue
        t = y_list[i - 1]
        b = y_list[i]
        l = x_list[j - 1]
        r = x_list[j]
        ans += (b - t) * (r - l)
print(ans)

Solution (Python):
N, M = map(int, input().split())
X = set()
Y = set()

ABC = []
for _ in range(N):
    
    A, B, C = map(int, input().split())
    X.add(A)
    X.add(B)
    Y.add(C)
    ABC.append((A,B,C))

DEF = []
for _ in range(M):
    
    D, E, F = map(int, input().split())
    X.add(D)
    Y.add(E)
    Y.add(F)
    DEF.append((D,E,F))

XL = sorted(list(X))
YL = sorted(list(Y))

XD = {k:v for v,k in enumerate(XL)}
YD = {k:v for v,k in enumerate(YL)}

nX = len(XL)+1
nY = len(YL)+1

S = [[False]*nY for _ in range(nX)]
T = [[15]*nY for _ in range(nX)]

for a, b, c in ABC:
    xbgn = XD[a]+1
    xend = XD[b]
    yu   = YD[c]
    yd   = yu+1
    for x in range(xbgn, xend+1):
        T[x][yu]-=4
        T[x][yd]-=8

for d, e, f in DEF:
    ybgn = YD[e]+1
    yend = YD[f]
    xl   = XD[d]
    xr   = xl+1
    for y in range(ybgn, yend+1):
        T[xl][y]-=1
        T[xr][y]-=2

x0 = 0
while XL[x0]<0 and x0<nX-2: x0+=1
y0 = 0
while YL[y0]<0 and y0<nY-2: y0+=1

queue = [(x0, y0)]

ans = 0
while queue:
    queue_new = []
    for qx, qy in queue:
        if S[qx][qy]: continue
        S[qx][qy]=True
        if qx==0 or qy==0 or qx==nX-1 or qy==nY-1:
            print('INF')
            exit()

        ans += (XL[qx]-XL[qx-1])*(YL[qy]-YL[qy-1])

        t = T[qx][qy]
        if t&1: queue_new.append((qx+1,qy))
        if t&2: queue_new.append((qx-1,qy))
        if t&4: queue_new.append((qx,qy+1))
        if t&8: queue_new.append((qx,qy-1))

    queue = queue_new


print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]



import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m = map(int, readline().split())
yoko = [list(map(int, readline().split())) for _ in range(n)]
tate = [list(map(int, readline().split())) for _ in range(m)]

INF = 10**9+5
xcoord = [-INF,0,INF]
ycoord = [-INF,0,INF]

for a,b,c in yoko: 
    xcoord.append(a)
    xcoord.append(b)
    ycoord.append(c)
for d,e,f in tate: 
    ycoord.append(e)
    ycoord.append(f)
    xcoord.append(d)

xcoord = list(sorted(set(xcoord)))
ycoord = list(sorted(set(ycoord)))

zaatu_x = {a:i for i,a in enumerate(xcoord)}
zaatu_y = {a:i for i,a in enumerate(ycoord)}

P = len(xcoord)
Q = len(ycoord)
QQ=Q-1



ok_up = [[0]*P for _ in range(Q)]
ok_ri = [[0]*Q for _ in range(P)]

for a,b,c in yoko: 
    xa = zaatu_x[a]
    xb = zaatu_x[b]
    yc = zaatu_y[c]
    ok_up[yc-1][xa] += 1
    ok_up[yc-1][xb] -= 1


for d,e,f in tate: 
    ye = zaatu_y[e]
    yf = zaatu_y[f]
    xd = zaatu_x[d]
    ok_ri[xd-1][ye] += 1
    ok_ri[xd-1][yf] -= 1



from itertools import accumulate
for i in range(Q):
    ok_up[i] = list(accumulate(ok_up[i]))
for j in range(P):
    ok_ri[j] = list(accumulate(ok_ri[j]))



UF = UnionFind((P-1)*QQ)
for i in range(P-1):
    for j in range(Q-2):
        v = i*QQ+j
        if ok_up[j][i]==0: UF.merge(v,v+1)
for i in range(P-2):
    for j in range(Q-1):
        v = i*QQ+j
        if ok_ri[i][j]==0: UF.merge(v,v+QQ)
        
x0 = zaatu_x[0]
y0 = zaatu_y[0]


r = UF.root(x0*QQ+y0) 
if UF.root(0) == r:
    print("INF")
else:
    ans = sum((xcoord[i+1]-xcoord[i])*(ycoord[j+1]-ycoord[j]) for i in range(P-1) for j in range(Q-1) if UF.root(i*QQ+j) == r)
    print(ans)

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 10**9 + 1

N, M = map(int, readline().split())
data = np.array(read().split(), np.int64)
A = data[::3]
B = data[1::3]
C = data[2::3]

D = A[N:]
E = B[N:]
F = C[N:]
A = A[:N]
B = B[:N]
C = C[:N]

X = np.unique(np.concatenate([A, B, D, [0, -INF, INF]]))
Y = np.unique(np.concatenate([C, E, F, [0, -INF, INF]]))
DX = X[1:] - X[:-1]
DY = Y[1:] - Y[:-1]

A = np.searchsorted(X, A)
B = np.searchsorted(X, B)
C = np.searchsorted(Y, C)
D = np.searchsorted(X, D)
E = np.searchsorted(Y, E)
F = np.searchsorted(Y, F)

H, W = len(X), len(Y)
N = H * W

@njit
def set_ng(A, B, C, D, E, F):
    p = 0
    head = np.full(N, -1, np.int32)
    ng = np.empty(4 * N, np.int32)
    nxt = np.empty(4 * N, np.int32)

    def add(v, w):
        nonlocal p
        nxt[p] = head[v]
        head[v] = p
        ng[p] = w
        p += 1

    for i in range(len(A)):
        a, b, c = A[i], B[i], C[i]
        for x in range(a, b):
            v = x * W + c
            add(v, v - 1)
            add(v - 1, v)
    for i in range(len(D)):
        d, e, f = D[i], E[i], F[i]
        for y in range(e, f):
            v = d * W + y
            add(v, v - W)
            add(v - W, v)
    return head, ng[:p], nxt[:p]

head, ng, nxt = set_ng(A, B, C, D, E, F)

@njit
def next_w(head, ng, nxt, v):
    p = head[v]
    V = [v - W, v + W, v - 1, v + 1]
    while p != -1:
        if ng[p] in V:
            V.remove(ng[p])
        p = nxt[p]
    return V

x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
v0 = x0 * W + y0

@njit
def solve():
    visited = np.zeros(N, np.bool_)
    visited[v0] = 1
    stack = np.empty(N, np.int32)
    p = 0
    ret = 0

    def area(x):
        x, y = divmod(x, W)
        return DX[x] * DY[y]

    def push(x):
        nonlocal p, ret
        stack[p] = x
        visited[x] = 1
        ret += area(x)
        p += 1

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

    push(v0)
    while p:
        v = pop()
        for w in next_w(head, ng, nxt, v):
            if visited[w]:
                continue
            x, y = divmod(w, W)
            if x == 0 or x == H - 1 or y == 0 or y == W - 1:
                return 0
            push(w)
    return ret

x = solve()
if x == 0:
    print('INF')
else:
    print(x)

Solution (Python):
N, M = map(int, input().split())
A, B, X, Y = [], [], {-10**9-1, 0, 10**9+1}, {-10**9-1, 0, 10**9+1}
for _ in range(N):
    a, b, c = map(int, input().split())
    A.append((a, b, c))
    X.add(a)
    X.add(b)
    Y.add(c)
for _ in range(M):
    d, e, f = map(int, input().split())
    B.append((d, e, f))
    X.add(d)
    Y.add(e)
    Y.add(f)
X = sorted(list(X))
Y = sorted(list(Y))
S = {a:i for i, a in enumerate(X)}
T = {a:i for i, a in enumerate(Y)}
H = len(X)
W = len(Y)
Z1 = [[0] * W for _ in range(H)]
Z2 = [[0] * W for _ in range(H)]

for a, b, c in A:
    a, b, c = S[a], S[b], T[c]
    for i in range(a, b):
        Z1[i][c] = 1
for d, e, f in B:
    d, e, f = S[d], T[e], T[f]
    for j in range(e, f):
        Z2[d][j] = 1

s = S[0] * W + T[0]

from collections import deque

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    ans = (X[S[0]+1] - X[S[0]]) * (Y[T[0]+1] - Y[T[0]])
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        dd = []
        if Z1[i][j] == 0: dd.append((0, -1))
        if Z1[i][j+1] == 0: dd.append((0, 1))
        if Z2[i][j] == 0: dd.append((-1, 0))
        if Z2[i+1][j] == 0: dd.append((1, 0))
        for di, dj in dd:
            ni, nj = i + di, j + dj
            if not (0 < ni < H - 1 and 0 < nj < W - 1):
                print("INF")
                exit()
            y = ni * W + nj
            if D[y] == -1:
                D[y] = D[x] + 1
                ans += (X[ni+1] - X[ni]) * (Y[nj+1] - Y[nj])
                Q.append(y)
    return ans
bfs = BFS(s)
print(bfs)

Solution (Python):

N,M = map(int,input().split())

ts = {}
tlis = []

for i in range(N):
    B,C,A = map(int,input().split())

    if A not in ts:
        tlis.append(A)
        ts[A] = []
    ts[A].append([B,C])

ys = {}
ylis = []

for i in range(M):
    A,B,C = map(int,input().split())

    if A not in ys:
        ylis.append(A)
        ys[A] = []
    ys[A].append([B,C])

tlis.sort()
ylis.sort()

import bisect

nowi = bisect.bisect_right(tlis,0) - 1
nowj = bisect.bisect_right(ylis,0) - 1



for i in ts:
    
    ts[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ts[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ts[i] = new

for i in ys:
    
    ys[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ys[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ys[i] = new


from collections import deque

q = deque([ [nowi,nowj] ])
import sys
ans = 0

end = {}
end[(nowi,nowj)] = 1

if len(tlis) < 2 or len(ylis) < 2:
    print ("INF")
    sys.exit()

while len(q) > 0:

    ni,nj = q.popleft()

    
    if ni == -1 or nj == -1 or ni == len(tlis)-1 or nj == len(ylis)-1:
        print ("INF")
        sys.exit()

    up = ylis[nj]
    do = ylis[nj + 1]
    le = tlis[ni]
    ri = tlis[ni + 1]

    

    ans += (do-up) * (ri-le)

    
    flag = True

    nex = (ni,nj-1)

    if nex not in end:
        for tmp in ys[up]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni,nj+1)
    flag = True

    if nex not in end:
        for tmp in ys[do]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni-1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[le]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni+1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[ri]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

print (ans)

Solution (Python):
N, M = map(int, input().split())
X = set()
Y = set()

ABC = []
for _ in range(N):
    
    A, B, C = map(int, input().split())
    X.add(A)
    X.add(B)
    Y.add(C)
    ABC.append((A,B,C))

DEF = []
for _ in range(M):
    
    D, E, F = map(int, input().split())
    X.add(D)
    Y.add(E)
    Y.add(F)
    DEF.append((D,E,F))

XL = sorted(list(X))
YL = sorted(list(Y))

XD = {k:v for v,k in enumerate(XL)}
YD = {k:v for v,k in enumerate(YL)}

nX = len(XL)+1
nY = len(YL)+1

S = [[False]*nY for _ in range(nX)]
T = [[15]*nY for _ in range(nX)]

for a, b, c in ABC:
    xbgn = XD[a]+1
    xend = XD[b]
    yu   = YD[c]
    yd   = yu+1
    for x in range(xbgn, xend+1):
        T[x][yu]-=4
        T[x][yd]-=8

for d, e, f in DEF:
    ybgn = YD[e]+1
    yend = YD[f]
    xl   = XD[d]
    xr   = xl+1
    for y in range(ybgn, yend+1):
        T[xl][y]-=1
        T[xr][y]-=2

x0 = 0
while XL[x0]<0 and x0<nX-2: x0+=1
y0 = 0
while YL[y0]<0 and y0<nY-2: y0+=1

queue = [(x0, y0)]

ans = 0
while queue:
    queue_new = []
    for qx, qy in queue:
        if S[qx][qy]: continue
        S[qx][qy]=True
        if qx==0 or qy==0 or qx==nX-1 or qy==nY-1:
            print('INF')
            exit()

        ans += (XL[qx]-XL[qx-1])*(YL[qy]-YL[qy-1])

        t = T[qx][qy]
        if t&1: queue_new.append((qx+1,qy))
        if t&2: queue_new.append((qx-1,qy))
        if t&4: queue_new.append((qx,qy+1))
        if t&8: queue_new.append((qx,qy-1))

    queue = queue_new


print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m = na()

hors = []
for i in range(n):
    hors.append(na())
vers = []
for j in range(m):
    vers.append(na())

xs = set()
for hor in hors:
    xs.add(hor[0])
    xs.add(hor[1])
for ver in vers:
    xs.add(ver[0])

xs = list(xs)
xs.sort()


ys = set()
for hor in hors:
    ys.add(hor[2])
for ver in vers:
    ys.add(ver[1])
    ys.add(ver[2])

ys = list(ys)
ys.sort()

upper = [-1] * ((len(xs)+1)*(len(ys)+1))
H = len(ys)+1

def root(x):
    if upper[x] < 0:
        return x
    else:
        upper[x] = root(upper[x])
        return upper[x]

def equiv(x, y):
    return root(x) == root(y)

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        if upper[y] < upper[x]:
            x, y = y, x
        upper[x] += upper[y]
        upper[y] = x
    return x == y

import bisect
horb = [[0] * (len(xs)+1) for _ in range(len(ys))]
for hor in hors:
    y = bisect.bisect_left(ys, hor[2])
    horb[y][bisect.bisect_left(xs, hor[0])] += 1
    horb[y][bisect.bisect_left(xs, hor[1])] -= 1
for i in range(len(ys)):
    for j in range(1, len(xs)+1):
        horb[i][j] += horb[i][j-1]

verb = [[0] * (len(ys)+1) for _ in range(len(xs))]
for ver in vers:
    x = bisect.bisect_left(xs, ver[0])
    verb[x][bisect.bisect_left(ys, ver[1])] += 1
    verb[x][bisect.bisect_left(ys, ver[2])] -= 1
for i in range(len(xs)):
    for j in range(1, len(ys)+1):
        verb[i][j] += verb[i][j-1]

for i in range(len(xs)+1):
    for j in range(len(ys)+1):
        if i < len(xs) and j in (0, len(ys)):
            
            unite(i*H+j, (i+1)*H+j)
        elif i < len(xs) and verb[i][j-1] == 0:
            
            unite(i*H+j, (i+1)*H+j)
        if j < len(ys) and i in (0, len(xs)):
            
            unite(i*H+j, i*H+j+1)
        elif j < len(ys) and horb[j][i-1] == 0:
            
            unite(i*H+j, i*H+j+1)

ox = bisect.bisect_left(xs, 0)
oy = bisect.bisect_left(ys, 0)

if equiv(ox*H+oy, 0):
    print("INF")
else:
    S = 0
    for i in range(len(xs) + 1):
        for j in range(len(ys) + 1):
            if equiv(i*H+j, ox*H+oy):
                S += (xs[i] - xs[i-1]) * (ys[j] - ys[j-1])
    print(S)