結果
| 問題 |
No.2786 RMQ on Grid Path
|
| コンテスト | |
| ユーザー |
 liupengsay
|
| 提出日時 | 2024-06-15 16:03:36 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,767 ms / 6,000 ms |
| コード長 | 6,564 bytes |
| コンパイル時間 | 401 ms |
| コンパイル使用メモリ | 82,456 KB |
| 実行使用メモリ | 181,888 KB |
| 最終ジャッジ日時 | 2024-06-15 16:04:15 |
| 合計ジャッジ時間 | 36,725 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 35 |
ソースコード
from collections import defaultdict
from sys import stdin
class FastIO:
def __init__(self):
self.random_seed = 0
self.flush = False
self.inf = 1 << 32
return
@staticmethod
def read_int():
return int(stdin.readline().rstrip())
@staticmethod
def read_float():
return float(stdin.readline().rstrip())
@staticmethod
def read_list_ints():
return list(map(int, stdin.readline().rstrip().split()))
@staticmethod
def read_list_ints_minus_one():
return list(map(lambda x: int(x) - 1, stdin.readline().rstrip().split()))
@staticmethod
def read_str():
return stdin.readline().rstrip()
@staticmethod
def read_list_strs():
return stdin.readline().rstrip().split()
def get_random_seed(self):
import random
self.random_seed = random.randint(0, 10 ** 9 + 7)
return
def st(self, x):
return print(x, flush=self.flush)
def yes(self, s=None):
self.st("Yes" if not s else s)
return
def no(self, s=None):
self.st("No" if not s else s)
return
def lst(self, x):
return print(*x, flush=self.flush)
def flatten(self, lst):
self.st("\n".join(str(x) for x in lst))
return
@staticmethod
def max(a, b):
return a if a > b else b
@staticmethod
def min(a, b):
return a if a < b else b
@staticmethod
def ceil(a, b):
return a // b + int(a % b != 0)
@staticmethod
def accumulate(nums):
n = len(nums)
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + nums[i]
return pre
class UnionFind:
def __init__(self, n: int) -> None:
self.root_or_size = [-1] * n
self.part = n
self.n = n
return
def initialize(self):
for i in range(self.n):
self.root_or_size[i] = -1
self.part = self.n
return
def find(self, x):
y = x
while self.root_or_size[x] >= 0:
# range_merge_to_disjoint to the direct root node after query
x = self.root_or_size[x]
while y != x:
self.root_or_size[y], y = x, self.root_or_size[y]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.root_or_size[root_x] < self.root_or_size[root_y]:
root_x, root_y = root_y, root_x
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def union_left(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_x] += self.root_or_size[root_y]
self.root_or_size[root_y] = root_x
self.part -= 1
return True
def union_right(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def union_max(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if root_x > root_y:
root_x, root_y = root_y, root_x
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return
def union_min(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if root_x < root_y:
root_x, root_y = root_y, root_x
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return
def is_connected(self, x, y):
return self.find(x) == self.find(y)
def size(self, x):
return -self.root_or_size[self.find(x)]
def get_root_part(self):
# get the nodes list of every root
part = defaultdict(list)
n = len(self.root_or_size)
for i in range(n):
part[self.find(i)].append(i)
return part
def get_root_size(self):
# get the size of every root
size = defaultdict(int)
n = len(self.root_or_size)
for i in range(n):
if self.find(i) == i:
size[i] = -self.root_or_size[i]
return size
class Solution:
def __init__(self):
return
@staticmethod
def main(ac=FastIO()):
"""
url: url of the problem
tag: algorithm tag
"""
m, n = ac.read_list_ints()
grid = [ac.read_list_ints() for _ in range(m)]
q = ac.read_int()
ans = [-1] * q
dct = [[] for _ in range(m * n)]
for i in range(q):
x1, y1, x2, y2 = ac.read_list_ints_minus_one()
dct[x1 * n + y1].append((i, x2 * n + y2))
dct[x2 * n + y2].append((i, x1 * n + y1))
ind = list(range(m * n))
ind.sort(key=lambda it: grid[it // n][it % n])
uf = UnionFind(m * n)
for num in ind:
x, y = num // n, num % n
for a, b in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= a < m and 0 <= b < n and grid[a][b] <= grid[x][y] and not uf.is_connected(num, a * n + b):
root1, root2 = uf.find(num), uf.find(a * n + b)
if len(dct[root1]) < len(dct[root2]):
lst = []
for i, xx in dct[root1]:
if uf.is_connected(xx, root2):
ans[i] = grid[x][y]
else:
lst.append((i, xx))
dct[root2].extend(lst)
uf.union_left(root2, root1)
else:
lst = []
for i, xx in dct[root2]:
if uf.is_connected(xx, root1):
ans[i] = grid[x][y]
else:
lst.append((i, xx))
dct[root1].extend(lst)
uf.union_left(root1, root2)
for a in ans:
ac.st(a)
return
Solution().main()