Problem p02680 (python)

Fixed submission:
from bisect import bisect_left as bl
from collections import deque
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
n,m = map(int,input().split())
H = set([float("INF"),-float("INF")])
V = set([float("INF"),-float("INF")])
nl = []
ml = []
for i in range(n):
    a,b,c = map(int,input().split())
    H |= set([a,b])
    V.add(c)
    nl.append([a,b,c])
for i in range(m):
    c,a,b = map(int,input().split())
    V |= set([a,b])
    H.add(c)
    ml.append([a,b,c])
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C
H ,dx = compress(H)
V, dy = compress(V)

h = len(H)+2
w = len(V)+2
d = [[0]*3001 for i in range(3001)]
checkh = [[0]*3001 for i in range(3001)]
checkv = [[0]*3001 for i in range(3001)]

for a,b,c in nl:
    s = dx[a]
    g = dx[b]
    t = dy[c]
    
    for x in range(s,g):
        checkh[x][t] = 1

for a,b,c in ml:
    s = dy[a]
    g = dy[b]
    t = dx[c]
    
    for y in range(s,g):
        checkv[t][y] = 1


def bfs(x,y):
    ans = 0
    sx = bl(H,0)-1
    sy = bl(V,0)-1
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 1
    while q:
        h,v = q.popleft()
        ans += (H[h+1]-H[h])*(V[v+1]-V[v])
        if h != 0 and checkv[h][v] == 0 and d[h-1][v] == 0:
            d[h-1][v] = 1
            q.append((h-1,v))
        if v != 0 and checkh[h][v] == 0 and d[h][v-1] == 0:
            d[h][v-1] = 1
            q.append((h,v-1))
        if h != len(H)-2 and checkv[h+1][v] == 0 and d[h+1][v] == 0:
            d[h+1][v] = 1
            q.append((h+1,v))
        if v != len(V)-2 and checkh[h][v+1] == 0 and d[h][v+1] == 0:
            d[h][v+1] = 1
            q.append((h,v+1))
    print("INF" if ans ==float("INF") else ans)

bfs(0,0)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
sys.setrecursionlimit(10**8)
n,m = map(int,input().split())
X = [0]
Y = [0]
nl = []
ml = []
for i in range(n):
    a,b,c = map(int,input().split())
    Y.append(c)
    X.append(a)
    X.append(b)
    nl.append([a,b,c])
for i in range(m):
    a,b,c = map(int,input().split())
    X.append(a)
    Y.append(b)
    Y.append(c)
    ml.append([a,b,c])

X.sort()
Y.sort()
xl = []
yl = []
dx = {}
dy = {}
for i in range(len(X)):
    if xl == []:
        xl.append(X[i])
        dx[X[i]] = 0
    else:
        if X[i] != xl[-1]:
            dx[X[i]] = len(xl)
            xl.append(X[i])

for i in range(len(Y)):
    if yl == []:
        dy[Y[i]] = 0
        yl.append(Y[i])
    else:
        if Y[i] != yl[-1]:
            dy[Y[i]] = len(yl)
            yl.append(Y[i])

h = len(xl)*2+1
w = len(yl)*2+1
d = [[0]*w for i in range(h)]

for a,b,c in nl:
    s = dx[a]*2+1
    g = dx[b]*2+1
    t = dy[c]*2+1
    
    for x in range(s,g+1):
        d[x][t] = -1

for a,b,c in ml:
    t = dx[a]*2+1
    s = dy[b]*2+1
    g = dy[c]*2+1
    
    for y in range(s,g+1):
        d[t][y] = -1


ans = 0
dtx = [1,-1,0,0]
dty = [0,0,1,-1]

sx = dx[0]*2+1
sy = dy[0]*2+1

q = deque([])
q.append((sx,sy))
d[sx][sy] = 1
while q:
    nx,ny = q.popleft()

    for i in range(4):
        x = nx+dtx[i]
        y = ny+dty[i]

        if 0 <= x < h and 0 <= y < w and d[x][y] == 0:
            d[x][y] = 1
            q.append((x,y))


for i in range(h):
    for j in range(w):
        if d[i][j] == 0:
            continue
        if (i == 0 or j == 0 or i == h-1 or j == w-1) and d[i][j] == 1:
            print("INF")
            exit()
        if i%2 == 1 or j%2 == 1:
            continue
        x = xl[i//2+1]-xl[i//2]
        y = yl[j//2+1]-yl[j//2]
        ans += x*y

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
n,m = map(int,input().split())
X = [0]
Y = [0]
nl = []
ml = []
for i in range(n):
    a,b,c = map(int,input().split())
    Y.append(c)
    X.append(a)
    X.append(b)
    nl.append([a,b,c])
for i in range(m):
    a,b,c = map(int,input().split())
    X.append(a)
    Y.append(b)
    Y.append(c)
    ml.append([a,b,c])

X.sort()
Y.sort()
xl = []
yl = []
dx = {}
dy = {}
for i in range(len(X)):
    if xl == []:
        xl.append(X[i])
        dx[X[i]] = 0
    else:
        if X[i] != xl[-1]:
            dx[X[i]] = len(xl)
            xl.append(X[i])

for i in range(len(Y)):
    if yl == []:
        dy[Y[i]] = 0
        yl.append(Y[i])
    else:
        if Y[i] != yl[-1]:
            dy[Y[i]] = len(yl)
            yl.append(Y[i])

h = len(xl)*2+1
w = len(yl)*2+1
d = [[0]*w for i in range(h)]

for a,b,c in nl:
    s = dx[a]*2+1
    g = dx[b]*2+1
    t = dy[c]*2+1
    
    for x in range(s,g+1):
        d[x][t] = -1

for a,b,c in ml:
    t = dx[a]*2+1
    s = dy[b]*2+1
    g = dy[c]*2+1
    
    for y in range(s,g+1):
        d[t][y] = -1


ans = 0
dtx = [1,-1,0,0]
dty = [0,0,1,-1]

sx = dx[0]*2+1
sy = dy[0]*2+1

q = deque([])
q.append((sx,sy))
d[sx][sy] = 1
while q:
    nx,ny = q.popleft()

    for i in range(4):
        x = nx+dtx[i]
        y = ny+dty[i]

        if 0 <= x < h and 0 <= y < w and d[x][y] == 0:
            d[x][y] = 1
            q.append((x,y))


for i in range(h):
    for j in range(w):
        if d[i][j] == 0:
            continue
        if (i == 0 or j == 0 or i == h-1 or j == w-1) and d[i][j] == 1:
            print("INF")
            exit()
        if i%2 == 1 or j%2 == 1:
            continue
        x = xl[i//2+1]-xl[i//2]
        y = yl[j//2+1]-yl[j//2]
        ans += x*y

print(ans)