Problem p02680 (python)

Fixed submission:
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]
OFFSET = 5000
stack = [si * 5000 + sw]
ans = 0
used[si][sw] = True

while stack:
    ij = stack.pop()
    i, j = divmod(ij, OFFSET)
    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 * OFFSET + 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 * OFFSET + 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 * OFFSET + 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 * OFFSET + nxt_j)
        
    if ans > INF:
        #広々としたところに出た場合はINF
        print("INF")
        exit()

print(ans)

Buggy submission (verdict: Runtime Error):
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 = 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)

Buggy submission (verdict: Runtime Error):
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}


# いずれにも進める = 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)

Buggy submission (verdict: Runtime Error):
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)