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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = [-1]*N

    def root(self, i):
        if self.tree[i] < 0:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[y] = x
        return x == y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    # 1. 座圧
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    H = len(my)
    W = len(mx)

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(W*H)

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.unite(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.unite(i+(j+1)*W, i+j*W)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.same(ushi, i+j*W):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    # 1. 座圧
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i
    H = len(my)
    W = len(mx)

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*H for _ in range(W)]
    segy = [[0]*H for _ in range(W)]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(W-1):
        for j in range(H):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(W):
        for j in range(H-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(W*H)

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(W):
        for j in range(H):
            if i+1 < W and segy[i][j] == 0:
                uf.unite(i+j*W, i+1+j*W)
            if j+1 < H and segx[i][j] == 0:
                uf.unite(i+(j+1)*W, i+j*W)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*W
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(W-1):
        for j in range(H-1):
            if uf.same(ushi, i+j*W):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    # 1. 座圧
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(mx):
        invx[x] = i
    for i, y in enumerate(my):
        invy[y] = i

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*len(my) for _ in range(len(mx))]
    segy = [[0]*len(my) for _ in range(len(mx))]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(len(mx)-1):
        for j in range(len(my)):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(len(invx)):
        for j in range(len(invy)-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(len(mx)*len(my))

    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    H = len(mx)
    for i in range(len(mx)):
        for j in range(len(my)):
            if i+1 < len(mx) and segy[i][j] == 0:
                uf.unite(i+j*H, i+1+j*H)
            if j+1 < len(my) and segx[i][j] == 0:
                uf.unite(i+(j+1)*H, i+j*H)

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = invx[0]+invy[0]*H
    if uf.same(ushi, 0):
        print("INF")
        return

    area = 0
    for i in range(len(mx)-1):
        for j in range(len(my)-1):
            if uf.same(ushi, i+j*H):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    A, B, C = [0]*N, [0]*N, [0]*N
    for i in range(N):
        a, b, c = map(int, readline().split())
        A[i], B[i], C[i] = a, b, c
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    D, E, F = [0]*M, [0]*M, [0]*M
    for i in range(M):
        d, e, f = map(int, readline().split())
        D[i], E[i], F[i] = d, e, f
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    # 1. 座圧
    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(sorted(x_coord)):
        invx[x] = i
    for i, y in enumerate(sorted(y_coord)):
        invy[y] = i

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*len(my) for _ in range(len(mx))]
    segy = [[0]*len(my) for _ in range(len(mx))]

    for a, b, c in zip(A, B, C):
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(len(mx)-1):
        for j in range(len(my)):
            segx[i+1][j] += segx[i][j]

    for d, e, f in zip(D, E, F):
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(len(invx)):
        for j in range(len(invy)-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(len(mx)*len(my))

    def idx(x, y):
        return x+y*len(mx)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(len(mx)):
        for j in range(len(my)):
            if i+1 < len(mx) and segy[i][j] == 0:
                uf.unite(idx(i, j), idx(i+1, j))
            if j+1 < len(my) and segx[i][j] == 0:
                uf.unite(idx(i, j+1), idx(i, j))

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = idx(invx[0], invy[0])
    if uf.same(ushi, idx(0, 0)):
        print("INF")
        return

    area = 0
    for i in range(len(mx)-1):
        for j in range(len(my)-1):
            if uf.same(ushi, idx(i, j)):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float("inf")


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():
    # 1. 座圧します
    # 2. 座標ごとに線分が乗っているかどうかを示す配列を作ります
    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # 4. 牛と同じグループの面積を数え上げます

    # 入力
    N, M = map(int, readline().split())
    ABC = [0]*N
    for i in range(N):
        ABC[i] = list(map(int, readline().split()))
    DEF = [0]*M
    for i in range(M):
        DEF[i] = list(map(int, readline().split()))

    # 1. 座圧
    x_coord, y_coord = {-INF, 0, INF}, {-INF, 0, INF}
    for a, b, c in ABC:
        x_coord.add(a)
        x_coord.add(b)
        y_coord.add(c)
    for d, e, f in DEF:
        x_coord.add(d)
        y_coord.add(e)
        y_coord.add(f)

    mx = list(sorted(x_coord))
    my = list(sorted(y_coord))
    invx, invy = {}, {}
    for i, x in enumerate(sorted(x_coord)):
        invx[x] = i
    for i, y in enumerate(sorted(y_coord)):
        invy[y] = i

    # 2. 線分ごとに線分が乗っているかどうかを示す配列を作ります(imos法)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分
    segx = [[0]*len(my) for _ in range(len(mx))]
    segy = [[0]*len(my) for _ in range(len(mx))]

    for i in range(N):
        a, b, c = ABC[i]
        segx[invx[a]][invy[c]-1] += 1
        segx[invx[b]][invy[c]-1] -= 1
    for i in range(len(mx)-1):
        for j in range(len(my)):
            segx[i+1][j] += segx[i][j]

    for i in range(M):
        d, e, f = DEF[i]
        segy[invx[d]-1][invy[e]] += 1
        segy[invx[d]-1][invy[f]] -= 1
    for i in range(len(invx)):
        for j in range(len(invy)-1):
            segy[i][j+1] += segy[i][j]

    # 3. 面ごとに同じ領域内かどうか、グルーピングします
    # UnionFindで検査していく
    uf = UnionFind(len(mx)*len(my))

    def idx(x, y):
        return x+y*len(mx)
    # segx[i][j]は座標(i, j)と(i+1, j)をつなぐ線分であり
    # 面[i][j-1]と面[i][j]の境界にあたる
    # segy[i][j]は座標(i, j)と(i, j+1)をつなぐ線分であり
    # 面[i-1][j]と面[i][j]の境界にあたる
    for i in range(len(mx)):
        for j in range(len(my)):
            if i+1 < len(mx) and segy[i][j] == 0:
                uf.unite(idx(i, j), idx(i+1, j))
            if j+1 < len(my) and segx[i][j] == 0:
                uf.unite(idx(i, j+1), idx(i, j))

    # 4. 牛と同じグループの面積を数え上げます
    # 無限の彼方と同じグル-プなら、INF
    ushi = idx(invx[0], invy[0])
    if uf.same(ushi, idx(0, 0)):
        print("INF")
        return

    area = 0
    for i in range(len(mx)-1):
        for j in range(len(my)-1):
            if uf.same(ushi, idx(i, j)):
                area += (mx[i+1]-mx[i])*(my[j+1]-my[j])
    print(area)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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 = abs(h_rests[hi] - h_rests[hi - 1]) * abs(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}

# grid[i][j]から進める/進めない方向の情報を管理
# いずれにも進める = 1
# 左右に進めない = 2
# 上下に進めない = 3
# 上下左右にも進めない = 6

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

grid = [[1] * (len(w_rests) + 2) for i in range(len(h_rests) + 2)]
for h1, h2, w1 in info_h:
    h1, h2, w1 = h_comps[h1], h_comps[h2], w_comps[w1]
    for hi in range(h1 + 1, h2 + 1):
        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] * (len(w_rests) + 2) for i in range(len(h_rests) + 2)]
si, sw = h_comps[0], w_comps[0]
stack = [(si, sw)]
ans = 0
used[si][sw] = True

while stack:
    i, j = stack.pop()
    ans += calc_s(i, j)

    # 上移動
    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
        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
        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
        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
        stack.append((nxt_i, nxt_j)) 
        
    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)

Submission status: Time Limit Exceeded

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 = abs(h_rests[hi] - h_rests[hi - 1]) * abs(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}


# いずれにも進める = 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 + 1, h2 + 1):
        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 = 0
used[si][sw] = True

while stack:
    i, j = stack.pop()
    ans += calc_s(i, j)

    # 上移動
    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
        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
        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
        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
        stack.append((nxt_i, nxt_j)) 
        
    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)

Submission status: Time Limit Exceeded

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

x=list()
y=list()

for i in range(n):
    x.append(list(map(int,input().split())))

for i in range(m):
    y.append(list(map(int,input().split())))


c = [i[2] for i in x]
cmax = max(c)
cmin = min(c)

d = [i[0] for i in y]
dmax = max(d)
dmin = min(d)

done = list()
ongoing = list()

ongoing.append([0,0])
ongoing.append([0,-1])
ongoing.append([-1,0])
ongoing.append([-1,-1])

while(ongoing!=[]):
    area = ongoing.pop()
    if ([area[0]+1,area[1]] not in ongoing) and ([area[0]+1,area[1]] not in done): 
        isbreak=0
        for line in y:
            if (line[0] == (area[0]+1)) and (line[1]<=area[1]) and (line[2]>=area[1]+1):
                isbreak=1
                break
        if isbreak==0:
            if area[0]+1>=dmax:
                print('INF')
                sys.exit()
            ongoing.append([area[0]+1,area[1]])


    if ([area[0]-1,area[1]] not in ongoing) and ([area[0]-1,area[1]] not in done): 
        isbreak=0
        for line in y:
            if (line[0] == (area[0])) and (line[1]<=area[1]) and (line[2]>=area[1]+1):
                isbreak=1
                break
        if isbreak==0:
            if area[0]-1<dmin:
                print('INF')
                sys.exit()
            ongoing.append([area[0]-1,area[1]])


    if ([area[0],area[1]+1] not in ongoing) and ([area[0],area[1]+1] not in done): 
        isbreak=0
        for line in x:
            if (line[2] == (area[1]+1)) and (line[0]<=area[0]) and (line[1]>=area[0]+1):
                isbreak=1
                break
        if isbreak==0:
            if area[1]+1>=cmax:
                print('INF')
                sys.exit()
            ongoing.append([area[0],area[1]+1])


    if ([area[0],area[1]-1] not in ongoing) and ([area[0],area[1]-1] not in done): 
        isbreak=0
        for line in x:
            if (line[2] == (area[1])) and (line[0]<=area[0]) and (line[1]>=area[0]+1):
                isbreak=1
                break
        if isbreak==0:
            if area[1]-1<cmin:
                print('INF')
                sys.exit()
            ongoing.append([area[0],area[1]-1])
    done.append(area)

print(len(done))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
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 1-v[d][c]and(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: Time Limit Exceeded

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=dict(enumerate(sorted(set(X))));return{s[i]:i for i in s},s,len(s)
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 1-v[d][c]and(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: Time Limit Exceeded

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=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(U[(f>0)+y][x]|e==0)|(V[y][(e>0)+x]|f==0)and 0==v[d][c]:q+=[(c,d)];v[d][c]=1
print([a,'INF'][a>F])

Submission status: Time Limit Exceeded

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


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

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))

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