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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: 
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    
    def query(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    
    def query_id(self,l,r):
        if r>self.size:r=self.size
        
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


show_flg=False
show_flg=True
ans=0
inf=1<<65
n,m=LI()
X=[0,inf,-inf]
Y=[0,inf,-inf]
V=[]
H=[]
for i in range(n):
    a,b,c=LI()
    V.append(((a,b),c))
    Y.append(c)
    X.append(a)
    X.append(b)
 
n+=2
V.append(((-inf,inf),inf))
V.append(((-inf,inf),-inf))
 
for i in range(m):
    a,b,c=LI()
    H.append((a,(b,c)))
    X.append(a)
    Y.append(b)
    Y.append(c)
 
m+=2
H.append((inf,(-inf,inf)))
H.append((-inf,(-inf,inf)))
 
 
X.sort()
xdc={}
c=1
for j in sorted(set(X)):
    xdc[c]=j
    c+=1
nx=c-1
 
Y.sort()
ydc={}
c=1
for j in sorted(set(Y)):
    ydc[c]=j
    c+=1
ny=c-1
 
xdcr=dict(zip(xdc.values(),xdc.keys()))
ydcr=dict(zip(ydc.values(),ydc.keys()))
 
mpy=[[0]*(nx+1+1) for i in range(ny+1+1)]
mpx=[[0]*(nx+1+1) for i in range(ny+1+1)]

 
for (a,b),c in V:
    mpx[ydcr[c]][xdcr[a]]+=1
    mpx[ydcr[c]][xdcr[b]]+=-1
for i in range(ny+1):
    for j in range(nx):
        mpx[i][j+1]+=mpx[i][j]
        
for d,(e,f) in H:
    mpy[ydcr[e]][xdcr[d]]+=1
    mpy[ydcr[f]][xdcr[d]]+=-1
for j in range(nx+1):
    for i in range(ny):
        mpy[i+1][j]+=mpy[i][j]


v=[[0]*(nx+1) for i in range(ny+1)]
q=deque()
q.append((xdcr[0],ydcr[0]))
v[ydcr[0]][xdcr[0]]=1


while q:
    cx,cy=q.popleft()
    px,py=cx,cy
    ans+=(xdc[px]-xdc[px+1])*(ydc[py]-ydc[py+1])
    
    for dx,dy in FourNb:
        nbx=cx+dx
        nby=cy+dy
        if (not 0<=nbx<nx) or (not 0<=nby<ny) or v[nby][nbx]==1:
            continue
        if dy!=0:
            if mpx[cy+(dy+1)//2][cx]==0:
                q.append((nbx,nby))
                v[nby][nbx]=1
        else:
            if mpy[cy][cx+(dx+1)//2]==0:
                q.append((nbx,nby))
                v[nby][nbx]=1
 
if ans>=inf:
    ans='INF'
print(ans)

Solution (Python):


import bisect
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
INF = 10**9 + 1
s_X = set([-INF, 0, INF])
s_Y = set([-INF, 0, INF])

def compress(s):
    ls = list(s)
    ls.sort()
    return {e: i for i, e in enumerate(ls)}

ABC = []
for i in range(N):
    A, B, C = map(int, readline().split())
    ABC.append((A, B, C))
    s_Y.add(C)

DEF = []
for i in range(M):
    D, E, F= map(int, readline().split())
    DEF.append((D, E, F))
    s_X.add(D)

mapX = compress(s_X)
mapY = compress(s_Y)
l_X = list(mapX.keys())
l_Y = list(mapY.keys())
maxX = len(mapX)*2
maxY = len(mapY)*2

W = [[0] * maxY for _ in range(maxX)]

for A, B, C in ABC:
    A = mapX[l_X[bisect.bisect_left(l_X, A)]]
    B = mapX[l_X[bisect.bisect_right(l_X, B)-1]]
    C = mapY[C]
    A *= 2
    B *= 2
    C *= 2
    for j in range(A, B+1):
        W[j][C] = 1

for D, E, F in DEF:
    D = mapX[D]
    E = mapY[l_Y[bisect.bisect_left(l_Y, E)]]
    F = mapY[l_Y[bisect.bisect_right(l_Y, F)-1]]
    D *= 2
    E *= 2
    F *= 2
    for j in range(E, F+1):
        W[D][j] = 1


q = []
q.append((mapX[0]*2, mapY[0]*2))
W[mapX[0]*2][mapY[0]*2] = 1
ans = 0
b_ans = True
while q:
    x, y = q.pop()
    if x == maxX or x == 0 or y == maxY or y == 0:
        b_ans = False
        break
    for (vx, vy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx = x + vx
        ny = y + vy
        if W[nx][ny] == 0:
            if nx%2==1 and ny%2==1:
                ex = l_X[(nx+1)//2] - l_X[(nx-1)//2]
                ey = l_Y[(ny+1)//2] - l_Y[(ny-1)//2]
                ans += ex * ey
                
            q.append((nx, ny))
            W[nx][ny] = 1

if b_ans == True:
    print(ans)
else:
    print('INF')

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

def main():
    n,m=map(int,input().split())
    X,Y=set(),set()
    H=[]
    V=[]
    for _ in range(n):
        a,b,c=map(int,input().split())
        X.add(a); X.add(b)
        Y.add(c)
        V.append((a,b,c))
    for _ in range(m):
        d,e,f=map(int,input().split())
        X.add(d)
        Y.add(e); Y.add(f)
        H.append((d,e,f))
    X=list(X); Y=list(Y)
    X.sort(); Y.sort()
    MapX={}; MapY={}
    for i,x in enumerate(X):
        MapX[x]=i
    for i,y in enumerate(Y):
        MapY[y]=i
    h=len(MapX)*2; w=len(MapY)*2
    Grid=[[0]*w for _ in range(h)]
    for a,b,c in V:
        a=MapX[a]*2; b=MapX[b]*2; c=MapY[c]*2
        for x in range(a,b+1):
            Grid[x][c]=1
    for d,e,f in H:
        d=MapX[d]*2; e=MapY[e]*2; f=MapY[f]*2
        for y in range(e,f+1):
            Grid[d][y]=1
    s_x=bisect_left(X,0)*2-1
    s_y=bisect_left(Y,0)*2-1
    if s_x<0 or s_y<0 or s_x>=h-1 or s_y>=w-1:
        return 'INF'
    Grid[s_x][s_y]=1
    D=[(1,0),(-1,0),(0,1),(0,-1)]
    ans=0
    q=deque([(s_x,s_y)])
    Grid[s_x][s_y]=1
    while q:
        x,y=q.popleft()
        ans+=(X[x//2+1]-X[x//2])*(Y[y//2+1]-Y[y//2])
        for dx,dy in D:
            half_x,half_y=x+dx,y+dy
            if Grid[half_x][half_y]!=0:
                continue
            to_x,to_y=half_x+dx,half_y+dy
            if to_x<0 or to_y<0 or to_x==h-1 or to_y==w-1:
                return 'INF'
            if Grid[to_x][to_y]!=0:
                continue
            Grid[to_x][to_y]=1
            q.append((to_x,to_y))
    return ans
    
if __name__=='__main__':
    print(main())

Solution (Python):
import sys
from bisect import bisect_left, bisect_right


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, sys.stdin.buffer.readline().split(sep=sep, maxsplit=maxsplit))

def input_2d_T(nrows : int, ncols : int, type=int, **kwargs):
	data = [[None] * nrows for _ in range(ncols)]
	for i in range(nrows):
		for j, v in enumerate(inputs(type)):
			data[j][i] = v
	return data

from collections import deque

N, M = inputs(int)
A, B, C = input_2d_T(N, 3)
D, E, F = input_2d_T(M, 3)
xs = sorted(set(C))
ys = sorted(set(D))

x_guard = [[False for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]
y_guard = [[False for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]

for a, b, c in zip(A, B, C):
	c = bisect_right(xs, c)
	a = bisect_left(ys, a) + 1
	b = bisect_right(ys, b)
	for i in range(a, b):
		x_guard[c][i] = True

for d, e, f in zip(D, E, F):
	d = bisect_right(ys, d)
	e = bisect_left(xs, e) + 1
	f = bisect_right(xs, f)
	for i in range(e, f):
		y_guard[i][d] = True

cow = (
	bisect_right(xs, 0),
	bisect_right(ys, 0)
)
nexts = deque([cow])
visited = [[0 for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]
visited[cow[0]][cow[1]] = True

area = 0

while nexts:
	xi, yi = nexts.popleft()
	
	if 0 < xi < len(xs) and 0 < yi < len(ys):
		area += (xs[xi] - xs[xi-1]) * (ys[yi] - ys[yi-1])
		if not visited[xi-1][yi] and not x_guard[xi][yi]:
			visited[xi-1][yi] = True
			nexts.append((xi-1, yi))
		if not visited[xi+1][yi] and not x_guard[xi+1][yi]:
			visited[xi+1][yi] = True
			nexts.append((xi+1, yi))
		if not visited[xi][yi-1] and not y_guard[xi][yi]:
			visited[xi][yi-1] = True
			nexts.append((xi, yi-1))
		if not visited[xi][yi+1] and not y_guard[xi][yi+1]:
			visited[xi][yi+1] = True
			nexts.append((xi, yi+1))
	else:
		area = 'INF'
		break

print(area)

Solution (Python):
import sys
from bisect import bisect_left, bisect_right


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, sys.stdin.buffer.readline().split(sep=sep, maxsplit=maxsplit))

def input_2d_T(nrows : int, ncols : int, type=int, **kwargs):
	data = [[None] * nrows for _ in range(ncols)]
	for i in range(nrows):
		for j, v in enumerate(inputs(type)):
			data[j][i] = v
	return data

from collections import deque

N, M = inputs(int)
A, B, C = input_2d_T(N, 3)
D, E, F = input_2d_T(M, 3)
xs = sorted(set(C))
ys = sorted(set(D))

x_guard = [[False for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]
y_guard = [[False for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]

for a, b, c in zip(A, B, C):
	c = bisect_right(xs, c)
	a = bisect_left(ys, a) + 1
	b = bisect_right(ys, b)
	for i in range(a, b):
		x_guard[c][i] = True

for d, e, f in zip(D, E, F):
	d = bisect_right(ys, d)
	e = bisect_left(xs, e) + 1
	f = bisect_right(xs, f)
	for i in range(e, f):
		y_guard[i][d] = True

cow = (
	bisect_right(xs, 0),
	bisect_right(ys, 0)
)
nexts = deque([cow])
visited = [[0 for _ in range(len(ys)+1)] for _ in range(len(xs)+1)]
visited[cow[0]][cow[1]] = True

area = 0

while nexts:
	xi, yi = nexts.popleft()
	
	if 0 < xi < len(xs) and 0 < yi < len(ys):
		area += (xs[xi] - xs[xi-1]) * (ys[yi] - ys[yi-1])
		if not visited[xi-1][yi] and not x_guard[xi][yi]:
			visited[xi-1][yi] = True
			nexts.append((xi-1, yi))
		if not visited[xi+1][yi] and not x_guard[xi+1][yi]:
			visited[xi+1][yi] = True
			nexts.append((xi+1, yi))
		if not visited[xi][yi-1] and not y_guard[xi][yi]:
			visited[xi][yi-1] = True
			nexts.append((xi, yi-1))
		if not visited[xi][yi+1] and not y_guard[xi][yi+1]:
			visited[xi][yi+1] = True
			nexts.append((xi, yi+1))
	else:
		area = 'INF'
		break

print(area)

Solution (Python):


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

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

INF = 10**9+5
hcoord = {-INF,0,INF}
wcoord = {-INF,0,INF}

for a,b,c in tate: 
    hcoord.add(a)
    hcoord.add(b)
    wcoord.add(c)
for d,e,f in yoko: 
    hcoord.add(d)
    wcoord.add(e)
    wcoord.add(f)

hcoord = list(sorted(hcoord))
wcoord = list(sorted(wcoord))

zaatu_x = {a:i for i,a in enumerate(sorted(hcoord))}
zaatu_y = {a:i for i,a in enumerate(sorted(wcoord))}

P = len(hcoord)
Q = len(wcoord)

ok_h = [[1 for y in range(Q-1)] for x in range(P-1)] 
ok_w = [[1 for y in range(Q-1)] for x in range(P-1)] 

for y in range(Q-1):
    ok_h[P-2][y] = 0
for x in range(P-1):
    ok_w[x][Q-2] = 0

for a,b,c in tate: 
    xa = zaatu_x[a]
    xb = zaatu_x[b]
    yc = zaatu_y[c]
    for i in range(xa,xb):
        ok_w[i][yc-1] = 0

for d,e,f in yoko: 
    ye = zaatu_y[e]
    yf = zaatu_y[f]
    xd = zaatu_x[d]
    for i in range(ye,yf):
        ok_h[xd-1][i] = 0

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

x0 = zaatu_x[0]
y0 = zaatu_y[0]
used = [[0 for y in range(Q-1)] for x in range(P-1)]

from collections import deque
q = deque([(x0,y0)])
used[x0][y0] = 1
while q:
    x,y = q.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or ny < 0 or nx >= P-1 or ny >= Q-1: continue 
        
        if i==0 and ok_h[x][y]==0: continue
        if i==2 and ok_h[nx][ny]==0: continue
        if i==1 and ok_w[x][y]==0: continue
        if i==3 and ok_w[nx][ny]==0: continue
        
        if used[nx][ny] == 0:
            used[nx][ny] = 1
            q.append((nx,ny))




if used[0][0] == 1:
    print("INF")
else:
    ans = 0
    for i in range(P-1):
        for j in range(Q-1):
            if used[i][j] == 1:
                ans += (hcoord[i+1]-hcoord[i])*(wcoord[j+1]-wcoord[j])
    print(ans)

Solution (Python):
import sys

from collections import deque
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

"""
    全く分からなかったので解説放送の写し。
        ・マス目に対してもBFSはできるのか！
        ・(NEW!)座標圧縮という技を使って計算量を削減できるのか
    あと壁に厚みを持たせて黒マスとして扱えばBFSがしやすくなる
"""

def main():
    N, M = map(int, input().split())
    X = set([])
    Y = set([])
    mapX = {}  
    mapY = {}  
    horizontal = []
    vertical = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        vertical.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        horizontal.append((d, e, f))
    X = list(X)
    Y =list(Y)
    X.sort()
    Y.sort()

    
    for i, x in enumerate(X):
        mapX[x] = i
    for i, y in enumerate(Y):
        mapY[y] = i

    
    
    h = len(mapX) * 2
    w = len(mapY) * 2
    

    
    
    grid = [[0] * w for _ in range(h)]
    for i in range(N):
        a = mapX[vertical[i][0]] * 2
        b = mapX[vertical[i][1]] * 2
        c = mapY[vertical[i][2]] * 2
        for x in range(a, b + 1): grid[x][c] = -1
    for j in range(M):
        d = mapX[horizontal[j][0]] * 2
        e = mapY[horizontal[j][1]] * 2
        f = mapY[horizontal[j][2]] * 2
        for y in range(e, f + 1): grid[d][y] = -1
    
    
    
    start_x = bisect_left(X, 0) * 2 - 1
    start_y = bisect_left(Y, 0) * 2 - 1
    if start_x < 0 or start_y < 0 or start_x >= h - 1 or start_y >= w - 1:
        print("INF")
        return
    grid[start_x][start_y] = 1
    
    

    
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    ans = 0
    q = deque([(start_x, start_y)])
    grid[start_x][start_y] = 1
    while q:
        x, y = q.popleft()
        
        ans += (X[x // 2 + 1] - X[x // 2]) * (Y[y // 2 + 1] - Y[y // 2])
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (nx == h - 2 and grid[nx][ny] == 0) or ny == w:
                print("INF")
                return
            if grid[nx][ny] != 0: continue
            nnx, nny = nx + dx[i], ny + dy[i]
            if nnx < 0 or nny < 0 or nnx == h - 1 or nny == w - 1:
                print("INF")
                return
            if grid[nnx][nny] != 0: continue  
            grid[nnx][nny] = 1
            q.append((nnx, nny))
        
        
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(N)]
DEF = [tuple(map(int,input().split())) for i in range(M)]
INF = float('inf')

def solve():
    xs = set([-INF,0,INF])
    ys = set([-INF,0,INF])
    for a,b,c in ABC:
        xs.add(a)
        xs.add(b)
        ys.add(c)
    for d,e,f in DEF:
        xs.add(d)
        ys.add(e)
        ys.add(f)
    xs = sorted(xs)
    ys = sorted(ys)
    xd = {x:i*2 for i,x in enumerate(xs)}
    yd = {y:i*2 for i,y in enumerate(ys)}

    W = len(xs)*2 - 1
    H = len(ys)*2 - 1
    S = [[0]*W for _ in range(H)]
    for y in (0,-1):
        for x in range(W):
            S[y][x] = 1
    for x in (0,-1):
        for y in range(H):
            S[y][x] = 1
    for a,b,c in ABC:
        for x in range(xd[a], xd[b]+1):
            S[yd[c]][x] = 1
    for d,e,f in DEF:
        for y in range(yd[e], yd[f]+1):
            S[y][xd[d]] = 1

    from collections import deque
    sx,sy = xd[0]+1, yd[0]+1
    q = deque([(sx,sy)])
    visited = [[0]*W for _ in range(H)]
    visited[sy][sx] = 1
    dxy = [(0,1),(1,0),(0,-1),(-1,0)]
    ans = (xs[sx//2+1] - xs[sx//2]) * (ys[sy//2+1] - ys[sy//2])
    while q:
        x,y = q.popleft()
        for dx,dy in dxy:
            nx,ny = x+dx,y+dy
            if S[ny][nx] == 1: continue
            nnx,nny = nx+dx,ny+dy
            if visited[nny][nnx]: continue
            visited[nny][nnx] = 1
            q.append((nnx,nny))
            tx,ty = (nx,nny) if nx%2 else (nnx,ny)
            assert tx%2 and ty%2
            w = xs[tx//2+1] - xs[tx//2]
            h = ys[ty//2+1] - ys[ty//2]
            ans += w*h
            if ans==INF:
                print('INF')
                exit()
    print(ans)
solve()

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

N,M=map(int,input().split())
TATE=[tuple(map(int,input().split())) for i in range(N)]
YOKO=[tuple(map(int,input().split())) for i in range(M)]


T=[-1<<63,(-1<<63)+1,0,1<<63,(1<<63)+1]
Y=[-1<<63,(-1<<63)+1,0,1<<63,(1<<63)+1]

for a,b,c in TATE:
    T.append(a)
    T.append(b)
    Y.append(c)

for d,e,f in YOKO:
    T.append(d)
    Y.append(e)
    Y.append(f)

T=sorted(set(T))
Y=sorted(set(Y))

BT=[T[0]]
BY=[Y[0]]

for i in range(1,len(T)):
    BT.append(T[i]-T[i-1])
    BT.append(T[i])

for i in range(1,len(Y)):
    BY.append(Y[i]-Y[i-1])
    BY.append(Y[i])

TDICT=dict()
YDICT=dict()

LBT=len(BT)
LBY=len(BY)

for i in range(LBT):
    if i%2==0:
        TDICT[BT[i]]=i

for i in range(LBY):
    if i%2==0:
        YDICT[BY[i]]=i

MAP=[[0]*(LBY+1) for i in range(LBT+1)]

for a,b,c in TATE:
    t0=TDICT[a]
    t1=TDICT[b]
    y=YDICT[c]

    MAP[t0][y]+=1
    MAP[t0][y+1]-=1
    MAP[t1+1][y]-=1
    MAP[t1+1][y+1]+=1

for d,e,f in YOKO:
    t=TDICT[d]
    y0=YDICT[e]
    y1=YDICT[f]

    MAP[t][y0]+=1
    MAP[t+1][y0]-=1
    MAP[t][y1+1]-=1
    MAP[t+1][y1+1]+=1

for i in range(LBT):
    for j in range(1,LBY):
        MAP[i][j]+=MAP[i][j-1]

for i in range(LBY):
    for j in range(1,LBT):
        MAP[j][i]+=MAP[j-1][i]




Q=deque()
x,y=TDICT[0],YDICT[0]
Q.append((x-1,y-1))
Q.append((x+1,y-1))
Q.append((x-1,y+1))
Q.append((x+1,y+1))
MAP[x-1][y-1]=MAP[x+1][y-1]=MAP[x-1][y+1]=MAP[x+1][y+1]=1
ANS=BT[x-1]*BY[y-1]+BT[x+1]*BY[y-1]+BT[x-1]*BY[y+1]+BT[x+1]*BY[y+1]

while Q:
    x,y=Q.pop()

    if MAP[x+1][y]==0 and MAP[x+2][y]==0:
        MAP[x+2][y]=1
        Q.append((x+2,y))
        ANS+=BT[x+2]*BY[y]

    if MAP[x-1][y]==0 and MAP[x-2][y]==0:
        MAP[x-2][y]=1
        Q.append((x-2,y))
        ANS+=BT[x-2]*BY[y]

    if MAP[x][y+1]==0 and MAP[x][y+2]==0:
        MAP[x][y+2]=1
        Q.append((x,y+2))
        ANS+=BT[x]*BY[y+2]

    if MAP[x][y-1]==0 and MAP[x][y-2]==0:
        MAP[x][y-2]=1
        Q.append((x,y-2))
        ANS+=BT[x]*BY[y-2]


    if ANS>=1<<62:
        print("INF")
        sys.exit()

print(ANS)

Solution (Python):
import sys
import numpy as np

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

INF = 10**9 + 1

def precompute(N, M, data):
    data = data.reshape(-1, 3)
    A, B, C = data[:N].T
    D, E, F = data[N:].T
    X = np.unique(np.concatenate([D, [0, -INF, INF]]))
    Y = np.unique(np.concatenate([C, [0, -INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B, 'right') - 1
    D = np.searchsorted(X, D)
    C = np.searchsorted(Y, C)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F, 'right') - 1
    return A, B, C, D, E, F, X, Y

def solve(A, B, C, D, E, F, X, Y):
    H, W = len(X), len(Y)
    N = H * W
    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    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 = set_ng(A, B, C, D, E, F, H, W)
    x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
    v0 = x0 * W + y0
    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

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    signature = '(i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1])'
    cc.export('solve', signature)(solve)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()

from my_module import solve

N, M = map(int, readline().split())
data = np.int64(read().split())

x = solve(*precompute(N, M, data))
if x == 0:
    print('INF')
else:
    print(x)

Solution (Python):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())

lx = [None] * n
ly = [None] * m
sx = set([-10**10, 0, 10**10])
sy = set([-10**10, 0, 10**10])
ix = 0
iy = 0
for i in range(n):
    t = tuple(map(int, input().split()))
    lx[i] = t
    sx.add(t[0])
    sx.add(t[1])
    sy.add(t[2])

for i in range(m):
    t = tuple(map(int, input().split()))
    ly[i] = t
    sx.add(t[0])
    sy.add(t[1])
    sy.add(t[2])

xs = list(sx)
ys = list(sy)
xs.sort(); ys.sort()

wx = len(xs)*2
wy = len(ys)*2
bs = [[1]*wy for _ in range(wx)]
import bisect
for i, (x0, x1, y) in enumerate(lx):
    ix0 = bisect.bisect_left(xs, x0)*2
    ix1 = bisect.bisect_left(xs, x1)*2
    iy = bisect.bisect_left(ys, y)*2
    for ii in range(ix0+1, ix1, 2):
        bs[ii][iy] = -1
for i, (x, y0, y1) in enumerate(ly):
    ix = bisect.bisect_left(xs, x)*2
    iy0 = bisect.bisect_left(ys, y0)*2
    iy1 = bisect.bisect_left(ys, y1)*2
    for ii in range(iy0+1, iy1, 2):
        bs[ix][ii] = -1

xx = bisect.bisect_left(xs, 0)*2+1
yy = bisect.bisect_left(ys, 0)*2+1
s = [(xx,yy)]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
ans = 0
end = False
while s:
    ix,iy = s.pop()
    for x, y in zip(dx,dy):
        ixx = ix + x
        iyy = iy + y
        if bs[ixx][iyy]!=1:
            continue
        ixx += x
        iyy += y
        if bs[ixx][iyy]!=1:
            continue
        if ixx<0 or ixx>=wx-1 or iyy<0 or iyy>=wy-1:
            print("INF")
            s = []
            end = True
            break
        bs[ixx][iyy] = 2
        ans += (xs[ixx//2+1] - xs[ixx//2]) * (ys[iyy//2+1] - ys[iyy//2])
        s.append((ixx, iyy))

if not end:
    print(ans)