Submission #57554290

---

Source Code Expand

H,W,Q = map(int, input().split())

from atcoder.dsu import DSU
uf = DSU(H*W)

wall = [True]*(H*W)

def Id(i,j):
    return i*W + j

def Pos(id):
    return divmod(id,W)

def is_inside(x, y):
    return 0 <= x <= H-1 and 0 <= y <= W-1

moves = [(0,1), (1,0), (0,-1), (-1,0)]

for _ in range(Q):
    # print(uf.groups())
    R,C = map(int, input().split())
    R,C = R-1,C-1
    id = Id(R,C)
    if wall[id]:
        wall[id] = False
        for move in moves:
            next_R, next_C = R+move[0],C+move[1]
            if is_inside(next_R, next_C) and not wall[Id(next_R, next_C)]:
                uf.merge(id, Id(next_R, next_C))
    else:
        group = list(filter(lambda x: id in x, uf.groups()))
        group = group[0]

        yoko = list(filter(lambda x: R*W<=x<=id, group))
        # print(f"{yoko=}")
        left = min(yoko)
        r,c = Pos(left)
        if is_inside(r,c-1):
            wall[left-1] = False
            uf.merge(left-1,left)

        right = max(yoko)
        r,c = Pos(right)
        if is_inside(r,c+1):
            wall[right+1] = False
            uf.merge(right+1,right)
        
        tate = list(filter(lambda x: x%W == C, group))
        # print(f"{tate=}")
        top = min(tate)
        r,c = Pos(top)
        if is_inside(r-1,c):
            wall[top-W] = False
            uf.merge(top,top-W)

        bottom = max(tate)
        r,c = Pos(bottom)
        if is_inside(r+1,c):
            wall[bottom+W] = False
            uf.merge(bottom,bottom+W)

        # print(f"{left=}, {right=}, {top=}, {bottom=}")

print(wall.count(True))

Submission Info

Judge Result