結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー とりゐ
提出日時 2024-06-14 21:55:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,351 ms / 6,000 ms
コード長 5,359 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 267,008 KB
最終ジャッジ日時 2024-06-14 21:56:38
合計ジャッジ時間 41,879 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin

input = lambda: stdin.readline()[:-1]

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.group_count -= 1

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def groups(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members


class SparseTable:
    def __init__(self, init, func, e):
        n = len(init)
        self.e = e
        self.func = func
        size = 0
        while (1 << size) <= n:
            size += 1
        self.size = size
        self.table = [e] * (size * (1 << size))
        for i in range(n):
            self.table[i] = init[i]

        for i in range(1, size):
            for j in range((1 << size) - (1 << i) + 1):
                self.table[(i << size) + j] = func(
                    self.table[((i - 1) << size) + j],
                    self.table[((i - 1) << size) + j + (1 << (i - 1))],
                )

    def query(self, l, r):
        if l == r:
            return self.e
        s = (r - l).bit_length() - 1
        return self.func(
            self.table[(s << self.size) + l],
            self.table[(s << self.size) + r - (1 << s)],
        )


class HeavyLightDecomposition:
    def __init__(self, n, edge):
        self.n = n
        self.sub_size = [1] * n
        self.par = [-1] * n

        todo = [0]
        while todo:
            v = todo.pop()
            if v >= 0:
                for u in edge[v]:
                    if u != self.par[v]:
                        todo.append(~u)
                        todo.append(u)
                        self.par[u] = v
            else:
                v = ~v
                self.sub_size[self.par[v]] += self.sub_size[v]

        self.head = [-1] * n
        self.head[0] = 0
        self.order = [-1] * n
        self.heavy_child = [-1] * n

        todo = [0]
        cnt = 0
        while todo:
            v = todo.pop()
            self.order[v] = cnt
            cnt += 1
            mx = 0
            for u in edge[v]:
                if u != self.par[v] and mx < self.sub_size[u]:
                    mx = self.sub_size[u]
                    self.heavy_child[v] = u
            for u in edge[v]:
                if self.par[v] != u and self.heavy_child[v] != u:
                    self.head[u] = u
                    todo.append(u)
            if self.heavy_child[v] != -1:
                self.head[self.heavy_child[v]] = self.head[v]
                todo.append(self.heavy_child[v])

    def for_each_edge(self, u, v):
        paths = []
        while True:
            if self.order[u] > self.order[v]:
                u, v = v, u
            if self.head[u] != self.head[v]:
                paths.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.par[self.head[v]]
            else:
                paths.append((self.order[u] + 1, self.order[v] + 1))
                return paths

    def for_each_vertex(self, u, v):
        paths = []
        while True:
            if self.order[u] > self.order[v]:
                u, v = v, u
            if self.head[u] != self.head[v]:
                paths.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.par[self.head[v]]
            else:
                paths.append((self.order[u], self.order[v] + 1))
                return paths


def f(x, y):
    return x * W + y


H, W = map(int, input().split())
a = [list(map(int, input().split())) for i in range(H)]
edges = []
for x in range(H):
    for y in range(W):
        for dx, dy in [[0, 1], [1, 0]]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W:
                edges.append((max(a[x][y], a[nx][ny]), f(x, y), f(nx, ny)))

n = H * W
edges.sort(key=lambda x: x[0])
tree = [[] for i in range(n)]

uf = UnionFind(n)
tree_edges = []
for w, u, v in edges:
    if not uf.same(u, v):
        uf.union(u, v)
        tree[u].append(v)
        tree[v].append(u)
        tree_edges.append((v, u, w))

hld = HeavyLightDecomposition(n, tree)
res = [0] * n
for u, v, w in tree_edges:
    if hld.par[u] == v:
        res[hld.order[u]] = w
    else:
        res[hld.order[v]] = w

ST = SparseTable(res, max, -1)
q = int(input())
for _ in range(q):
    sx, sy, gx, gy = map(lambda x: int(x) - 1, input().split())
    u = f(sx, sy)
    v = f(gx, gy)
    ans = 0
    for l, r in hld.for_each_edge(u, v):
        ans = max(ans, ST.query(l, r))
    print(ans)
0