結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー LyricalMaestro
提出日時 2025-10-18 21:23:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,367 ms / 6,000 ms
コード長 3,716 bytes
コンパイル時間 544 ms
コンパイル使用メモリ 82,896 KB
実行使用メモリ 256,852 KB
最終ジャッジ日時 2025-10-18 21:23:46
合計ジャッジ時間 33,504 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2786



class UnionFind:
    """
    UnionFindの基本的な処理を実装したクラス
    """

    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def get_root(self, v):
        if v == self.root[v]:
            return v
        else:
            old_root = self.root[v]
            new_root = self.get_root(old_root)
            self.root[v] = new_root
            return new_root

    def merge(self, u, v):
        root_u = self.get_root(u)
        root_v = self.get_root(v)
        if root_u == root_v:
            return False

        if self.size[root_u] >= self.size[root_v]:
            self.size[root_u] += self.size[root_v]
            self.root[root_v] = root_u
            self.root[v] = root_u
        else:
            self.size[root_v] += self.size[root_u]
            self.root[root_u] = root_v
            self.root[u] = root_v
        return True
    

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    Q = int(input())
    queries = []
    for _ in range(Q):
        rs, cs, rt, ct = map(int, input().split())
        queries.append((rs - 1, cs - 1, rt - 1, ct - 1))


    # コスト単位
    array = [[] for _ in range(H * W + 1)]
    for h in range(H):
        for w in range(W):
            array[A[h][w]].append(h * W + w)

    answers = [-1] * Q
    st_sets = [set() for _ in range(H * W)]
    for i in range(Q):
        rs, cs, rt, ct = queries[i]
        st_sets[rs * W + cs].add(i)
        st_sets[rt * W + ct].add(i)

    uf = UnionFind(H * W)
    for a in range(H * W + 1):
        for index in array[a]:
            h = index // W
            w = index % W

            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                new_h = dh + h
                new_w = dw + w
                if 0 <= new_h < H and 0 <= new_w < W:
                    if A[new_h][new_w] <= a:
                        new_index = new_h * W + new_w
                        r_index = uf.get_root(index)
                        r_new_index = uf.get_root(new_index)
                        if r_index != r_new_index:
                            t_set = None
                            if len(st_sets[r_new_index]) >= len(st_sets[r_index]):
                                for y_index in st_sets[r_index]:
                                    if y_index not in st_sets[r_new_index]:
                                        st_sets[r_new_index].add(y_index)
                                    else:
                                        st_sets[r_new_index].remove(y_index)
                                        answers[y_index] = a
                                t_set = st_sets[r_new_index]
                            else:
                                for y_index in st_sets[r_new_index]:
                                    if y_index not in st_sets[r_index]:
                                        st_sets[r_index].add(y_index)
                                    else:
                                        st_sets[r_index].remove(y_index)
                                        answers[y_index] = a
                                t_set = st_sets[r_index]
                            uf.merge(index, new_index)
                            index1 = uf.get_root(index)
                            if index1 == r_index:
                                st_sets[r_index] = t_set
                            else:
                                st_sets[r_new_index] = t_set
                            
    for i in range(Q):
        print(answers[i])








if __name__ == "__main__":
    main()
0