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: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
import bisect
from collections import deque
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = [-float("inf"),0,float("inf")]
    fy = [-float("inf"),0,float("inf")]
    for a,b,c in p:
        fy.append(a)
        fy.append(a+1e-1)
        fy.append(b)
        fy.append(b+1e-1)
        fx.append(c)
        fx.append(c+1e-1)

    for d,e,f in q:
        fy.append(d)
        fy.append(d+1e-1)
        fx.append(e)
        fx.append(e+1e-1)
        fx.append(f)
        fx.append(f+1e-1)
    fy = list(set(fy))
    fx = list(set(fx))
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    nh,nw = len(fy)-1,len(fx)-1
    for i in range(1,nw-1):
        fx[i+1] = round(fx[i+1])
        fx[i] = fx[i+1]-fx[i]
    for i in range(1,nh-1):
        fy[i+1] = round(fy[i+1])
        fy[i] = fy[i+1]-fy[i]
    fx[0] = -fx[0]
    fy[0] = -fy[0]
    ans = fx[sx]*fy[sy]
    q = deque((sy,sx))
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < nh and 0 <= nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    k = fx[nx]*fy[ny]
                    if k == float("inf"):
                        print("INF")
                        return
                    ans += k
                    f[ny][nx] = 0
                    q.appendleft((ny,nx))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = [-float("inf"),0,float("inf")]
    fy = [-float("inf"),0,float("inf")]
    for a,b,c in p:
        fy.append(a)
        fy.append(a+1e-1)
        fy.append(b)
        fy.append(b+1e-1)
        fx.append(c)
        fx.append(c+1e-1)

    for d,e,f in q:
        fy.append(d)
        fy.append(d+1e-1)
        fx.append(e)
        fx.append(e+1e-1)
        fx.append(f)
        fx.append(f+1e-1)
    fy = list(set(fy))
    fx = list(set(fx))
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    nh,nw = len(fy)-1,len(fx)-1
    for i in range(1,nw-1):
        fx[i+1] = round(fx[i+1])
        fx[i] = fx[i+1]-fx[i]
    for i in range(1,nh-1):
        fy[i+1] = round(fy[i+1])
        fy[i] = fy[i+1]-fy[i]
    fx[0] = -fx[0]
    fy[0] = -fy[0]
    ans = fx[sx]*fy[sy]
    q = [(sy,sx)]
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < nh and 0 <= nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    k = fx[nx]*fy[ny]
                    if k == float("inf"):
                        print("INF")
                        return
                    ans += k
                    f[ny][nx] = 0
                    q.appendleft((ny,nx))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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:
        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: Runtime Error

Solution code:
# coding: utf-8
from collections import deque
N,M=map(int,input().split())
tate=[]
yoko=[]
INF=10**20
MAP=[[INF for i in range(N+1)] for j in range(M+1)]
visited=[[False for i in range(N+1)] for j in range(M+1)]
tkabe=[[False for i in range(M-1)] for j in range(N)]
ykabe=[[False for i in range(N-1)] for j in range(M)]
Cl=[]
Dl=[]

for i in range(N):
    A,B,C=map(int,input().split())
    tate.append([C,[A,B]])
    Cl.append(C)
    
for i in range(M):
    D,E,F=map(int,input().split())
    yoko.append([D,[E,F]])
    Dl.append(D)

tate.sort()
yoko.sort()
Cl.sort()
Dl.sort()

for i in range(N):
    for j in range(M-1):
        a,b=tate[i][1]
        if a<=Dl[j] and Dl[j+1]<=b:
            tkabe[i][j]=True
        if Dl[j]<=0 and 0<=Dl[j+1]:
            sy=j+1

for i in range(M):
    for j in range(N-1):
        e,f=yoko[i][1]
        if e<=Cl[j] and Cl[j+1]<=f:
            ykabe[i][j]=True
        if Cl[j]<=0 and 0<=Cl[j+1]:
            sx=j+1
            
for i in range(M-1):
    for j in range(N-1):
        MAP[i+1][j+1]=(Cl[j+1]-Cl[j])*(Dl[i+1]-Dl[i])
        
dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=deque()
ans=MAP[sy][sx]
visited[sy][sx]=True
queue.append([sy,sx])

while len(queue)>0:
    y,x=queue.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if not(k==0 and tkabe[nx][ny-1]) and  not(k==2 and tkabe[nx-1][ny-1]) and not(k==1 and tkabe[ny][nx-1]) and not(k==3 and tkabe[ny+1][nx-1]):
            if 0<=ny<M+1 and 0<=nx<N+1:
                if not(visited[ny][nx]):
                    ans+=MAP[ny][nx]
                    queue.append([ny,nx])
                    visited[ny][nx]=True

if ans>=10**20-1:
    print("INF")
else:
    print(ans)

Submission status: Runtime Error

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:
        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: Runtime Error

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from bisect import bisect_left
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    AB = {}
    C = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        C.append(c)
        if c in AB:
            AB[c].append((a, b))
        else:
            AB[c] = [(a, b)]
    DE = {}
    F = []
    for _ in range(M):
        f, d, e = map(int, input().split())
        F.append(f)
        if f in DE:
            DE[f].append((d, e))
        else:
            DE[f] = [(d, e)]

    C = list(set(C))
    F = list(set(F))
    C.sort()
    F.sort()
    if C[0] >= 0 or C[-1] <= 0 or F[0] >= 0 or F[-1] <= 0:
        print("INF")
        exit()
        
    # boundary
    A = {}
    B = {}
    for c in AB:
        ab_list = AB[c]
        if len(ab_list) >= 2:
            ab_list.sort(key=lambda x: x[0])
            st = []
            for a, b in ab_list:
                if not st:
                    st.append((a, b))
                else:
                    aa, bb = st[-1]
                    if bb >= a:
                        st.pop()
                        st.append((aa, max(bb, b)))
            A[c] = [ab[0] for ab in st]
            B[c] = [ab[1] for ab in st]
        else:
            A[c] = [ab[0] for ab in ab_list]
            B[c] = [ab[1] for ab in ab_list]

    D = {}
    E = {}
    for f in DE:
        de_list = DE[f]
        if len(de_list) >= 2:
            de_list.sort(key=lambda x: x[0])
            st = []
            for d, e in de_list:
                if not st:
                    st.append((d, e))
                else:
                    dd, ee = st[-1]
                    if ee >= d:
                        st.pop()
                        st.append((dd, max(ee, e)))
            D[f] = [de[0] for de in st]
            E[f] = [de[1] for de in st]
        else:
            D[f] = [de[0] for de in de_list]
            E[f] = [de[1] for de in de_list]

    for i in range(1, len(C)):
        if C[i] >= 0:
            c0 = i-1
            break
    for j in range(1, len(F)):
        if F[j] >= 0:
            f0 = j-1
            break
    
    que = deque()
    que.append((c0, f0))
    seen = set()
    seen.add(c0 * 1001 + f0)
    ans = 0
    while que:
        i0, j0 = que.popleft()
        c0 = C[i0]
        c1 = C[i0+1]
        f0 = F[j0]
        f1 = F[j0+1]
        ans += (c1-c0) * (f1-f0)

        # right
        if i0 * (N+1) + j0+1 not in seen:
            i = bisect_left(D[f1], c0+1)
            j = bisect_left(E[f1], c1)
            if i <= j:
                que.append((i0, j0+1))
                seen.add(i0 * (N+1) + j0+1)
                if j0 == len(F):
                    print("INF")
                    exit()

        #left
        if i0 * (N+1) + j0-1 not in seen:
            i = bisect_left(D[f0], c0 + 1)
            j = bisect_left(E[f0], c1)
            if i <= j:
                que.append((i0, j0 - 1))
                seen.add(i0 * (N+1) + j0-1)
                if j0 == 0:
                    print("INF")
                    exit()

        # down
        if (i0+1) * (N+1) + j0 not in seen:
            i = bisect_left(A[c1], f0 + 1)
            j = bisect_left(B[c1], f1)
            if i <= j:
                que.append((i0+1, j0))
                seen.add((i0+1) * (N+1) + j0)
                if i0 == len(C):
                    print("INF")
                    exit()

        # up
        if (i0-1) * (N+1) + j0 not in seen:
            i = bisect_left(A[c0], f0 + 1)
            j = bisect_left(B[c0], f1)
            if i <= j:
                que.append((i0-1, j0))
                seen.add((i0-1) * (N+1) + j0)
                if i0 == 0:
                    print("INF")
                    exit()
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
M = 1000000007

import math

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		if a < 0:
			a = -a
			b = -b
		g = math.gcd(a, b)
		if g > 1:
			a //= g
			b //= g
		fish_list.append((a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_index_table = {}
for i, (f, c) in enumerate(fish_count_list):
	fish_index_table[f] = i

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	a, b = f
	a, b = (-b, a)
	if a < 0:
		a = -a
		b = -b
	key = (a, b)
	if key in fish_index_table:
		j = fish_index_table[key]
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += c

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

count = pow(2, singles, M)

#print(singles, pair_list, a_zero_count, b_zero_count)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)

Submission status: Runtime Error

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_left(tlis,0)
nowj = bisect.bisect_left(ylis,0)

#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

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: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = set([-float("inf"),0,float("inf")])
    fy = set([-float("inf"),0,float("inf")])
    for a,b,c in p:
        fy.add(a)
        fy.add(a+1e-1)
        fy.add(a-1e-1)
        fy.add(b)
        fy.add(b+1e-1)
        fy.add(b-1e-1)
        fx.add(c)
        fx.add(c+1e-1)
        fx.add(c-1e-1)

    for d,e,f in q:
        fy.add(d)
        fy.add(d+1e-1)
        fy.add(d-1e-1)
        fx.add(e)
        fx.add(e+1e-1)
        fx.add(e-1e-1)
        fx.add(f)
        fx.add(f+1e-1)
        fx.add(f-1e-1)
    fy = list(fy)
    fx = list(fx)
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    ans = 0
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    ans += round((fx[sx+1]-fx[sx])*(fy[sy+1]-fy[sy]))
    q = [(sy,sx)]
    nh,nw = len(fy)-1,len(fx)-1
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < nh and 0 <= nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    k = (fx[nx+1]-fx[nx])*(fy[ny+1]-fy[ny])
                    if k == float("inf"):
                        print("INF")
                        return
                    ans += round(k)
                    f[ny][nx] = 0
                    q.append((ny,nx))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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()]
yoko = [[int(i) for i in readline().split()] for _ in range(n)]
tate = [[int(i) for i in readline().split()] for _ in range(n)]

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)

ok = [[[1,1,1,1] for y in range(Q-1)] for x in range(P-1)] #移動できる方角
for y in range(Q-1):
    ok[0][y][2] = 0
    ok[P-2][y][0] = 0
for x in range(P-1):
    ok[x][0][3] = 0
    ok[x][Q-2][1] = 0

for a,b,c in yoko: # (a,c) to (b,c)
    xa = zaatu_x[a]
    xb = zaatu_x[b]
    yc = zaatu_y[c]
    for i in range(xa,xb):
        ok[i][yc][3] = 0
        ok[i][yc-1][1] = 0

for d,e,f in tate: # (d,e) to (d,f)
    ye = zaatu_y[e]
    yf = zaatu_y[f]
    xd = zaatu_x[d]
    for i in range(ye,yf):
        ok[xd][i][2] = 0
        ok[xd-1][i][0] = 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)]

q = [(x0,y0)]
used[x0][y0] = 1

while q:
    x,y = q.pop()
    for i,oki in enumerate(ok[x][y]):
        if oki:
            nx = x+dx[i]
            ny = y+dy[i]
            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 += (xcoord[i+1]-xcoord[i])*(ycoord[j+1]-ycoord[j])
    print(ans)

#print(xcoord)
#print(ycoord)

Submission status: Runtime Error

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: x0+=1
y0 = 0
while YL[y0]<0: 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: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = set([0])
    fy = set([0])
    for a,b,c in p:
        fy.add(a-1e-15)
        fy.add(a)
        fy.add(a+1e-15)
        fy.add(b-1e-15)
        fy.add(b)
        fy.add(b+1e-15)
        fx.add(c-1e-15)
        fx.add(c)
        fx.add(c+1e-15)

    for d,e,f in q:
        fy.add(d-1e-15)
        fy.add(d)
        fy.add(d+1e-15)
        fx.add(e-1e-15)
        fx.add(e)
        fx.add(e+1e-15)
        fx.add(f-1e-15)
        fx.add(f)
        fx.add(f+1e-15)
    fy = list(fy)
    fx = list(fx)
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    ans = 0
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    ans += (fx[sx+1]-fx[sx])*(fy[sy+1]-fy[sy])
    q = [(sy,sx)]
    nh,nw = len(fy)-1,len(fx)-1
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 < ny < nh and 0 < nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    ans += (fx[nx+1]-fx[nx])*(fy[ny+1]-fy[ny])
                    f[ny][nx] = 0
                    q.append((ny,nx))
    for i in range(1,nh):
        for j in range(1,nw):
            if s[i][j] == 0:
                if f[i][j]:
                    break
        else:
            continue
        break
    else:
        print("INF")
        return
    print(round(ans))
    return

#Solve
if __name__ == "__main__":
    solve()