Submit Info #3023

Problem Lang User Status Time Memory
Static RMQ pypy3 knuu AC 1391 ms 141.71 MiB

ケース詳細
Name Status Time Memory
example_00 AC 41 ms 26.06 MiB
max_random_00 AC 1373 ms 124.01 MiB
max_random_01 AC 1382 ms 124.21 MiB
max_random_02 AC 1391 ms 124.06 MiB
max_random_03 AC 1378 ms 123.92 MiB
max_random_04 AC 1366 ms 124.18 MiB
random_00 AC 1132 ms 141.71 MiB
random_01 AC 1185 ms 125.82 MiB
random_02 AC 825 ms 82.43 MiB
random_03 AC 354 ms 102.33 MiB
random_04 AC 439 ms 85.69 MiB
small_00 AC 62 ms 29.47 MiB
small_01 AC 64 ms 29.60 MiB
small_02 AC 64 ms 29.57 MiB
small_03 AC 65 ms 29.57 MiB
small_04 AC 65 ms 30.22 MiB
small_05 AC 66 ms 30.19 MiB
small_06 AC 65 ms 30.35 MiB
small_07 AC 65 ms 30.21 MiB
small_08 AC 67 ms 30.20 MiB
small_09 AC 65 ms 30.19 MiB

class SegmentTree: """Segment Tree (Point Update & Range Query) Query 1. update(i, val): update i-th value to val 2. query(low, high): find f(value) in [low, high) Complexity time complexity: O(log n) space complexity: O(n) """ def __init__(self, N, f, default): self.N = 1 << (N-1).bit_length() self.default = default self.f = f self.segtree = [self.default] * ((self.N << 1) - 1) @classmethod def create_from_array(cls, arr, f, default): N = len(arr) self = cls(N, f, default) for i in range(N): self.segtree[self.N - 1 + i] = arr[i] for i in reversed(range(self.N - 1)): self.segtree[i] = self.f( self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]) return self def update(self, i, val): i += self.N - 1 self.segtree[i] = val while i > 0: i = (i - 1) >> 1 self.segtree[i] = self.f( self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]) def __getitem__(self, k): return self.segtree[self.N - 1 + k] def query(self, low, high): # query [l, r) low, high = low + self.N, high + self.N ret = self.default while low < high: if low & 1: ret = self.f(ret, self.segtree[low-1]) low += 1 if high & 1: high -= 1 ret = self.f(ret, self.segtree[high-1]) low, high = low >> 1, high >> 1 return ret def yosupo1(): # https://judge.yosupo.jp/problem/staticrmq _, Q = map(int, input().split()) A = [int(x) for x in input().split()] rmq = SegmentTree.create_from_array(A, min, 10**9) ans = [] for _ in range(Q): l, r = map(int, input().split()) ans.append(rmq.query(l, r)) print(*ans, sep="\n") def yosupo2(): # https://judge.yosupo.jp/problem/point_add_range_sum import operator _, Q = map(int, input().split()) A = [int(x) for x in input().split()] rsq = SegmentTree.create_from_array(A, operator.add, 0) for _ in range(Q): type_, l, r = map(int, input().split()) if type_ == 0: rsq.update(l, rsq[l] + r) else: print(rsq.query(l, r)) def aoj(): # https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A N, Q = map(int, input().split()) default = (1 << 31) - 1 rmq = SegmentTree(N, min, default) for _ in range(Q): com, x, y = map(int, input().split()) if com == 0: rmq.update(x, y) else: print(rmq.query(x, y+1)) if __name__ == '__main__': yosupo1() # yosupo2() # aoj()