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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**20 

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

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

xseen = list(xseen)
xseen.sort()
xcomp = dict()
yseen = list(yseen)
yseen.sort()
ycomp = dict()
for i, item in enumerate(xseen):
    xcomp[item] = i
for i, item in enumerate(yseen):
    ycomp[item] = i

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

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

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

# for line in field:
#     print("".join([item for item in line]))

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**20 

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

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

xseen = list(xseen)
xseen.sort()
xcomp = dict()
yseen = list(yseen)
yseen.sort()
ycomp = dict()
for i, item in enumerate(xseen):
    xcomp[item] = i
for i, item in enumerate(yseen):
    ycomp[item] = i

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

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

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

# for line in field:
#     print("".join([item for item in line]))

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

st = [(sx, sy)]
field[sx][sy] = True 
ans += x_range[sx] * y_range[sy]
while st:
    x, y = st.pop()
    for dx, dy in diff:
        nx, ny = dx + x, dy + y
        if not field[nx][ny]:
            field[nx][ny] = True 
            st.append((nx, ny))
            if (nx) % 2 == 1 and (ny) % 2 == 1: 
                ans += x_range[nx] * y_range[ny]
                if ans >= INF:
                    print("INF")
                    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**20 

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

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

xseen = list(xseen)
xseen.sort()
xcomp = dict()
yseen = list(yseen)
yseen.sort()
ycomp = dict()
for i, item in enumerate(xseen):
    xcomp[item] = i
for i, item in enumerate(yseen):
    ycomp[item] = i

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

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

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

# for line in field:
#     print("".join([item for item in line]))

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

st = []
field[sx][sy] = True 
st.append((sx, sy))
ans += x_range[sx] * y_range[sy]
while st:
    x, y = st.pop()
    for dx, dy in diff:
        if not field[x + dx][y + dy]:
            field[x + dx][y + dy] = True 
            st.append((x + dx, y + dy))
            if (x + dx) % 2 == 1 and (y + dy) % 2 == 1: 
                ans += x_range[x + dx] * y_range[y + dy]
                if ans >= INF:
                    print("INF")
                    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**20 

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

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

xseen = list(xseen)
xseen.sort()
xcomp = dict()
yseen = list(yseen)
yseen.sort()
ycomp = dict()
for i, item in enumerate(xseen):
    xcomp[item] = i
for i, item in enumerate(yseen):
    ycomp[item] = i

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

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

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

# for line in field:
#     print("".join([item for item in line]))

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

st = []
field[sx][sy] = "#"
st.append((sx, sy))
ans += x_range[sx] * y_range[sy]
while st:
    x, y = st.pop()
    for dx, dy in diff:
        if field[x + dx][y + dy] == ".":
            field[x + dx][y + dy] = "#"
            st.append((x + dx, y + dy))
            ans += x_range[x + dx] * y_range[y + dy]
            if ans >= INF:
                print("INF")
                exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X))
@njit
def f(i,j):
    s = [(i,j)]
    v = set()
    r = 0
    while s:
        i, j = s.pop()
        if (i,j) in v:
            continue
        v.add((i,j))
        if not (0<=i<H and 0<=j<W):
            print('INF')
            break
        r += S[i][j]
        if U[i][j]:
            s.append((i-1,j))
        if U[i+1][j]:
            s.append((i+1,j))
        if L[i][j]:
            s.append((i,j-1))
        if L[i][j+1]:
            s.append((i,j+1))
    else:
        print(r)
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
f(i,j)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m
 
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())
 
x_items = list(set(a+b+d+[0]))
y_items = list(set(c+e+f+[0]))
 
x_items.sort()
y_items.sort()
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1
 
 
h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2
 
for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2
 
q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
flug1 = True
ans = 0
while q:
    x, y = q.popleft()
    grid[x][y] = 1
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            flug1 = False
            break
        if ny < 0 or ny >= w:
            flug1 = False
            break
        if grid[x+dx[i]][y+dy[i]] == 0:
            q.append((x+dx[i],y+dy[i]))
    if flug1 == False:
        ans = "INF"
        break
 
flug2 = True
if flug1 == True:
    for x in range(h):
        for y in range(w):
            if grid[x][y] != 1:
                continue
            if x == 0 or x == h-1 or y == 0 or y == w-1:
                flug2 = False
                break
            if x%2 == 0 or y%2 == 0:
                continue
            xx = x_items[x//2+1] - x_items[x//2]
            yy = y_items[y//2+1] - y_items[y//2]
            ans = ans + xx*yy
        if flug2 == False:
            ans = "INF"
            break
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())

x_items = list(set(a+b+d+[0]))
y_items = list(set(c+e+f+[0]))

x_items.sort()
y_items.sort()
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1


h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2

for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2

q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
flug1 = True
ans = 0
while q:
    x, y = q.popleft()
    grid[x][y] = 1
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            flug1 = False
            break
        if ny < 0 or ny >= w:
            flug1 = False
            break
        if grid[x+dx[i]][y+dy[i]] == 0:
            q.append((x+dx[i],y+dy[i]))
    if flug1 == False:
        ans = "INF"
        break

flug2 = True
if flug1 == True:
    for x in range(h):
        for y in range(w):
            if grid[x][y] != 1:
                continue
            if x == 0 or x == h-1 or y == 0 or y == w-1:
                flug2 = False
                break
            if x%2 == 0 or y%2 == 0:
                continue
            xx = x_items[x//2+1] - x_items[x//2]
            yy = y_items[y//2+1] - y_items[y//2]
            ans = ans + xx*yy
        if flug2 == False:
            ans = "INF"
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
a = [0]*n
b = [0]*n
c = [0]*n
d = [0]*m
e = [0]*m
f = [0]*m

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
for i in range(m):
    d[i], e[i], f[i] = map(int, input().split())

x_items = sorted(set(a+b+d+[0]))
y_items = sorted(set(c+e+f+[0]))
xi = 0
yi = 0
x_map = {}
y_map = {}
for i in x_items:
    x_map[i] = xi
    xi = xi + 1
for i in y_items:
    y_map[i] = yi
    yi = yi + 1


h = len(x_map)*2
w = len(y_map)*2
grid = [[0] * w for i in range(h)]
for i in range(n):
    a_comp = x_map[a[i]]*2
    b_comp = x_map[b[i]]*2
    c_comp = y_map[c[i]]*2
    for x in range(a_comp,b_comp+1):
        grid[x][c_comp] = 2

for i in range(m):
    d_comp = x_map[d[i]]*2
    e_comp = y_map[e[i]]*2
    f_comp = y_map[f[i]]*2
    for y in range(e_comp,f_comp+1):
        grid[d_comp][y] = 2

q = deque()
xo = x_map[0]*2
yo = y_map[0]*2
dx = (-1, 0, 1, 0)
dy = (0,-1,0,1)
q.append((xo,yo))
while q:
    x, y = q.popleft()
    grid[x][y] = 1
    for i in range(4): 
        nx = x+dx[i]
        ny = y+dy[i]
        if nx < 0 or nx >= h:
            continue
        if ny < 0 or ny >= w:
            continue
        if grid[x+dx[i]][y+dy[i]] == 0:
            q.append((x+dx[i],y+dy[i]))

ans = 0
flug = True
for x in range(h):
    for y in range(w):
        if grid[x][y] != 1:
            continue
        if x == 0 or x == h-1 or y == 0 or y == w-1:
            flug = False
            break
        if x%2 == 0 or y%2 == 0:
            continue
        xx = x_items[x//2+1] - x_items[x//2]
        yy = y_items[y//2+1] - y_items[y//2]
        ans = ans + xx*yy
    
    if flug == False:
        ans = "INF"
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = [[True]*W for _ in range(H+1)]
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    for i in range(e, f):
        U[d][i] = False 
L = [[True]*(W+1) for _ in range(H)]
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    for i in range(a, b):
        L[i][c] = False
i = TY(0)
j = TX(0)
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += (Y[i+1]-Y[i])*(X[j+1]-X[j])
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X)) 
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
s = [(i,j)]
v = set()
r = 0
while s:
    i, j = s.pop()
    if (i,j) in v:
        continue
    v.add((i,j))
    if not (0<=i<H and 0<=j<W):
        print('INF')
        break
    r += S[i][j]
    if U[i][j]:
        s.append((i-1,j))
    if U[i+1][j]:
        s.append((i+1,j))
    if L[i][j]:
        s.append((i,j-1))
    if L[i][j+1]:
        s.append((i,j+1))
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
NS = []
X_num = set()
EW = []
Y_num = set()

INF = 10 ** 36

X_num.add(INF)
X_num.add(0)
X_num.add(-INF)
Y_num.add(INF)
Y_num.add(0)
Y_num.add(-INF)

cant_inc_x = [[0] * 3300 for i in range(3300)]
cant_inc_y = [[0] * 3300 for i in range(3300)]

for i in range(n):
    a, b, c = map(int, input().split())
    X_num.add(a)
    X_num.add(b)
    Y_num.add(c)
    NS.append((a,b,c))

for i in range(m):
    d, e, f = map(int, input().split())
    X_num.add(d)
    Y_num.add(e)
    Y_num.add(f)
    EW.append((d,e,f))

X_dict = {}
Y_dict = {}

X_num = sorted(list(X_num))
Y_num = sorted(list(Y_num))


for xp, x in enumerate(X_num):
    X_dict[x] = xp
    xp += 1

for yp, y in enumerate(Y_num):
    Y_dict[y] = yp
    yp += 1

#(a,b) (a,c)
for a, b, c in NS:
    a = X_dict[a]
    b = X_dict[b]
    c = Y_dict[c]
    cant_inc_y[a][c-1] += 1
    cant_inc_y[b][c-1] -= 1
    

#(d,e) (d,f)
for d, e, f in EW:
    d = X_dict[d]
    e = Y_dict[e]
    f = Y_dict[f]
    cant_inc_x[d-1][e] += 1
    cant_inc_x[d-1][f] -= 1

for i in range(3003):
    for j in range(3003):
        if(j):cant_inc_x[i][j] += cant_inc_x[i][j-1]
        if(i):cant_inc_y[i][j] += cant_inc_y[i-1][j]

from collections import deque
q = deque()
q.append((X_dict[0], Y_dict[0]))
done = [[False] * 3003 for _ in range(3003)]

ans = 0


while len(q) != 0:
    (nowx, nowy) = q.popleft()
    if nowx < 0 or nowy < 0 or nowx+1 >= len(X_num) or nowy+1 >= len(Y_num):
        continue
    if done[nowx][nowy]:continue
    done[nowx][nowy] = True
    ans += (X_num[nowx+1] - X_num[nowx]) * (Y_num[nowy+1] - Y_num[nowy])
    if cant_inc_x[nowx][nowy] == 0:q.append((nowx+1, nowy))
    if cant_inc_y[nowx][nowy] == 0:q.append((nowx, nowy+1))
    if nowx > 0 and cant_inc_x[nowx-1][nowy] == 0:q.append((nowx-1, nowy))
    if nowy > 0 and cant_inc_y[nowx][nowy-1] == 0:q.append((nowx, nowy-1))

if ans > INF:
    print("INF")
else:    
    print(ans)

Submission status: Time Limit Exceeded

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]))
"""
for i in range(Q):
    for j in range(P-1):
        ok_up[i][j+1] += ok_up[i][j]

for j in range(P):
    for i in range(Q-1):
        ok_ri[j][i+1] += ok_ri[j][i]

#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: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

def main():
    N, M = map(int, input().split())

    LV = []
    LH = []

    mp_X = defaultdict(int)
    mp_Y = defaultdict(int)

    mp_X[0] = 0
    mp_Y[0] = 0

    for _ in range(N):
        a,b,c = map(int, input().split())
        mp_X[a] = mp_X[b] = mp_Y[c] = 0
        LH.append((a,b,c))

    for _ in range(M):
        d,e,f = map(int, input().split())
        mp_X[d] = mp_Y[e] = mp_Y[f] = 0
        LV.append((e,f,d))

    sX = []
    sY = []

    for i, k in enumerate(sorted(mp_X)):
        mp_X[k] = i
        sX.append(k)
    for i, k in enumerate(sorted(mp_Y)):
        mp_Y[k] = i
        sY.append(k)

    sizeX = len(mp_X) * 2 - 1
    sizeY = len(mp_Y) * 2 - 1

    d = [[0 for _ in range(sizeY)] for _ in range(sizeX)]

    for x1,x2,y in LH:
        for x in range(mp_X[x1]*2, mp_X[x2]*2+1):
            d[x][mp_Y[y]*2] = -1

    for y1,y2,x in LV:
        for y in range(mp_Y[y1]*2, mp_Y[y2]*2+1):
            d[mp_X[x]*2][y] = -1

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

    q = []
    cx, cy = mp_X[0]*2, mp_Y[0]*2
    d[cx][cy] = 1
    q.insert(0, (cx,cy))
    while q:
        cx, cy = q.pop()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < sizeX and 0 <= ny < sizeY:
                if abs(d[nx][ny]) == 1:
                    continue

                d[nx][ny] = 1
                q.insert(0, (nx,ny))

    ans = 0
    for x in range(sizeX):

        if d[x][0] == 1 or d[x][sizeY-1] == 1:
            print("INF")
            break

        if x % 2 == 0:
            continue

        for y in range(sizeY):
            if d[0][y] == 1 or d[sizeX-1][y] == 1:
                print("INF")
                break
            if y % 2 == 0:
                continue
            if d[x][y] == 1:
                ans += (sX[x//2+1]-sX[x//2])*(sY[y//2+1]-sY[y//2])
        else:
            continue
        break
    else:
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

def main():
    N, M = map(int, input().split())

    LV = []
    LH = []

    mp_X = defaultdict(int)
    mp_Y = defaultdict(int)

    mp_X[0] = 0
    mp_Y[0] = 0

    for _ in range(N):
        a,b,c = map(int, input().split())
        mp_X[a] = 0
        mp_X[b] = 0
        mp_Y[c] = 0
        LH.append((a,b,c))

    for _ in range(M):
        d,e,f = map(int, input().split())
        mp_X[d] = 0
        mp_Y[e] = 0
        mp_Y[f] = 0
        LV.append((e,f,d))

    sX = []
    sY = []

    for i, k in enumerate(sorted(mp_X)):
        mp_X[k] = i
        sX.append(k)
    for i, k in enumerate(sorted(mp_Y)):
        mp_Y[k] = i
        sY.append(k)

    sizeX = len(mp_X) * 2 - 1
    sizeY = len(mp_Y) * 2 - 1

    d = [[0 for _ in range(sizeY)] for _ in range(sizeX)]

    for x1,x2,y in LH:
        for x in range(mp_X[x1]*2, mp_X[x2]*2+1):
            d[x][mp_Y[y]*2] = -1

    for y1,y2,x in LV:
        for y in range(mp_Y[y1]*2, mp_Y[y2]*2+1):
            d[mp_X[x]*2][y] = -1

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

    q = deque()
    cx, cy = mp_X[0]*2, mp_Y[0]*2
    d[cx][cy] = 1
    q.append((cx,cy))
    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < sizeX and 0 <= ny < sizeY:
                if abs(d[nx][ny]) == 1:
                    continue

                d[nx][ny] = 1
                q.append((nx,ny))

    ans = 0
    for x in range(sizeX):

        if d[x][0] == 1 or d[x][sizeY-1] == 1:
            print("INF")
            break

        if x % 2 == 0:
            continue

        for y in range(sizeY):
            if d[0][y] == 1 or d[sizeX-1][y] == 1:
                print("INF")
                break
            if y % 2 == 0:
                continue
            if d[x][y] == 1:
                ans += (sX[x//2+1]-sX[x//2])*(sY[y//2+1]-sY[y//2])
        else:
            continue
        break
    else:
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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

LV = []
LH = []

mp_X = defaultdict(int)
mp_Y = defaultdict(int)

mp_X[0] = 0
mp_Y[0] = 0

for _ in range(N):
    a,b,c = map(int, input().split())
    mp_X[a] = 0
    mp_X[b] = 0
    mp_Y[c] = 0
    LH.append((a,b,c))

for _ in range(M):
    d,e,f = map(int, input().split())
    mp_X[d] = 0
    mp_Y[e] = 0
    mp_Y[f] = 0
    LV.append((e,f,d))

sX = []
sY = []

for i, k in enumerate(sorted(mp_X)):
    mp_X[k] = i
    sX.append(k)
for i, k in enumerate(sorted(mp_Y)):
    mp_Y[k] = i
    sY.append(k)

sizeX = len(mp_X) * 2 - 1
sizeY = len(mp_Y) * 2 - 1

d = [[0 for _ in range(sizeY)] for _ in range(sizeX)]

for x1,x2,y in LH:
    for x in range(mp_X[x1]*2, mp_X[x2]*2+1):
        d[x][mp_Y[y]*2] = -1

for y1,y2,x in LV:
    for y in range(mp_Y[y1]*2, mp_Y[y2]*2+1):
        d[mp_X[x]*2][y] = -1

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

q = deque()
cx, cy = mp_X[0]*2, mp_Y[0]*2
d[cx][cy] = 1
q.append((cx,cy))
while q:
    cx, cy = q.popleft()
    for i in range(4):
        nx, ny = cx + dx[i], cy + dy[i]
        if nx < 0 or sizeX <= nx or ny < 0 or sizeY <= ny:
            continue
        if d[nx][ny] == -1:
            continue
        if d[nx][ny] == 1:
            continue

        d[nx][ny] = 1
        q.append((nx,ny))

ans = 0
for x in range(sizeX):

    if d[x][0] == 1 or d[x][sizeY-1] == 1:
        print("INF")
        break

    if x % 2 == 0:
        continue

    for y in range(sizeY):
        if d[0][y] == 1 or d[sizeX-1][y] == 1:
            print("INF")
            break
        if y % 2 == 0:
            continue
        if d[x][y] == 1:
            ans += (sX[x//2+1]-sX[x//2])*(sY[y//2+1]-sY[y//2])
    else:
        continue
    break
else:
    print(ans)