Problem p02680 (python)

Fixed submission:
from collections import deque
import bisect

INF = float("inf")

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

xtic = {0,-INF,INF}
ytic = {0,-INF,INF}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if (hor_wall[y+1]>>x)&1:
        return False
      return True
    else:
      if (hor_wall[y]>>x)&1:
        return False
      return True
  else:
    if dx > 0:
      if (ver_wall[x+1]>>y)&1:
        return False
      return True
    else:
      if (ver_wall[x]>>y)&1:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

hor_wall = [0 for i in range(H)]
ver_wall = [0 for i in range(W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]
"""
for k in range(H):
  listb = list(map(int,list(bin(hor_wall[k])[2:])))
  hor_wall[k] = [0 for j in range(H-len(listb))] + listb

for k in range(W):
  listb = list(map(int,list(bin(ver_wall[k])[2:])))
  ver_wall[k] = [0 for j in range(W-len(listb))] + listb  
"""

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 10**9 + 1

def precompute(N, M, data):
    data = data.reshape(-1, 3)
    A, B, C = data[:N].T
    D, E, F = data[N:].T
    X = np.unique(np.concatenate([A, B, D, [0, -INF, INF]]))
    Y = np.unique(np.concatenate([C, E, F, [0, -INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B)
    D = np.searchsorted(X, D)
    C = np.searchsorted(Y, C)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F)
    return A, B, C, D, E, F, X, Y

def solve(A, B, C, D, E, F, X, Y):
    H, W = len(X), len(Y)
    N = H * W
    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    def set_ng(A, B, C, D, E, F, H, W):
        ng = np.zeros((H * W, 4), np.bool_)

        for i in range(len(A)):
            for x in range(A[i], B[i]):
                v = x * W + C[i]
                ng[v][1] = 1
                ng[v - 1][0] = 1

        for i in range(len(D)):
            for y in range(E[i], F[i]):
                v = D[i] * W + y
                ng[v][3] = 1
                ng[v - W][2] = 1
        return ng

    ng = set_ng(A, B, C, D, E, F, H, W)
    x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
    v0 = x0 * W + y0
    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)
    move = (1, -1, W, -W)
    while p:
        v = pop()
        for i in range(4):
            if ng[v][i]:
                continue
            w = v + move[i]
            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

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    signature = '(i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1])'
    cc.export('solve', signature)(solve)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()

from my_module import solve

N, M = map(int, readline().split())
data = np.int64(read().split())

x = solve(*precompute(N, M, data))
if x == 0:
    print('INF')
else:
    print(x)

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

INF = float("inf")

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

xtic = {0,-INF,INF}
ytic = {0,-INF,INF}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_wall[y+1][H-1-x]:
        return False
      return True
    else:
      if hor_wall[y][H-1-x]:
        return False
      return True
  else:
    if dx > 0:
      if ver_wall[x+1][W-1-y]:
        return False
      return True
    else:
      if ver_wall[x][W-1-y]:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

hor_wall = [0 for i in range(H)]
ver_wall = [0 for i in range(W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]

def Base_10_to_2(X):
  if (int(X/2)):
    return Base_10_to_2(int(X/2))+str(X%2)
  return str(X%2)  

for k in range(H):
  listb = list(map(int,list(Base_10_to_2(hor_wall[k]))))
  hor_wall[k] = [0 for j in range(H-len(listb))] + listb

for k in range(W):
  listb = list(map(int,list(Base_10_to_2(ver_wall[k]))))
  ver_wall[k] = [0 for j in range(W-len(listb))] + listb  
  

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_wall[y+1][H-1-x]:
        return False
      return True
    else:
      if hor_wall[y][H-1-x]:
        return False
      return True
  else:
    if dx > 0:
      if ver_wall[x+1][W-1-y]:
        return False
      return True
    else:
      if ver_wall[x][W-1-y]:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1


hor_wall = [0 for i in range(H)]
ver_wall = [0 for i in range(W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]
  
for k in range(len(hor_wall)):
  listb = list(map(int,list(bin(hor_wall[k])[2:])))
  hor_wall[k] = [0 for j in range(H-len(listb))] + listb

for k in range(len(ver_wall)):
  listb = list(map(int,list(bin(ver_wall[k])[2:])))
  ver_wall[k] = [0 for j in range(W-len(listb))] + listb
  


d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_wall[y+1][H-1-x]:
        return False
      return True
    else:
      if hor_wall[y][H-1-x]:
        return False
      return True
  else:
    if dx > 0:
      if ver_wall[x+1][W-1-y]:
        return False
      return True
    else:
      if ver_wall[x][W-1-y]:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

hor_wall = [0]*H
ver_wall = [0]*W

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]
  
for k in range(H):
  listb = list(map(int,list(bin(hor_wall[k])[2:])))
  hor_wall[k] = [0]*(H-len(listb)) + listb

for k in range(W):
  listb = list(map(int,list(bin(ver_wall[k])[2:])))
  ver_wall[k] = [0]*(W-len(listb)) + listb

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_wall[y+1][x]:
        return False
      return True
    else:
      if hor_wall[y][x]:
        return False
      return True
  else:
    if dx > 0:
      if ver_wall[x+1][y]:
        return False
      return True
    else:
      if ver_wall[x][y]:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[W] = INF
gyaku_ydic[H] = INF

hor_wall = [0] + [0 for i in range(1,H)]
ver_wall = [0] + [0 for i in range(1,W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]
  
for k in range(len(hor_wall)):
  listb = list(map(int,list(bin(hor_wall[k])[2:])))
  hor_wall[k] = [0 for j in range(H)]
  hor_wall[k][:len(listb)] = listb[::-1]

for k in range(len(ver_wall)):
  listb = list(map(int,list(bin(ver_wall[k])[2:])))
  ver_wall[k] = [0 for j in range(W)]
  ver_wall[k][:len(listb)] = listb[::-1]
  


d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_wall[y+1][H-1-x]:
        return False
      return True
    else:
      if hor_wall[y][H-1-x]:
        return False
      return True
  else:
    if dx > 0:
      if ver_wall[x+1][W-1-y]:
        return False
      return True
    else:
      if ver_wall[x][W-1-y]:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[W] = INF
gyaku_ydic[H] = INF

hor_wall = [0] + [0 for i in range(1,H)]
ver_wall = [0] + [0 for i in range(1,W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]
  
for i in range(len(hor_wall)):
  listb = list(map(int,(list(bin(hor_wall[i])[2:]))))
  hor_wall[i] = [0 for j in range(W)]
  hor_wall[i][-len(listb):] = listb
for i in range(len(ver_wall)):
  listb = list(map(int,(list(bin(ver_wall[i])[2:]))))
  ver_wall[i] = [0 for j in range(H)]
  ver_wall[i][-len(listb):] = listb

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = (1<<b) - (1<<a)
  else:
    hor_dic[c] |= (1<<b) - (1<<a)
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = (1<<f) - (1<<e)
  else:
    ver_dic[d] |= (1<<f) - (1<<e)
  now = d

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if hor_dic[y+1] & (1<<x):
        return False
      return True
    else:
      if hor_dic[y] & (1<<x):
        return False
      return True
  else:
    if dx > 0:
      if ver_dic[x+1] & (1<<y):
        return False
      return True
    else:
      if ver_dic[x] & (1<<y):
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[W] = INF
gyaku_ydic[H] = INF

hor_wall = [0] + [0 for i in range(1,H)]
ver_wall = [0] + [0 for i in range(1,W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]


d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.popleft()
  area += calc_area(x,y)
  if area == INF:
    print("INF")
    exit()
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = [(a,b)]
  else:
    hor_dic[c].append((a,b))
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = [(e,f)]
  else:
    ver_dic[d].append((e,f))
  now = d

hor_wall = [-INF] + [k for k in hor_dic] + [INF]
ver_wall = [-INF] + [k for k in ver_dic] + [INF]

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      p = bisect.bisect_left(hor_wall,y+1)
      if hor_wall[p] != y+1:
        return True
      else:
        for l,r in hor_dic[y+1]:
          if l<=x<r:
            return False
        return True
    else:
      p = bisect.bisect_left(hor_wall,y)
      if hor_wall[p] != y:
        return True
      else:
        for l,r in hor_dic[y]:
          if l<=x<r:
            return False
        return True
  else:
    if dx > 0:
      p = bisect.bisect_left(ver_wall,x+1)
      if ver_wall[p] != x+1:
        return True
      else:
        for l,r in ver_dic[x+1]:
          if l<=y<r:
            return False
        return True
    else:
      p = bisect.bisect_left(ver_wall,x)
      if ver_wall[p] != x:
        return True
      else:
        for l,r in ver_dic[x]:
          if l<=y<r:
            return False
        return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[H] = INF
gyaku_ydic[W] = INF

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.popleft()
  area += calc_area(x,y)
  #if area == INF:
  #  print("INF")
  #  exit()
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      #if is_connected(x,y,dx,dy):
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = [(a,b)]
  else:
    hor_dic[c].append((a,b))
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = [(e,f)]
  else:
    ver_dic[d].append((e,f))
  now = d

hor_wall = [-INF] + [k for k in hor_dic] + [INF]
ver_wall = [-INF] + [k for k in ver_dic] + [INF]

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      p = bisect.bisect_left(hor_wall,y+1)
      if hor_wall[p] != y+1:
        return True
      else:
        for l,r in hor_dic[y+1]:
          if l<=x<r:
            return False
        return True
    else:
      p = bisect.bisect_left(hor_wall,y)
      if hor_wall[p] != y:
        return True
      else:
        for l,r in hor_dic[y]:
          if l<=x<r:
            return False
        return True
  else:
    if dx > 0:
      p = bisect.bisect_left(ver_wall,x+1)
      if ver_wall[p] != x+1:
        return True
      else:
        for l,r in ver_dic[x+1]:
          if l<=y<r:
            return False
        return True
    else:
      p = bisect.bisect_left(ver_wall,x)
      if ver_wall[p] != x:
        return True
      else:
        for l,r in ver_dic[x]:
          if l<=y<r:
            return False
        return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[H] = INF
gyaku_ydic[W] = INF

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.popleft()
  area += calc_area(x,y)
  if area == INF:
    print("INF")
    exit()
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = [(a,b)]
  else:
    hor_dic[c].append((a,b))
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = [(e,f)]
  else:
    ver_dic[d].append((e,f))
  now = d

hor_wall = [-INF] + [k for k in hor_dic] + [INF]
ver_wall = [-INF] + [k for k in ver_dic] + [INF]

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      p = bisect.bisect_left(hor_wall,y+1)
      if hor_wall[p] != y+1:
        return True
      else:
        for l,r in hor_dic[y+1]:
          if l<=x<r:
            return False
        return True
    else:
      p = bisect.bisect_left(hor_wall,y)
      if hor_wall[p] != y:
        return True
      else:
        for l,r in hor_dic[y]:
          if l<=x<r:
            return False
        return True
  else:
    if dx > 0:
      p = bisect.bisect_left(ver_wall,x+1)
      if ver_wall[p] != x+1:
        return True
      else:
        for l,r in ver_dic[x+1]:
          if l<=y<r:
            return False
        return True
    else:
      p = bisect.bisect_left(ver_wall,x)
      if ver_wall[p] != x:
        return True
      else:
        for l,r in ver_dic[x]:
          if l<=y<r:
            return False
        return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[H] = INF
gyaku_ydic[W] = INF

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.popleft()
  area += calc_area(x,y)
  if area == INF:
    print("INF")
    exit()
  nd = d[y][x]+1
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if d[nx][ny] == 0:
          d[nx][ny] = 1
          q.append((nx,ny))

print(area)

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

INF = float("inf")

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

xtic = {0}
ytic = {0}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor.sort()
ver.sort()

hor_dic = {}
ver_dic = {}

now = None
for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  if c != now:
    hor_dic[c] = [(a,b)]
  else:
    hor_dic[c].append((a,b))
  now = c

now = None
for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  if d != now:
    ver_dic[d] = [(e,f)]
  else:
    ver_dic[d].append((e,f))
  now = d

hor_wall = [-INF] + [k for k in hor_dic] + [INF]
ver_wall = [-INF] + [k for k in ver_dic] + [INF]

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      p = bisect.bisect_left(hor_wall,y+1)
      if hor_wall[p] != y+1:
        return True
      else:
        for l,r in hor_dic[y+1]:
          if l<=x<r:
            return False
        return True
    else:
      p = bisect.bisect_left(hor_wall,y)
      if hor_wall[p] != y:
        return True
      else:
        for l,r in hor_dic[y]:
          if l<=x<r:
            return False
        return True
  else:
    if dx > 0:
      p = bisect.bisect_left(ver_wall,x+1)
      if ver_wall[p] != x+1:
        return True
      else:
        for l,r in ver_dic[x+1]:
          if l<=y<r:
            return False
        return True
    else:
      p = bisect.bisect_left(ver_wall,x)
      if ver_wall[p] != x:
        return True
      else:
        for l,r in hor_dic[x]:
          if l<=y<r:
            return False
        return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

gyaku_xdic[0] = -INF
gyaku_ydic[0] = -INF
gyaku_xdic[H] = INF
gyaku_ydic[W] = INF

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.popleft()
  area += calc_area(x,y)
  if area == INF:
    print("INF")
    exit()
  nd = d[y][x]+1
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if d[nx][ny] == 0:
          d[nx][ny] = 1
          q.append((nx,ny))

print(area)