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:
def compress(set_):
    """座標圧縮した辞書を返す"""
    array2 = sorted(list(set_))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

def calc_s(hi, wj):
    """座標圧縮後の範囲hi <= i < hi + 1, wj <= j < wj + 1について、
    座標圧縮前の面積を求める
    """
    res = (h_rests[hi] - h_rests[hi + 1]) * (w_rests[wj] - w_rests[wj + 1]) 
    return res   

h, w = map(int, input().split())
info_h = [list(map(int, input().split())) for i in range(h)]
info_w = [list(map(int, input().split())) for i in range(w)]
INF = 10 ** 20

h_coords = set([-INF, 0, INF])
w_coords = set([-INF, 0, INF])

for h1, h2, w1 in info_h:
    h_coords.add(h1)
    h_coords.add(h2)
    w_coords.add(w1)
for h1, w1, w2 in info_w:
    h_coords.add(h1)
    w_coords.add(w1)
    w_coords.add(w2)


h_comps = compress(h_coords)
w_comps = compress(w_coords)

h_rests = {h_comps[index]: index for index in h_comps}
w_rests = {w_comps[index]: index for index in w_comps}
print(h_comps, w_comps)


# いずれにも進める = 1
# 左右に進めない = 2
# 上下に進めない = 3
# 上下左右にも進めない = 6

# 半開区間の線分で管理
# 横線
# ●-●-●-●-○
# 縦線
# ●
# |
# ●
# |
# ●
# |
# ○

grid = [[1] * (3010) for i in range(3010)]
for h1, h2, w1 in info_h:
    h1, h2, w1 = h_comps[h1], h_comps[h2], w_comps[w1]
    for hi in range(h1, h2):
        grid[hi][w1] *= 2

for h1, w1, w2 in info_w:
    h1, w1, w2 = h_comps[h1], w_comps[w1], w_comps[w2]
    for wi in range(w1, w2):
        grid[h1][wi] *= 3


used = [[False] * (3010) for i in range(3010)]
si, sw = h_comps[0], w_comps[0]
stack = [(si, sw)]
ans = calc_s(si, sw)
used[si][sw] = True

while stack:
    i, j = stack.pop()
    # 上移動
    nxt_i, nxt_j = i - 1, j

    if grid[nxt_i][nxt_j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 上に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 下移動
    nxt_i, nxt_j = i + 1, j
    if grid[i][j] % 3 == 0 or used[nxt_i][nxt_j]:
        # 下に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))

    # 右移動
    nxt_i, nxt_j = i, j + 1
    if grid[nxt_i][nxt_j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 右に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j))
        
    # 左移動
    nxt_i, nxt_j = i, j - 1
    if grid[i][j] % 2 == 0 or used[nxt_i][nxt_j]:
        # 左に進めない
        pass
    else:
        used[nxt_i][nxt_j] = True
        ans += calc_s(nxt_i, nxt_j)
        stack.append((nxt_i, nxt_j)) 

    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)

Submission status: Runtime Error

Solution code:
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R=(f,F),(f,-F),;H=(F,f),(-F,f),
for i in r(n):*a,c=I();R+=(a,c),;Y+=c,;X+=a
for i in r(m):a,*b=I();H+=(a,b),;X+=a,;Y+=b
def g(X):s=sorted(set(X));l=len(s);return{s[i]:i for i in r(l)},s,l
h,s,K=g(X);w,t,L=g(Y);V,U,v=[[[0]*-~K for i in r(L+1)]for _ in r(3)]
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]-=1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]-=1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];a=0
while q:
 x,y=q.pop();v[y][x]=1;a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in(-1,0),(1,0),(0,1),(0,-1),:
  c=x+e;d=y+f
  if 1-v[d][c]and U[(f>0)+y][x]*f+V[y][(e>0)+x]*e==0:q+=[(c,d)];v[d][c]=1
print [a,'INF'][a>F]

Submission status: Runtime Error

Solution code:
I=lambda:map(int,input().split());F=1e21;r=range;n,m=I();f=[-F,F];X=[0]+f;Y=X[:];R,H=[],[]
for i in r(n):*a,c=I();R+=[(a,c)];Y+=c,;X+=a
for i in r(m):a,*b=I();H+=[(a,b)];X+=a,;Y+=b
def g(X):s=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)+1
h,s,K=g(X);w,t,L=g(Y);j=lambda:[[0]*-~K for i in r(L+1)];V=j();U=j();v=j()
for(a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for d,(e,f)in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for i in r(L):
 for j in r(K):U[i][j+1]+=U[i][j];V[i+1][j]+=V[i][j]
q=[(h[0],w[0])];v[w[0]][h[0]]=1;a=0
while q:
 x,y=q.pop();a+=(s[x]-s[x+1])*(t[y]-t[y+1])
 for e,f in[(-1,0),(1,0),(0,1),(0,-1)]:
  c=x+e;d=y+f
  if(K>c>=0<=d<L)*v[d][c]==0and(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0):q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect
import collections


class VBoarder(object):

  def __init__(self, x1, x2, y):
    self.x1 = x1
    self.x2 = x2
    self.y = y


class HBoarder(object):

  def __init__(self, x, y1, y2):
    self.x = x
    self.y1 = y1
    self.y2 = y2


class Cell(object):

  def __init__(self, x1, y1, x2, y2):
    self.x1 = x1
    self.y1 = y1
    self.x2 = x2
    self.y2 = y2
    self.up = True
    self.down = True
    self.left = True
    self.right = True
    self.checked = False

  def area(self):
    return (self.x2 - self.x1) * (self.y2 - self.y1)

  def __str__(self):
    return '(({:2d},{:2d}),({:2d},{:2d})){}{}{}{}'.format(
      self.x1, self.y1, self.x2, self.y2,
      'Uu'[int(self.up)], 'Dd'[int(self.down)], 'Ll'[int(self.left)], 'Rr'[int(self.right)])


def main():
  N, M = map(int, input().split())
  vborders = [VBoarder(*map(int, input().split())) for _ in range(N)]
  hborders = [HBoarder(*map(int, input().split())) for _ in range(M)]

  y_axis = list(set([b.y for b in vborders]))
  y_axis.sort()
  y_axis = [y_axis[0] - 1] + y_axis + [y_axis[-1] + 1]
  x_axis = list(set([b.x for b in hborders]))
  x_axis.sort()
  x_axis = [x_axis[0] - 1] + x_axis + [x_axis[-1] + 1]

  cells = [[Cell(x1, y1, x2, y2)
            for x1, x2 in zip(x_axis[:-1], x_axis[1:])]
           for y1, y2 in zip(y_axis[:-1], y_axis[1:])]

  for b in vborders:
    y_idx = bisect.bisect_left(y_axis, b.y)
    x_idx1 = bisect.bisect_left(x_axis, b.x1)
    x_idx2 = bisect.bisect_right(x_axis, b.x2) - 1

    for x_idx in range(x_idx1, x_idx2):
      cells[y_idx - 1][x_idx].down = False
      cells[y_idx][x_idx].up = False

  for b in hborders:
    x_idx = bisect.bisect_left(x_axis, b.x)
    y_idx1 = bisect.bisect_left(y_axis, b.y1)
    y_idx2 = bisect.bisect_right(y_axis, b.y2) - 1

    for y_idx in range(y_idx1, y_idx2):
      cells[y_idx][x_idx - 1].right = False
      cells[y_idx][x_idx].left = False

  queue = collections.deque()
  area = 0

  x = bisect.bisect_right(x_axis, 0.5) - 1
  y = bisect.bisect_right(y_axis, 0.2) - 1
  queue.append((x, y))

  while len(queue) != 0:
    x, y = queue.popleft()

    if x == 0 or x == len(x_axis) - 1 or y == 0 or y == len(y_axis):
      print('INF')
      return

    c = cells[y][x]

    if c.checked:
      continue

    area += c.area()
    c.checked = True

    if c.up:
      queue.append((x, y - 1))

    if c.down:
      queue.append((x, y + 1))

    if c.left:
      queue.append((x - 1, y))

    if c.right:
      queue.append((x + 1, y))

  print(area)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#168 - F
import sys
import numpy as np
#from numba import njit


def main():
    N, M = map(int, sys.stdin.buffer.readline().split())
    LineData = np.int64(sys.stdin.buffer.read().split())

    INF = 10**9 + 1

    LineData = LineData.reshape(-1, 3)
    A, B, C = LineData[:N].T
    D, E, F = LineData[N:].T
    #X = np.unique(np.concatenate([D, [-INF, 0, INF]]))
    #Y = np.unique(np.concatenate([C, [-INF, 0, INF]]))
    X = np.unique(np.concatenate([D, [-INF, INF]]))
    Y = np.unique(np.concatenate([C, [-INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B, 'right') - 1
    C = np.searchsorted(Y, C)
    D = np.searchsorted(X, D)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F, 'right') - 1

    area = cal_area(A, B, C, D, E, F, X, Y)

    if area == 0:
        print("INF")
    else:
        print(area)


#@njit
def cal_area(A, B, C, D, E, F, X, Y):
    x = np.searchsorted(X, 0, 'right') - 1
    y = np.searchsorted(Y, 0, 'right') - 1

    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    A = A.tolist()
    B = B.tolist()
    C = C.tolist()
    D = D.tolist()
    E = E.tolist()
    F = F.tolist()
    X = X.tolist()
    Y = Y.tolist()
    DX = DX.tolist()
    DY = DY.tolist()

    LenX = len(X) - 1
    LenY = len(Y) - 1

    visit = [[False] * LenY for _ in range(LenX)]
    visit[x][y] = True
    area = 0
    queue = [(x, y)]

    LineX = [[False] * LenY for _ in range(LenX)]
    LineY = [[False] * LenY for _ in range(LenX)]

    for x1, x2, y in zip(A, B, C):
        for x in range(x1, x2):
            LineY[x][y] = True

    for x, y1, y2 in zip(D, E, F):
        for y in range(y1, y2):
            LineX[x][y] = True

    while queue:
        x, y = queue.pop()

        if x == 0 or x == LenX or y == 0 or y == LenY:
            area = 0
            break
        
        area += DX[x] * DY[y]

        if not LineX[x][y] and not visit[x - 1][y]:
            visit[x - 1][y] = True
            queue.append((x - 1, y))
        if not LineY[x][y] and not visit[x][y - 1]:
            visit[x][y - 1] = True
            queue.append((x, y - 1))
        if not LineX[x + 1][y] and not visit[x + 1][y]:
            visit[x + 1][y] = True
            queue.append((x + 1, y))
        if not LineY[x][y + 1] and not visit[x][y + 1]:
            visit[x][y + 1] = True
            queue.append((x, y + 1))

    return area


if __name__ == '__main__':
	main()

sys.exit()

Submission status: Runtime Error

Solution code:
I=lambda:[int(i) for i in input().split()]

ans=0
inf=1<<65
n,m=I()
X=set([0,inf,-inf])
Y=set([0,inf,-inf])
R=[]
H=[]
for i in range(n):
    a,b,c=I()
    R.append(((a,b),c))
    Y.add(c)
    X.add(a)
    X.add(b)
 
n+=2
R.append(((-inf,inf),inf))
R.append(((-inf,inf),-inf))
 
for i in range(m):
    a,b,c=I()
    H.append((a,(b,c)))
    X.add(a)
    Y.add(b)
    Y.add(c)
 
m+=2
H.append((inf,(-inf,inf)))
H.append((-inf,(-inf,inf)))

xdc={}
c=1
for j in sorted(X):
    xdc[c]=j
    c+=1
nx=c-1
 
ydc={}
c=1
for j in sorted(Y):
    ydc[c]=j
    c+=1
ny=c-1
 
xdcr=dict(zip(xdc.Ralues(),xdc.keys()))
ydcr=dict(zip(ydc.Ralues(),ydc.keys()))
 
mpy=[[0]*(nx+1+1) for i in range(ny+1+1)]
mpx=[i[:]for i in mpy]

for (a,b),c in R:
    mpx[ydcr[c]][xdcr[a]]+=1
    mpx[ydcr[c]][xdcr[b]]+=-1
for i in range(ny+1):
    for j in range(nx):
        mpx[i][j+1]+=mpx[i][j]
        
for d,(e,f) in H:
    mpy[ydcr[e]][xdcr[d]]+=1
    mpy[ydcr[f]][xdcr[d]]+=-1
for j in range(nx+1):
    for i in range(ny):
        mpy[i+1][j]+=mpy[i][j]

R=[[0]*(nx+1) for i in range(ny+1)]
q=[(xdcr[0],ydcr[0])]
R[ydcr[0]][xdcr[0]]=1

while q:
    cx,cy=q.pop()
    ans+=(xdc[cx]-xdc[cx+1])*(ydc[cy]-ydc[cy+1])
    for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
        nbx=cx+dx
        nby=cy+dy
        if (0>nbx>=nx)or(0>nby>=ny)or R[nby][nbx]==1:
            continue
        if dy!=0:
            if mpx[-~dy//2+cy][cx]==0:
                q.append((nbx,nby))
                R[nby][nbx]=1
        else:
            if mpy[cy][-~dx//2+cx]==0:
                q.append((nbx,nby))
                R[nby][nbx]=1
if ans>=inf:
    ans='INF'
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())

x = set([0])
y = set([0])
h, v = [], []
for _ in range(n):
    a, b, c = map(int, input().split())
    y.add(a)
    y.add(b)
    x.add(c)
    v.append((a, b, c))

for _ in range(m):
    d, e, f = map(int, input().split())
    y.add(d)
    x.add(e)
    x.add(f)
    h.append((d, e, f))

x, y = sorted(x), sorted(y)
lx, ly = len(x)*2, len(y)*2
dx, dy = {v:i*2 for i,v in enumerate(x)}, {v:i*2 for i, v in enumerate(y)}

m = [[0 for _ in range(lx)] for _ in range(ly)]

for a, b, c in v:
    xx = dx[c]
    for yy in range(dy[a], dy[b]+1):
        m[yy][xx] = 1

for d, e, f in h:
    yy = dy[d]
    for xx in range(dx[e], dx[f]+1):
        m[yy][xx] = 1

ans = 0
px = [1, 0, -1, 0]
py = [0, 1, 0, -1]

def _s(xx, yy):
    global ans
    m[yy][xx] = 1
    if xx == 0 or xx == lx-2 or yy == 0 or yy == ly-2:
        print('INF')
        exit(0)
    for i in range(4):
        xxx, yyy = xx+px[i], yy+py[i]
        if m[yyy][xxx] == 1:
            continue
        if xxx % 2 != 0 and yyy % 2 != 0:
            x1, y1 = xxx // 2, yyy // 2
            x2, y2 = x1+1, y1+1
            ans = ans + (x[x2]-x[x1]) * (y[y2]-y[y1])
        _s(xxx, yyy)


_s(dx[0], dy[0])
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())

x = set([0])
y = set([0])
h, v = [], []
for _ in range(n):
    a, b, c = map(int, input().split())
    y.add(a)
    y.add(b)
    x.add(c)
    v.append((a, b, c))

for _ in range(m):
    d, e, f = map(int, input().split())
    y.add(d)
    x.add(e)
    x.add(f)
    h.append((d, e, f))

x, y = sorted(x), sorted(y)
lx, ly = len(x)*2, len(y)*2
dx, dy = {v:i*2 for i,v in enumerate(x)}, {v:i*2 for i, v in enumerate(y)}

m = [[0 for _ in range(lx)] for _ in range(ly)]

for a, b, c in v:
    xx = dx[c]
    for yy in range(dy[a], dy[b]+1):
        m[yy][xx] = 1

for d, e, f in h:
    yy = dy[d]
    for xx in range(dx[e], dx[f]+1):
        m[yy][xx] = 1

ans = 0
px = [1, 0, -1, 0]
py = [0, 1, 0, -1]

def _s(xx, yy):
    global ans
    m[yy][xx] = 1
    if xx == 0 or xx == lx-1 or yy == 0 or yy == ly-1:
        print('INF')
        exit(0)
    for i in range(4):
        xxx, yyy = xx+px[i], yy+py[i]
        if m[yyy][xxx] == 1:
            continue
        if xxx % 2 != 0 and yyy % 2 != 0:
            x1, y1 = xxx // 2, yyy // 2
            x2, y2 = x1+1, y1+1
            ans = ans + (x[x2]-x[x1]) * (y[y2]-y[y1])
        _s(xxx, yyy)


_s(dx[0], dy[0])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

x = set([0])
y = set([0])
h, v = [], []
for _ in range(n):
    a, b, c = map(int, input().split())
    y.add(a)
    y.add(b)
    x.add(c)
    v.append((a, b, c))

for _ in range(m):
    d, e, f = map(int, input().split())
    y.add(d)
    x.add(e)
    x.add(f)
    h.append((d, e, f))

x, y = sorted(x), sorted(y)
lx, ly = len(x)*2, len(y)*2
dx, dy = {v:i*2 for i,v in enumerate(x)}, {v:i*2 for i, v in enumerate(y)}

m = [[0 for _ in range(lx)] for _ in range(ly)]

for a, b, c in v:
    xx = dx[c]
    for yy in range(dy[a], dy[b]+1):
        m[yy][xx] = 1

for d, e, f in h:
    yy = dy[d]
    for xx in range(dx[e], dx[f]+1):
        m[yy][xx] = 1

ans = 0
px = [1, 0, -1, 0]
py = [0, 1, 0, -1]

def _s(xx, yy):
    global ans
    m[yy][xx] = 1
    if xx == 0 or xx == lx-1 or yy == 0 or yy == ly-1:
        print('INF')
        exit(0)
    for i in range(4):
        xxx, yyy = xx+px[i], yy+py[i]
        if m[yyy][xxx] == 1:
            continue
        if xxx % 2 != 0 and yyy % 2 != 0:
            x1, y1 = xxx // 2, yyy // 2
            x2, y2 = x1+1, y1+1
            ans = ans + (x[x2]-x[x1]) * (y[y2]-y[y1])
        _s(xxx, yyy)


_s(dx[0], dy[0])
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

x = set([0])
y = set([0])
h, v = [], []
for _ in range(n):
    a, b, c = map(int, input().split())
    y.add(a)
    y.add(b)
    x.add(c)
    v.append((a, b, c))

for _ in range(m):
    d, e, f = map(int, input().split())
    y.add(d)
    x.add(e)
    x.add(f)
    h.append((d, e, f))

x, y = sorted(x), sorted(y)
lx, ly = len(x)*2, len(y)*2
dx, dy = {v:i*2 for i,v in enumerate(x)}, {v:i*2 for i, v in enumerate(y)}

m = [[0 for _ in range(lx)] for _ in range(ly)]

for a, b, c in v:
    xx = dx[c]
    for yy in range(dy[a], dy[b]+1):
        m[yy][xx] = 1

for d, e, f in h:
    yy = dy[d]
    for xx in range(dx[e], dx[f]+1):
        m[yy][xx] = 1

ans = 0
px = [1, 0, -1, 0]
py = [0, 1, 0, -1]

def _s(xx, yy):
    global ans
    m[yy][xx] = 1
    print(xx, yy)
    if xx == 0 or xx == lx-1 or yy == 0 or yy == ly-1:
        print('INF')
        exit(0)
    for i in range(4):
        xxx, yyy = xx+px[i], yy+py[i]
        if m[yyy][xxx] == 1:
            continue
        if xxx % 2 != 0 and yyy % 2 != 0:
            x1, y1 = xxx // 2, yyy // 2
            x2, y2 = x1+1, y1+1
            ans = ans + (x[x2]-x[x1]) * (y[y2]-y[y1])
        _s(xxx, yyy)


_s(dx[0], dy[0])
print(ans)

Submission status: Runtime Error

Solution code:
# F - . (Single Dot)

from collections import deque
import bisect
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
INF = 10**9 + 1
s_X = set([-INF, 0, INF])
s_Y = set([-INF, 0, INF])

def compress(s):
    ls = list(s)
    ls.sort()
    return {e: i for i, e in enumerate(ls)}

ABC = []
for i in range(N):
    A, B, C = map(int, readline().split())
    ABC.append((A, B, C))
    s_Y.add(C)

DEF = []
for i in range(M):
    D, E, F= map(int, readline().split())
    DEF.append((D, E, F))
    s_X.add(D)

mapX = compress(s_X)
mapY = compress(s_Y)
l_X = list(mapX.keys())
l_Y = list(mapY.keys())
maxX = len(mapX)*2
maxY = len(mapY)*2

W = [[False] * maxY for _ in range(maxX)]

for A, B, C in ABC:
    A = mapX[l_X[bisect.bisect_left(l_X, A)]]
    B = mapX[l_X[bisect.bisect_right(l_X, B)-1]]
    C = mapY[C]
    A *= 2
    B *= 2
    C *= 2
    for j in range(A, B+1):
        W[j][C] = True

for D, E, F in DEF:
    D = mapX[D]
    E = mapY[l_Y[bisect.bisect_left(l_Y, E)]]
    F = mapY[l_Y[bisect.bisect_right(l_Y, F)-1]]
    D *= 2
    E *= 2
    F *= 2
    for j in range(E, F+1):
        W[D][j] = True

q = deque()
q.append((mapX[0]*2, mapY[0]*2))
W[mapX[0]*2][mapY[0]*2] = True
ans = 0
b_ans = True
while q:
    x, y = q.pop()
    if x == maxX or x == 0 or y == maxY or y == 0:
        b_ans = False
        break
    for (vx, vy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx = x + vx
        ny = y + vy
        if W[nx][ny] == False:
            W[nx][ny] == True
            for (px, py) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nx +=  px
                ny +=  py
                if W[nx][ny] == False:
                    if nx%2==1 and ny%2==1:
                        ex = l_X[(nx+1)//2] - l_X[(nx-1)//2]
                        ey = l_Y[(ny+1)//2] - l_Y[(ny-1)//2]
                        ans += ex * ey
                        #print(nx, ny, ans)
                    q.append((nx, ny))
                    W[nx][ny] = True

if b_ans == True:
    print(ans)
else:
    print('INF')

Submission status: Runtime Error

Solution code:
# F - . (Single Dot)

from collections import deque
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
INF = 10**9 + 1
s_X = set()
s_Y = set()
s_X.add(0)
s_X.add(INF)
s_X.add(-INF)
s_Y.add(0)
s_Y.add(INF)
s_Y.add(-INF)

def compress(s):
    ls = list(s)
    ls.sort()
    return {e: i for i, e in enumerate(ls)}

ABC = []
for i in range(N):
    A, B, C = map(int, readline().split())
    ABC.append((A, B, C))
    s_Y.add(C)

DEF = []
for i in range(M):
    D, E, F= map(int, readline().split())
    DEF.append((D, E, F))
    s_X.add(D)

mapX = compress(s_X)
mapY = compress(s_Y)
l_X = list(mapX.keys())
l_Y = list(mapY.keys())
maxX = len(mapX)*2
maxY = len(mapY)*2

W = [[0] * maxY for _ in range(maxX)]

for A, B, C in ABC:
    A = mapX[A]
    B = mapX[B]
    C = mapY[C]
    A *= 2
    B *= 2
    C *= 2
    for j in range(A, B+1):
        W[j][C] = 1

for D, E, F in DEF:
    D = mapX[D]
    E = mapY[E]
    F = mapY[F]
    D *= 2
    E *= 2
    F *= 2
    for j in range(E, F+1):
        W[D][j] = 1

#print(W)
q = deque()
q.append((mapX[0]*2, mapY[0]*2))
W[mapX[0]*2][mapY[0]*2] = 1
ans = 0
b_ans = True
while q:
    x, y = q.pop()
    if x == maxX or x == 0 or y == maxY or y == 0:
        b_ans = False
        break
    for (vx, vy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx = x + vx
        ny = y + vy
        if W[nx][ny]==0:
            if nx%2==1 and ny%2==1:
                ex = l_X[(nx+1)//2] - l_X[(nx-1)//2]
                ey = l_Y[(ny+1)//2] - l_Y[(ny-1)//2]
                ans += ex * ey
                #print(nx, ny, ans)
            q.append((nx, ny))
            W[nx][ny] = 1

if b_ans == True:
    print(ans)
else:
    print('INF')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys, bisect
from queue import Queue
from pprint import pprint
sys.setrecursionlimit(300000)


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]", E: "List[int]", F: "List[int]"):
    sx, sy = set(), set()
    for i in range(N):
        sx.add(A[i])
        sx.add(B[i])
        sy.add(C[i])
    for i in range(M):
        sx.add(D[i])
        sy.add(E[i])
        sy.add(F[i])

    sx = list(sx)
    sy = list(sy)
    sx.sort()
    sy.sort()
    h, w = len(sy) * 2, len(sx) * 2
    g = [[0] * w for _ in range(h)]
    for i in range(N):
        ax = bisect.bisect_left(sx, A[i]) * 2
        bx = bisect.bisect_left(sx, B[i]) * 2
        y  = bisect.bisect_left(sy, C[i]) * 2
        for x in range(ax, bx + 1):
            g[y][x] = 1
    for i in range(M):
        x  = bisect.bisect_left(sx, D[i]) * 2
        ay = bisect.bisect_left(sy, E[i]) * 2
        by = bisect.bisect_left(sy, F[i]) * 2
        for y in range(ay, by + 1):
            g[y][x] = 1

    x = bisect.bisect_left(sx, 0) * 2
    y = bisect.bisect_left(sy, 0) * 2
    g[y][x] = 2
    q = Queue()
    q.put((x, y))
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    ret = 0
    #pprint(g)
    while not q.empty():
        x, y = q.get()
        if x % 2 and y % 2:
            xx = sx[x // 2 + 1] - sx[x // 2]
            yy = sy[y // 2 + 1] - sy[y // 2]
            ret += xx * yy
        for k in range(len(dx)):
            tx, ty = x + dx[k], y + dy[k]
            if 0 <= tx < w and 0 <= ty < h and g[ty][tx] == 0:
                if tx == 0 or tx == w - 1 or ty == 0 or ty == h - 1:
                    print('INF')
                    return
                g[ty][tx] = 2
                q.put((tx, ty))
    #pprint(g)

    #ret = 0
    #for y in range(h):
    #    for x in range(w):
    #        if g[y][x] != 2:
    #            continue
    #        if x == 0 or x == w - 1 or y == 0 or y == h - 1:
    #            print('INF')
    #            return
    #        if x % 2 == 0 or y % 2 == 0:
    #            continue
    #        xx = sx[x // 2 + 1] - sx[x // 2]
    #        yy = sy[y // 2 + 1] - sy[y // 2]
    #        ret += xx * yy
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    C = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    D = [int()] * (M)  # type: "List[int]"
    E = [int()] * (M)  # type: "List[int]"
    F = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        D[i] = int(next(tokens))
        E[i] = int(next(tokens))
        F[i] = int(next(tokens))
    solve(N, M, A, B, C, D, E, F)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys, bisect
from queue import Queue
from pprint import pprint
sys.setrecursionlimit(300000)


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]", E: "List[int]", F: "List[int]"):
    sx, sy = [], []
    for i in range(N):
        sx.append(A[i])
        sx.append(B[i])
        sy.append(C[i])
    for i in range(M):
        sx.append(D[i])
        sy.append(E[i])
        sy.append(F[i])

    sx.sort()
    sy.sort()
    h, w = len(sy) * 2, len(sx) * 2
    g = [[0] * w for _ in range(h)]
    for i in range(N):
        ax = bisect.bisect_left(sx, A[i]) * 2
        bx = bisect.bisect_left(sx, B[i]) * 2
        y  = bisect.bisect_left(sy, C[i]) * 2
        for x in range(ax, bx + 1):
            g[y][x] = 1
    for i in range(M):
        x  = bisect.bisect_left(sx, D[i]) * 2
        ay = bisect.bisect_left(sy, E[i]) * 2
        by = bisect.bisect_left(sy, F[i]) * 2
        for y in range(ay, by + 1):
            g[y][x] = 1

    x = bisect.bisect_left(sx, 0) * 2
    y = bisect.bisect_left(sy, 0) * 2
    g[y][x] = 2
    q = Queue()
    q.put((x, y))
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    ret = 0
    #pprint(g)
    while not q.empty():
        x, y = q.get()
        if x % 2 and y % 2:
            xx = sx[x // 2 + 1] - sx[x // 2]
            yy = sy[y // 2 + 1] - sy[y // 2]
            ret += xx * yy
        for k in range(len(dx)):
            tx, ty = x + dx[k], y + dy[k]
            if 0 <= tx < w and 0 <= ty < h and g[ty][tx] == 0:
                if tx == 0 or tx == w - 1 or ty == 0 or ty == h - 1:
                    print('INF')
                    return
                g[ty][tx] = 2
                q.put((tx, ty))
    #pprint(g)

    #ret = 0
    #for y in range(h):
    #    for x in range(w):
    #        if g[y][x] != 2:
    #            continue
    #        if x == 0 or x == w - 1 or y == 0 or y == h - 1:
    #            print('INF')
    #            return
    #        if x % 2 == 0 or y % 2 == 0:
    #            continue
    #        xx = sx[x // 2 + 1] - sx[x // 2]
    #        yy = sy[y // 2 + 1] - sy[y // 2]
    #        ret += xx * yy
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    C = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    D = [int()] * (M)  # type: "List[int]"
    E = [int()] * (M)  # type: "List[int]"
    F = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        D[i] = int(next(tokens))
        E[i] = int(next(tokens))
        F[i] = int(next(tokens))
    solve(N, M, A, B, C, D, E, F)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# F - . (Single Dot)

from collections import defaultdict
from collections import deque
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
W = defaultdict(int)

s_X = set()
s_Y = set()
s_X.add(0)
s_Y.add(0)

def compress(s):
    ls = list(s)
    ls.sort()
    return {e: i for i, e in enumerate(ls)}

ABC = []
for i in range(N):
    A, B, C = map(int, readline().split())
    ABC.append((A, B, C))
    s_X.add(A)
    s_X.add(B)
    s_Y.add(C)

DEF = []
for i in range(M):
    D, E, F= map(int, readline().split())
    DEF.append((D, E, F))
    s_X.add(D)
    s_Y.add(E)
    s_Y.add(F)

mapX = compress(s_X)
mapY = compress(s_Y)
l_X = list(mapX.keys())
l_Y = list(mapY.keys())
maxX = len(mapX)*2
maxY = len(mapY)*2

for A, B, C in ABC:
    A = mapX[A]
    B = mapX[B]
    C = mapY[C]
    A *= 2
    B *= 2
    C *= 2
    for j in range(A, B+1):
        W[(j, C)] = -1

for D, E, F in DEF:
    D = mapX[D]
    E = mapY[E]
    F = mapY[F]
    D *= 2
    E *= 2
    F *= 2
    for j in range(E, F+1):
        W[(D, j)] = -1

#print(W)
q = deque()
q.append((mapX[0]*2, mapY[0]*2))
W[(mapX[0]*2, mapY[0]*2)] = -1
ans = 0
b_ans = True
while len(q) > 0:
    x, y = q.pop()
    if x >= maxX or x <= 0 or y >= maxY or y <= 0:
        b_ans = False
        break
    for (vx, vy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx = x + vx
        ny = y + vy
        if (nx, ny) not in W:
            if nx%2==1 and ny%2==1:
                ex = l_X[(nx+1)//2] - l_X[(nx-1)//2]
                ey = l_Y[(ny+1)//2] - l_Y[(ny-1)//2]
                ans += ex * ey
                #print(nx, ny, ans)
            q.append((nx, ny))
            W[(nx, ny)] = -1

if b_ans == True:
    print(ans)
else:
    print('INF')

Submission status: Runtime Error

Solution code:
# F - . (Single Dot)

from collections import defaultdict
from collections import deque
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
INF = 2 * 10**9 + 1
W = defaultdict(int)

s_X = set()
s_Y = set()
s_X.add(0)
s_Y.add(0)

def compress(s):
    ls = list(s)
    ls.sort()
    return {e: i for i, e in enumerate(ls)}

ABC = []
for i in range(N):
    A, B, C = map(int, readline().split())
    ABC.append((A, B, C))
    s_X.add(A)
    s_X.add(B)
    s_Y.add(C)

DEF = []
for i in range(M):
    D, E, F= map(int, readline().split())
    DEF.append((D, E, F))
    s_X.add(D)
    s_Y.add(E)
    s_Y.add(F)

mapX = compress(s_X)
mapY = compress(s_Y)
l_X = list(mapX.keys())
l_Y = list(mapY.keys())
maxX = len(mapX)*2
maxY = len(mapY)*2

for A, B, C in ABC:
    A = mapX[A]
    B = mapX[B]
    C = mapY[C]
    A *= 2
    B *= 2
    C *= 2
    for j in range(A, B+1):
        W[(j, C)] = -1

for D, E, F in DEF:
    D = mapX[D]
    E = mapY[E]
    F = mapY[F]
    D *= 2
    E *= 2
    F *= 2
    for j in range(E, F+1):
        W[(D, j)] = -1

#print(W)
q = deque()
q.append((mapX[0]*2, mapY[0]*2))
W[(mapX[0]*2, mapY[0]*2)] = -1
ans = 0
b_ans = True
while len(q) > 0:
    x, y = q.pop()
    if x > maxX or x < 0 or y > maxY or y < 0:
        b_ans = False
        break
    for (vx, vy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        nx = x + vx
        ny = y + vy
        if (nx, ny) not in W:
            if nx%2==1 and ny%2==1:
                ex = l_X[(nx+1)//2] - l_X[(nx-1)//2]
                ey = l_Y[(ny+1)//2] - l_Y[(ny-1)//2]
                ans += ex * ey
                #print(nx, ny, ans)
            q.append((nx, ny))
            W[(nx, ny)] = -1

if b_ans == True:
    print(ans)
else:
    print('INF')