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: Accepted

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) - 1:
      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: Accepted

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, 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)
    LenY = len(Y)

    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

    LenX -= 1
    LenY -= 1
    
    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]
        
        x1 = x - 1
        if not LineX[x][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y - 1
        if not LineY[x][y] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))
        x1 = x + 1
        if not LineX[x1][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y + 1
        if not LineY[x][y1] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))

    return area


if __name__ == '__main__':
	main()

sys.exit()

Submission status: Accepted

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, 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)
    LenY = len(Y)

    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 i in range(len(A)):
    #    y = C[i]
    #    for x in range(A[i], B[i]):
    #        LineY[x][y] = True

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

    LenX -= 1
    LenY -= 1
    
    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]
        
        x1 = x - 1
        if not LineX[x][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y - 1
        if not LineY[x][y] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))
        x1 = x + 1
        if not LineX[x1][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y + 1
        if not LineY[x][y1] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))

    return area


if __name__ == '__main__':
	main()

sys.exit()

Submission status: Accepted

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)
    LenY = len(Y)

    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 i in range(len(A)):
        y = C[i]
        for x in range(A[i], B[i]):
            LineY[x][y] = True

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

    LenX -= 1
    LenY -= 1
    
    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]
        
        x1 = x - 1
        if not LineX[x][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y - 1
        if not LineY[x][y] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))
        x1 = x + 1
        if not LineX[x1][y] and not visit[x1][y]:
            visit[x1][y] = True
            queue.append((x1, y))
        y1 = y + 1
        if not LineY[x][y1] and not visit[x][y1]:
            visit[x][y1] = True
            queue.append((x, y1))

    return area


if __name__ == '__main__':
	main()

sys.exit()

Submission status: Accepted

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)
    LenY = len(Y)

    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 i in range(len(A)):
        y = C[i]
        for x in range(A[i], B[i]):
            LineY[x][y] = True

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

    LenX -= 1
    LenY -= 1
    
    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: Accepted

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)
    LenY = len(Y)

    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 i in range(len(A)):
        y = C[i]
        for x in range(A[i], B[i]):
            LineY[x][y] = True

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

    LenX -= 1
    LenY -= 1
    
    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: Accepted

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)
    LenY = len(Y)

    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

    LenX -= 1
    LenY -= 1
    
    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: Accepted

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)
    LenY = len(Y)

    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 - 1 or y == 0 or y == LenY - 1:
            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: Accepted

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)
    LenY = len(Y)

    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 - 1 or y == 0 or y == LenY - 1:
            area = 0
            break
        
        #area += (X[x + 1] - X[x]) * (Y[y + 1] - Y[y])
        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: Accepted

Solution code:
import sys
from typing import Iterable, Tuple, Union

class nd (object):
	getter = (
		lambda a, i: a,
		lambda a, i: a[i[0]],
		lambda a, i: a[i[0]][i[1]],
		lambda a, i: a[i[0]][i[1]][i[2]],
		lambda a, i: a[i[0]][i[1]][i[2]][i[3]],
		lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]],
		lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]][i[5]],
	)
	class _setter (object):
		def __getitem__(self, n : int):
			setter_getter = nd.getter[n-1]
			def setter(a, i, v):
				setter_getter(a, i[:-1])[i[-1]] = v
			return setter
	setter = _setter()
	initializer = (
		lambda s, v: [v] * s,
		lambda s, v: [v] * s[0],
		lambda s, v: [[v] * s[1] for _ in range(s[0])],
		lambda s, v: [[[v] * s[2] for _ in range(s[1])] for _ in range(s[0])],
		lambda s, v: [[[[v] * s[3] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
		lambda s, v: [[[[[v] * s[4] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
		lambda s, v: [[[[[[v] * s[5] for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
	)
	shape_getter = (
		lambda a: len(a),
		lambda a: (len(a),),
		lambda a: (len(a), len(a[0])),
		lambda a: (len(a), len(a[0]), len(a[0][0])),
		lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0])),
		lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0])),
		lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0]), len(a[0][0][0][0][0])),
	)
	indices_iterator = (
		lambda s: iter(range(s)),
		lambda s: ((i,) for i in range(s[0])),
		lambda s: ((i, j) for j in range(s[1]) for i in range(s[0])),
		lambda s: ((i, j, k) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
		lambda s: ((i, j, k, l) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
		lambda s: ((i, j, k, l, m) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
		lambda s: ((i, j, k, l, m, n) for n in range(s[5]) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
	)
	iterable_product = (
		lambda s: iter(s),
		lambda s: ((i,) for i in s[0]),
		lambda s: ((i, j) for j in s[1] for i in s[0]),
		lambda s: ((i, j, k) for k in s[2] for j in s[1] for i in s[0]),
		lambda s: ((i, j, k, l) for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
		lambda s: ((i, j, k, l, m) for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
		lambda s: ((i, j, k, l, m, n) for n in s[5] for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
	)
	
	@classmethod
	def full(cls, fill_value, shape : Union[int, Tuple[int], Iterable[int]]):
		if isinstance(shape, int):
			return cls.initializer[0](shape, fill_value)
		elif not isinstance(shape, tuple):
			shape = tuple(shape)
		return cls.initializer[len(shape)](shape, fill_value)
	
	@classmethod
	def fromiter(cls, iterable : Iterable, ndim=1):
		if ndim == 1:
			return list(iterable)
		else:
			return list(map(cls.fromiter, iterable))
	
	@classmethod
	def nones(cls, shape : Union[int, Tuple[int], Iterable[int]]):
		return cls.full(None, shape)
	
	@classmethod
	def zeros(cls, shape : Union[int, Tuple[int], Iterable[int]], type=int):
		return cls.full(type(0), shape)
	
	@classmethod
	def ones(cls, shape : Union[int, Tuple[int], Iterable[int]], type=int):
		return cls.full(type(1), shape)
	
	class _range (object):
		def __getitem__(self, shape : Union[int, slice, Tuple[Union[int, slice]]]):
			if isinstance(shape, int):
				return iter(range(shape))
			elif isinstance(shape, slice):
				return iter(range(shape.stop)[shape])
			else:
				shape = tuple(range(s.stop)[s] for s in shape)
				return nd.iterable_product[len(shape)](shape)
		def __call__(self, shape : Union[int, slice, Tuple[Union[int, slice]]]):
			return self[shape]
	range = _range()



def bytes_to_str(x : bytes):
	return x.decode('utf-8')

def inputs(func=bytes_to_str, sep=None, maxsplit=-1):
	return map(func, sys.stdin.buffer.readline().split(sep=sep, maxsplit=maxsplit))

def inputs_1d(func=bytes_to_str, **kwargs):
	return nd.fromiter(inputs(func, **kwargs))

def inputs_2d(nrows : int, func=bytes_to_str, **kwargs):
	return nd.fromiter(
		(inputs(func, **kwargs) for _ in range(nrows)),
		ndim=2
	)

def inputs_2d_T(nrows : int, func=bytes_to_str, **kwargs):
	return nd.fromiter(
		zip(*(inputs(func, **kwargs) for _ in range(nrows))),
		ndim=2
	)

from typing import Optional


class DepthFirstSearch (object):
	__slots__ = [
		'shape',
		'pushed',
		'_stack',
		'_getter',
		'_setter'
	]
	
	def __init__(self, shape : Union[int, Iterable[int]]):
		self.shape = (shape,) if isinstance(shape, int) else tuple(shape)
		self.pushed = nd.zeros(self.shape, type=bool)
		self._stack = []
		self._getter = nd.getter[len(self.shape)]
		self._setter = nd.setter[len(self.shape)]
	
	def push(self, position : Tuple[int]):
		if not self._getter(self.pushed, position):
			self._setter(self.pushed, position, True)
			self._stack.append(position)
	
	def peek(self) -> Optional[Tuple[int]]:
		return self._stack[-1] if self._stack else None
	
	def pop(self) -> Optional[Tuple[int]]:
		return self._stack.pop() if self._stack else None
	
	def __bool__(self):
		return bool(self._stack)

DFS = DepthFirstSearch

from bisect import bisect_left, bisect_right
from collections import deque


N, M = inputs(int)
A, B, C = inputs_2d_T(N, int)
D, E, F = inputs_2d_T(M, int)
xs = sorted(set(C))
ys = sorted(set(D))

x_guard = nd.zeros((len(xs)+1, len(ys)+1), type=bool)
y_guard = nd.zeros((len(xs)+1, len(ys)+1), type=bool)

for a, b, c in zip(A, B, C):
	c = bisect_right(xs, c)
	a = bisect_left(ys, a) + 1
	b = bisect_right(ys, b)
	for y in range(a, b):
		x_guard[c][y] = True

for d, e, f in zip(D, E, F):
	d = bisect_right(ys, d)
	e = bisect_left(xs, e) + 1
	f = bisect_right(xs, f)
	for x in range(e, f):
		y_guard[x][d] = True

cow = (
	bisect_right(xs, 0),
	bisect_right(ys, 0)
)

bfs = DepthFirstSearch(shape=(len(xs)+1, len(ys)+1))
bfs.push(cow)

area = 0
while bfs:
	xi, yi = bfs.pop()
	
	if 0 < xi < len(xs) and 0 < yi < len(ys):
		area += (xs[xi] - xs[xi-1]) * (ys[yi] - ys[yi-1])
		if not x_guard[xi][yi]:
			bfs.push((xi-1, yi))
		if not x_guard[xi+1][yi]:
			bfs.push((xi+1, yi))
		if not y_guard[xi][yi]:
			bfs.push((xi, yi-1))
		if not y_guard[xi][yi+1]:
			bfs.push((xi, yi+1))
	else:
		area = 'INF'
		break

print(area)