結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
55,228 KB
testcase_01 AC 39 ms
55,956 KB
testcase_02 AC 64 ms
73,228 KB
testcase_03 AC 70 ms
74,716 KB
testcase_04 AC 63 ms
72,980 KB
testcase_05 AC 74 ms
77,084 KB
testcase_06 AC 67 ms
74,836 KB
testcase_07 AC 76 ms
77,260 KB
testcase_08 AC 73 ms
74,744 KB
testcase_09 AC 67 ms
74,400 KB
testcase_10 AC 67 ms
73,564 KB
testcase_11 AC 79 ms
74,364 KB
testcase_12 AC 2,348 ms
265,528 KB
testcase_13 AC 2,351 ms
265,536 KB
testcase_14 AC 2,339 ms
266,224 KB
testcase_15 AC 2,284 ms
265,204 KB
testcase_16 AC 2,258 ms
265,756 KB
testcase_17 AC 2,323 ms
265,464 KB
testcase_18 AC 2,267 ms
265,232 KB
testcase_19 AC 2,202 ms
258,276 KB
testcase_20 AC 2,207 ms
267,008 KB
testcase_21 AC 2,269 ms
256,504 KB
testcase_22 AC 2,120 ms
265,704 KB
testcase_23 AC 2,175 ms
265,436 KB
testcase_24 AC 1,085 ms
263,612 KB
testcase_25 AC 1,093 ms
261,132 KB
testcase_26 AC 1,111 ms
261,320 KB
testcase_27 AC 571 ms
113,176 KB
testcase_28 AC 398 ms
84,884 KB
testcase_29 AC 1,921 ms
265,744 KB
testcase_30 AC 436 ms
92,740 KB
testcase_31 AC 277 ms
87,432 KB
testcase_32 AC 759 ms
252,352 KB
testcase_33 AC 166 ms
79,296 KB
testcase_34 AC 815 ms
263,340 KB
testcase_35 AC 789 ms
263,604 KB
testcase_36 AC 844 ms
263,388 KB
権限があれば一括ダウンロードができます

ソースコード

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