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
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)

Submission status: Accepted

Solution code:
import sys

# from itertools import chain, accumulate

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]

# banned_up = list(chain.from_iterable(map(accumulate, banned_up_ij)))
# banned_down = list(chain.from_iterable(map(accumulate, banned_down_ij)))
# banned_left = list(chain.from_iterable(zip(*map(accumulate, banned_left_ij))))
# banned_right = list(chain.from_iterable(zip(*map(accumulate, banned_right_ij))))

# for i in range(col):
#     print(walls[i * row:(i + 1) * row])

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

# for i in range(col):
#     print(enable[i * row:(i + 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)
# for i in range(col):
#     print(enable[i * row:(i + 1) * row])


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)

Submission status: Accepted

Solution code:
import sys
# from itertools import chain, accumulate

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]

# banned_up = list(chain.from_iterable(map(accumulate, banned_up_ij)))
# banned_down = list(chain.from_iterable(map(accumulate, banned_down_ij)))
# banned_left = list(chain.from_iterable(zip(*map(accumulate, banned_left_ij))))
# banned_right = list(chain.from_iterable(zip(*map(accumulate, banned_right_ij))))

# for i in range(col):
#     print(walls[i * row:(i + 1) * row])

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

# for i in range(col):
#     print(enable[i * row:(i + 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)
# for i in range(col):
#     print(enable[i * row:(i + 1) * row])


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)

Submission status: Accepted

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

ABC = []
for _ in range(N):
    # (A,C)-(B,C)
    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)-(D,F)
    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)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): 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): #merge(x,y): 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 #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

# coding: utf-8
# Your code here!
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: # (a,c) to (b,c)
    xcoord.append(a)
    xcoord.append(b)
    ycoord.append(c)
for d,e,f in tate: # (d,e) to (d,f)
    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


# (i,j) から右 or 上 に行けるか？
ok_up = [[0]*P for _ in range(Q)]
ok_ri = [[0]*Q for _ in range(P)]

for a,b,c in yoko: # (a,c) to (b,c)
    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: # (d,e) to (d,f)
    ye = zaatu_y[e]
    yf = zaatu_y[f]
    xd = zaatu_x[d]
    ok_ri[xd-1][ye] += 1
    ok_ri[xd-1][yf] -= 1

#print(ok_up)
#print(ok_ri)
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]))

#print(*[i for i in ok_ri],sep="\n")

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]

#print([UF.root(i) for i in range((P-1)*(Q-1))])
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)

#print(xcoord)
#print(ycoord)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

#print (tlis,ylis,nowi,nowj)

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]

    #print (ni,nj,up,do,le,ri)

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

    #up
    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)

Submission status: Accepted

Solution code:
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()  # ignore trailing spaces

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)):
            # print(i, j, i+1, j)
            unite(i*H+j, (i+1)*H+j)
        elif i < len(xs) and verb[i][j-1] == 0:
            # print(i, j, i+1, j)
            unite(i*H+j, (i+1)*H+j)
        if j < len(ys) and i in (0, len(xs)):
            # print(i, j, i, j+1)
            unite(i*H+j, i*H+j+1)
        elif j < len(ys) and horb[j][i-1] == 0:
            # print(i, j, i, j+1)
            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)

Submission status: Runtime Error

Solution code:
# ABC168F .(Single Dot)
g=lambda:map(int,input().split())

N,M=g()

sortx=[]
sorty=[]

y_line=[]
x_line=[]

for _ in [0]*N:
    a,b,c=g()
    sortx.append(a)
    sortx.append(b)
    sorty.append(c)
    y_line.append((a,b,c))
    
for _ in [0]*M:
    d,e,f=g()
    sortx.append(d)
    sorty.append(e)
    sorty.append(f)
    x_line.append((d,e,f))
    
from bisect import bisect_left as bl
    
sortx=sorted(list(set(sortx)))
sorty=sorted(list(set(sorty)))

zip_x_line=[]
zip_y_line=[]
for a,b,c in y_line:
    a=bl(sortx,a)
    b=bl(sortx,b)
    c=bl(sorty,c)
    zip_y_line.append((a,b,c))
    
for d,e,f in x_line:
    d=bl(sortx,d)
    e=bl(sorty,e)
    f=bl(sorty,f)
    zip_x_line.append((d,e,f))
    
W=len(sortx)*2-1
H=len(sorty)*2-1
    
G=[1]*W*H+[0]*(W+1)

def make_graph(i,j,s=0):
    G[i+j*W]=s

for a,b,c in zip_y_line:
    for i in range(2*a,2*b+1):
        make_graph(i,2*c)
        
for d,e,f in zip_x_line:
    for j in range(2*e,2*f+1):
        make_graph(2*d,j)
        
def get_score(i,j):
    if i*j==0 or i==W or j==H:
        return float('inf')
    elif i==1 or j==1 or i==W-1 or j==H-1:
        return 0
    elif i%2 and j%2:
        dx=sortx[(i+1)//2]-sortx[(i-1)//2]
        dy=sorty[(j+1)//2]-sorty[(j-1)//2]
        return dx*dy
    else:
        return 0
        
# for i in range(H):
#     print(*G[W*i:W*i+H],sep='')

dic=[(-1,0),(1,0),(0,1),(0,-1)]    
    
def search(i,j):
    res=[]
    for dx,dy in dic:
        if G[(i+dx)+(j+dy)*W]==1:
            res.append((i+dx,j+dy))
    return res
    
stack=[(2*bl(sortx,0)-1,2*bl(sorty,0)-1)]
res=0
while stack:
    x,y=stack.pop()
    if G[x+y*W]!=1:
        continue
    res+=get_score(x,y)
    stack+=search(x,y)
    make_graph(x,y)
print(res if res<float('inf') else 'INF')

Submission status: Runtime Error

Solution code:
# ABC168F .(Single Dot)
g=lambda:map(int,input().split())

N,M=g()

sortx=[]
sorty=[]

y_line=[]
x_line=[]

for _ in [0]*N:
    a,b,c=g()
    sortx.append(a)
    sortx.append(b)
    sorty.append(c)
    y_line.append((a,b,c))
    
for _ in [0]*M:
    d,e,f=g()
    sortx.append(d)
    sorty.append(e)
    sorty.append(f)
    x_line.append((d,e,f))
    
from bisect import bisect_left as bl
    
sortx=sorted(list(set(sortx)))
sorty=sorted(list(set(sorty)))

zip_x_line=[]
zip_y_line=[]
for a,b,c in y_line:
    a=bl(sortx,a)
    b=bl(sortx,b)
    c=bl(sorty,c)
    zip_y_line.append((a,b,c))
    
for d,e,f in x_line:
    d=bl(sortx,d)
    e=bl(sorty,e)
    f=bl(sorty,f)
    zip_x_line.append((d,e,f))
    
W=len(sortx)*2-1
H=len(sorty)*2-1
    
G=['o']*W*H+['x']*10

def make_graph(i,j,s='x'):
    G[i+j*W]=s

for a,b,c in zip_y_line:
    for i in range(2*a,2*b+1):
        make_graph(i,2*c)
        
for d,e,f in zip_x_line:
    for j in range(2*e,2*f+1):
        make_graph(2*d,j)
        
def get_score(i,j):
    if i*j==0 or i>=W-1 or j>=H-1:
        return float('inf')
    elif i%2 and j%2:
        dx=sortx[(i+1)//2]-sortx[(i-1)//2]
        dy=sorty[(j+1)//2]-sorty[(j-1)//2]
        return dx*dy
    else:
        return 0
        
# for i in range(H):
#     print(*G[W*i:W*i+H],sep='')
    
def search(i,j):
    res=[]
    dic=[(-1,0),(1,0),(0,1),(0,-1)]
    for dx,dy in dic:
        if G[(i+dx)+(j+dy)*W]=='o':
            res.append((i+dx,j+dy))
    return res
    
stack=[(2*bl(sortx,0)-1,2*bl(sorty,0)-1)]
res=0
while stack:
    x,y=stack.pop()
    if G[x+y*W]!='o':
        continue
    res+=get_score(x,y)
    stack+=search(x,y)
    make_graph(x,y)
print(res if res<float('inf') else 'INF')

Submission status: Runtime Error

Solution code:
g=lambda:map(int,input().split())

N,M=g()

sortx=[]
sorty=[]

y_line=[]
x_line=[]

for _ in [0]*N:
    a,b,c=g()
    sortx.append(a)
    sortx.append(b)
    sorty.append(c)
    y_line.append((a,b,c))
    
for _ in [0]*M:
    d,e,f=g()
    sortx.append(d)
    sorty.append(e)
    sorty.append(f)
    x_line.append((d,e,f))
    
from bisect import bisect_left as bl
    
sortx=sorted(list(set(sortx)))
sorty=sorted(list(set(sorty)))

zip_x_line=[]
zip_y_line=[]
for a,b,c in y_line:
    a=bl(sortx,a)
    b=bl(sortx,b)
    c=bl(sorty,c)
    zip_y_line.append((a,b,c))
    
for d,e,f in x_line:
    d=bl(sortx,d)
    e=bl(sorty,e)
    f=bl(sorty,f)
    zip_x_line.append((d,e,f))
    
W=len(sortx)*2-1
H=len(sorty)*2-1
    
G=['o']*W*H

def make_graph(i,j,s='x'):
    G[i+j*W]=s

for a,b,c in zip_y_line:
    for i in range(2*a,2*b+1):
        make_graph(i,2*c)
        
for d,e,f in zip_x_line:
    for j in range(2*e,2*f+1):
        make_graph(2*d,j)
        
def get_score(i,j):
    if i*j==0 or i>=W-1 or j>=H-1:
        return float('inf')
    elif i%2 and j%2:
        dx=sortx[(i+1)//2]-sortx[(i-1)//2]
        dy=sorty[(j+1)//2]-sorty[(j-1)//2]
        return dx*dy
    else:
        return 0
        
# for i in range(H):
#     print(*G[W*i:W*i+H],sep='')
    
def search(i,j):
    res=[]
    dic=[(-1,0),(1,0),(0,1),(0,-1)]
    for dx,dy in dic:
        if G[(i+dx)+(j+dy)*W]=='o':
            res.append((i+dx,j+dy))
    return res
    
stack=[(2*bl(sortx,0)-1,2*bl(sorty,0)-1)]
res=0
while stack:
    x,y=stack.pop()
    if G[x+y*W]!='o':
        continue
    res+=get_score(x,y)
    stack+=search(x,y)
    make_graph(x,y,str(get_score(x,y)))
print(res if res<float('inf') else 'INF')

Submission status: Runtime Error

Solution code:
def main():
n,m=map(int,input().split())
  def hashh(x1,y1,x2,y2):
      if x1>x2:
          x1,y1,x2,y2=x2,y2,x1,y1
      if x1==x2 and y1>y2:
          x1,y1,x2,y2=x2,y2,x1,y1
      return x1*27000000000+y1*9000000+x2*3000+y2
  abc_l=[list(map(int,input().split()))for _ in range(n)]
  def_l=[list(map(int,input().split()))for _ in range(m)]
  x=[0]
  y=[0]
  for a,b,c in abc_l:
      x.append(a)
      x.append(b)
      y.append(c)
  for d,e,f in def_l:
      x.append(d)
      y.append(e)
      y.append(f)
  x=sorted(list(set(x)))
  y=sorted(list(set(y)))
  h=len(x)+1
  w=len(y)+1
  dicx={}
  dicy={}
  for i in range(len(x)):dicx[x[i]]=i
  for i in range(len(y)):dicy[y[i]]=i
  grid=[[0]*w for _ in range(h)]
  dont=set()
  for a,b,c in abc_l:
      for i in range(dicx[a],dicx[b]):
          dont.add(hashh(i+1,dicy[c],i+1,dicy[c]+1))
  for d,e,f in def_l:
      for j in range(dicy[e],dicy[f]):
          dont.add(hashh(dicx[d],j+1,dicx[d]+1,j+1))
  if dicx[0]==0 or dicx[0]==h-1 or dicy[0]==0 or dicy[0]==w-1:
      exit(print("INF"))
  stack=[(dicx[0],dicy[0])]
  grid[dicx[0]][dicy[0]]=1
  ans=0
  for sx,sy in stack:
      ans+=(x[sx]-x[sx-1])*(y[sy]-y[sy-1])
      for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
          tx=sx+dx
          ty=sy+dy
          if grid[tx][ty]:continue
          if hashh(sx,sy,tx,ty) in dont:continue
          if tx==0 or tx==h-1 or ty==0 or ty==w-1:
              exit(print("INF"))
          grid[tx][ty]=1
          stack.append((tx,ty))
  print(ans)
main()