Problem p02680 (python)

Fixed submission:
import sys
from collections import defaultdict

input = sys.stdin.readline
n, m = map(int, input().split())

xx = set([0]); yy = set([0]);
aa = []; bb = []; cc = []; dd = []; ee = []; ff = []; 
for _ in range(n):
    a, b, c = map(int, input().split())
    xx.add(a)
    xx.add(b)
    yy.add(c)
    aa.append(a); bb.append(b); cc.append(c); 
for _ in range(m):
    d, e, f = map(int, input().split())
    xx.add(d)
    yy.add(e)
    yy.add(f)
    dd.append(d); ee.append(e); ff.append(f); 
xx = sorted(list(xx))
yy = sorted(list(yy))
xp = defaultdict(int)
yp = defaultdict(int)

for i, v in enumerate(xx):
    xp[v] = i
for i, v in enumerate(yy):
    yp[v] = i

h = len(xx) - 1
w = len(yy) - 1
lx = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
ly = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(n):
    a, b, c = aa[i], bb[i], cc[i]
    for x in range(xp[a], xp[b]):
        lx[x][yp[c]] = 1

for i in range(m):
    d, e, f = dd[i], ee[i], ff[i]
    for y in range(yp[e], yp[f]):
        ly[xp[d]][y] = 1

visited = [[False for _ in range(w)] for _ in range(h)]
sx, sy = min(xp[0], h - 1), min(yp[0], w - 1)
visited[sx][sy] = True
q = [(sx, sy)]
ans = 0

while q:
    x, y = q.pop()
    ans += (xx[x + 1] - xx[x]) * (yy[y + 1] - yy[y])
    if ly[x][y] == 0:
        if x == 0:
            print('INF'); exit();
        if not visited[x - 1][y]:
            visited[x - 1][y] = True
            q.append((x - 1, y))
    if lx[x][y] == 0:
        if y == 0:
            print('INF'); exit();
        if not visited[x][y - 1]:
            visited[x][y - 1] = True
            q.append((x, y - 1))
    if ly[x + 1][y] == 0:
        if x == h - 1:
            print('INF'); exit();
        if not visited[x + 1][y]:
            visited[x + 1][y] = True
            q.append((x + 1, y))
    if lx[x][y + 1] == 0:
        if y == w - 1:
            print('INF'); exit();
        if not visited[x][y + 1]:
            visited[x][y + 1] = True
            q.append((x, y + 1))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict

input = sys.stdin.readline
n, m = map(int, input().split())

xx = set([0]); yy = set([0]);
aa = []; bb = []; cc = []; dd = []; ee = []; ff = []; 
for _ in range(n):
    a, b, c = map(int, input().split())
    xx.add(a)
    xx.add(b)
    yy.add(c)
    aa.append(a); bb.append(b); cc.append(c); 
for _ in range(m):
    d, e, f = map(int, input().split())
    xx.add(d)
    yy.add(e)
    yy.add(f)
    dd.append(d); ee.append(e); ff.append(f); 
xx = sorted(list(xx))
yy = sorted(list(yy))
xp = defaultdict(int)
yp = defaultdict(int)

for i, v in enumerate(xx):
    xp[v] = i
for i, v in enumerate(yy):
    yp[v] = i

h = len(xx) - 1
w = len(yy) - 1
lx = [[0 for _ in range(w + 1)] for _ in range(h + 1)]
ly = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(n):
    a, b, c = aa[i], bb[i], cc[i]
    for x in range(xp[a], xp[b]):
        lx[x][yp[c]][1] = 1

for i in range(m):
    d, e, f = dd[i], ee[i], ff[i]
    for y in range(yp[e], yp[f]):
        ly[xp[d]][y] = 1

visited = [[False for _ in range(w)] for _ in range(h)]
sx, sy = min(xp[0], h - 1), min(yp[0], w - 1)
visited[sx][sy] = True
q = [(sx, sy)]
ans = 0

while q:
    x, y = q.pop()
    ans += (xx[x + 1] - xx[x]) * (yy[y + 1] - yy[y])
    if ly[x][y] == 0:
        if x == 0:
            print('INF'); exit();
        if not visited[x - 1][y]:
            visited[x - 1][y] = True
            q.append((x - 1, y))
    if lx[x][y] == 0:
        if y == 0:
            print('INF'); exit();
        if not visited[x][y - 1]:
            visited[x][y - 1] = True
            q.append((x, y - 1))
    if ly[x + 1][y] == 0:
        if x == h - 1:
            print('INF'); exit();
        if not visited[x + 1][y]:
            visited[x + 1][y] = True
            q.append((x + 1, y))
    if lx[x][y + 1] == 0:
        if y == w - 1:
            print('INF'); exit();
        if not visited[x][y + 1]:
            visited[x][y + 1] = True
            q.append((x, y + 1))

print(ans)

Buggy submission (verdict: Runtime Error):
import bisect
import sys
from collections import defaultdict

INF = 10**9 + 1
input = sys.stdin.readline
n, m = map(int, input().split())

xx = set()
yy = set()
a2c = []
d2f = [] 
for _ in range(n):
    a, b, c = map(int, input().split())
    yy.add(c)
    a2c.append((a, b, c))
for _ in range(m):
    d, e, f = map(int, input().split())
    xx.add(d)
    d2f.append((d, e, f))
xx.add(-INF)
xx.add(+INF)
yy.add(-INF)
yy.add(+INF)
xx = sorted(list(xx))
yy = sorted(list(yy))

h = len(xx) - 1
w = len(yy) - 1
field = [[[0, 0, 0, 0] for _ in range(w)] for _ in range(h)]

for a, b, c in a2c:
    for x in range(bisect.bisect_left(xx, a), bisect.bisect_left(xx, b)):
        y = bisect.bisect_left(yy, c)
        field[x][y][1] = 1
        field[x][y - 1][3] = 1

for d, e, f in d2f:
    for y in range(bisect.bisect_left(yy, e), bisect.bisect_left(yy, f)):
        x = bisect.bisect_left(xx, d)
        field[x][y][0] = 1
        field[x - 1][y][2] = 1

visited = [[False for _ in range(w)] for _ in range(h)]
sx, sy = bisect.bisect_left(xx, 0), bisect.bisect_left(yy, 0)
visited[sx][sy] = True
q = [(sx, sy)]
ans = 0

while q:
    x, y = q.pop()
    ans += (xx[x + 1] - xx[x]) * (yy[y + 1] - yy[y])
    if field[x][y][0] == 0:
        if x <= 1:
            print('INF'); exit();
        if not visited[x - 1][y]:
            visited[x - 1][y] = True
            q.append((x - 1, y))
    if field[x][y][1] == 0:
        if y <= 1:
            print('INF'); exit();
        if not visited[x][y - 1]:
            visited[x][y - 1] = True
            q.append((x, y - 1))
    if field[x][y][2] == 0:
        if x >= h - 2:
            print('INF'); exit();
        if not visited[x + 1][y]:
            visited[x + 1][y] = True
            q.append((x + 1, y))
    if field[x][y][3] == 0:
        if y >= w - 2:
            print('INF'); exit();
        if not visited[x][y + 1]:
            visited[x][y + 1] = True
            q.append((x, y + 1))

print(ans)

Buggy submission (verdict: Runtime Error):
import bisect
import sys
from collections import defaultdict

input = sys.stdin.readline
n, m = map(int, input().split())

xx = set()
yy = set()
a2c = []
d2f = [] 
for _ in range(n):
    a, b, c = map(int, input().split())
    yy.add(c)
    a2c.append((a, b, c))
for _ in range(m):
    d, e, f = map(int, input().split())
    xx.add(d)
    d2f.append((d, e, f))
xx = sorted(list(xx))
yy = sorted(list(yy))

h = len(xx) - 1
w = len(yy) - 1
field = [[[0, 0, 0, 0] for _ in range(w)] for _ in range(h)]

for a, b, c in a2c:
    for x in range(bisect.bisect_left(xx, a), bisect.bisect_left(xx, b)):
        if x < h:
            y = bisect.bisect_left(yy, c)
            if y < w:
                field[x][y][1] = 1
            if y - 1 >= 0:
                field[x][y - 1][3] = 1

for d, e, f in d2f:
    for y in range(bisect.bisect_left(yy, e), bisect.bisect_left(yy, f)):
        if y < w:
            x = bisect.bisect_left(xx, d)
            if x < h:
                field[x][y][0] = 1
            if x - 1 >= 0:
                field[x - 1][y][2] = 1

visited = [[False for _ in range(w)] for _ in range(h)]
sx, sy = min(bisect.bisect_left(xx, 0), h - 1), min(bisect.bisect_left(yy, 0), w - 1)
visited[sx][sy] = True
q = [(sx, sy)]
ans = 0

while q:
    x, y = q.pop()
    ans += (xx[x + 1] - xx[x]) * (yy[y + 1] - yy[y])
    if field[x][y][0] == 0:
        if x == 0:
            print('INF'); exit();
        if not visited[x - 1][y]:
            visited[x - 1][y] = True
            q.append((x - 1, y))
    if field[x][y][1] == 0:
        if y == 0:
            print('INF'); exit();
        if not visited[x][y - 1]:
            visited[x][y - 1] = True
            q.append((x, y - 1))
    if field[x][y][2] == 0:
        if x == h - 1:
            print('INF'); exit();
        if not visited[x + 1][y]:
            visited[x + 1][y] = True
            q.append((x + 1, y))
    if field[x][y][3] == 0:
        if y == w - 1:
            print('INF'); exit();
        if not visited[x][y + 1]:
            visited[x][y + 1] = True
            q.append((x, y + 1))

print(ans)