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: Accepted

Solution code:
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={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    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
#sys.setrecursionlimit(10**7)
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: # O(N log N) for init, O(1) for query(l,r)
    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]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        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):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    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
    # calc
    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)]
#mpy=[[0]*(2*nx+2) for i in range(2*ny+2)]
 
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])
    #show((cx,cy),(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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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: # (a,c) to (b,c)
    hcoord.add(a)
    hcoord.add(b)
    wcoord.add(c)
for d,e,f in yoko: # (d,e) to (d,f)
    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: # (a,c) to (b,c)
    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: # (d,e) to (d,f)
    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 #枠外
        #4方向
        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))


#print(used)

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)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
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 = {}  # mapX[x] = (柵の座標xが小さい方から何番目か)
    mapY = {}  # mapX[y] = (柵の座標yが小さい方から何番目か)
    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
    #print("grid size: (h,w)=({},{})".format(h, w))

    # グリッド作成、柵部分は-1の値を入れたブロックとして扱う
    # また偶数グリッドは面積0として扱う
    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
    
    # BFSをする前に、スタート地点が柵単位で数えたためにもはや(0, 0)ではなくなっているため、
    # まずは開始位置を二分探索で求めておく
    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
    #print("start=({}, {})".format(start_x, start_y))
    #print(np.array(grid))

    # BFS
    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()
        #print("({}, {})".format(x, y))
        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(q)
        #print(np.array(grid))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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]

#for m in MAP:
#    print(*m)

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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, ix1):
        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, iy1):
        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)