Submit Info #7795

Problem Lang User Status Time Memory
Static RMQ pypy3 maspy AC 712 ms 162.06 MiB

ケース詳細
Name Status Time Memory
example_00 AC 32 ms 25.59 MiB
max_random_00 AC 699 ms 158.83 MiB
max_random_01 AC 702 ms 157.80 MiB
max_random_02 AC 712 ms 159.40 MiB
max_random_03 AC 692 ms 162.06 MiB
max_random_04 AC 698 ms 159.29 MiB
random_00 AC 561 ms 138.13 MiB
random_01 AC 578 ms 138.43 MiB
random_02 AC 407 ms 138.06 MiB
random_03 AC 186 ms 85.02 MiB
random_04 AC 224 ms 77.06 MiB
small_00 AC 41 ms 27.54 MiB
small_01 AC 45 ms 29.47 MiB
small_02 AC 46 ms 29.25 MiB
small_03 AC 46 ms 29.28 MiB
small_04 AC 47 ms 29.34 MiB
small_05 AC 46 ms 29.35 MiB
small_06 AC 49 ms 29.32 MiB
small_07 AC 47 ms 29.30 MiB
small_08 AC 47 ms 29.29 MiB
small_09 AC 48 ms 29.33 MiB

import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines class SegTree: X_unit = 1 << 30 X_f = min def __init__(self, N): self.N = N self.X = [self.X_unit] * (N + N) def build(self, seq): for i, x in enumerate(seq, self.N): self.X[i] = x for i in range(self.N - 1, 0, -1): self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1]) def set_val(self, i, x): i += self.N self.X[i] = x while i > 1: i >>= 1 self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1]) def fold(self, L, R): L += self.N R += self.N vL = self.X_unit vR = self.X_unit while L < R: if L & 1: vL = self.X_f(vL, self.X[L]) L += 1 if R & 1: R -= 1 vR = self.X_f(self.X[R], vR) L >>= 1 R >>= 1 return self.X_f(vL, vR) N, Q = map(int, readline().split()) seg = SegTree(N) A = map(int, readline().split()) seg.build(A) m = map(int, read().split()) ans = (seg.fold(L,R) for L, R in zip(m, m)) print('\n'.join(map(str, ans)))