結果
問題 | No.875 Range Mindex Query |
ユーザー | tktk_snsn |
提出日時 | 2020-09-28 22:36:03 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,429 ms / 2,000 ms |
コード長 | 2,437 bytes |
コンパイル時間 | 79 ms |
コンパイル使用メモリ | 11,028 KB |
実行使用メモリ | 28,920 KB |
最終ジャッジ日時 | 2023-09-15 15:02:32 |
合計ジャッジ時間 | 11,285 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
8,048 KB |
testcase_01 | AC | 22 ms
8,168 KB |
testcase_02 | AC | 25 ms
8,128 KB |
testcase_03 | AC | 18 ms
8,276 KB |
testcase_04 | AC | 19 ms
8,216 KB |
testcase_05 | AC | 18 ms
8,612 KB |
testcase_06 | AC | 22 ms
8,512 KB |
testcase_07 | AC | 22 ms
8,232 KB |
testcase_08 | AC | 20 ms
8,224 KB |
testcase_09 | AC | 20 ms
8,164 KB |
testcase_10 | AC | 25 ms
8,492 KB |
testcase_11 | AC | 1,429 ms
24,432 KB |
testcase_12 | AC | 1,161 ms
20,548 KB |
testcase_13 | AC | 943 ms
27,988 KB |
testcase_14 | AC | 923 ms
26,696 KB |
testcase_15 | AC | 1,322 ms
28,008 KB |
testcase_16 | AC | 1,198 ms
27,996 KB |
testcase_17 | AC | 1,304 ms
28,788 KB |
testcase_18 | AC | 1,281 ms
28,920 KB |
ソースコード
#data: (val, idx) unit = (10**9, -1) def op(A, B): if A[0] > B[0]: return B return A class SegmentTree: def __init__(self, N, arr=None, op=None, unit=None): """ INPUT N: 配列のサイズ segment tree: 1-indexedで構築 original array: 0-indexed 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 --------------------- 0 1 2 3 4 5 6 7 """ self.N = N self.unit = unit self.op = op self.tree = [unit] * (2 * N + 1) if arr is not None: self._build(arr) def _build(self, arr): op = self.op N = self.N for i, a in enumerate(arr, N): self.tree[i] = a for i in reversed(range(1, N)): self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1]) def show(self): for i in range(self.N): print(self.tree[i+self.N], end=" ") print() def update(self, i, x): """ arr[i]の値をxに変更する i: 0-indexed """ i += self.N op = self.op self.tree[i] = x while i > 1: i >>= 1 self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1]) def swap(self, l, r): """ arr[l], arr[r]をswap i: 0-indexed """ lv, li = self.tree[l + self.N] rv, ri = self.tree[r + self.N] if lv > rv: self.update(l, (rv, li)) self.update(r, (lv, ri)) else: self.update(r, (lv, ri)) self.update(l, (rv, li)) def query(self, L, R): """ L,R: 0-indexed 半開区間[L,R)の累積演算した値を返す """ op = self.op res = self.unit L += self.N R += self.N while L < R: if L & 1: res = op(res, self.tree[L]) L += 1 if R & 1: R -= 1 res = op(res, self.tree[R]) L >>= 1 R >>= 1 return res N, Q = map(int, input().split()) arr = [(a, i + 1) for i, a in enumerate(map(int, input().split()))] seg = SegmentTree(N, arr, op, unit) for _ in range(Q): t, l, r = map(int, input().split()) if t == 1: seg.swap(l - 1, r - 1) else: print(seg.query(l - 1, r)[1])