結果
問題 | No.875 Range Mindex Query |
ユーザー | nephrologist |
提出日時 | 2020-05-06 21:32:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 646 ms / 2,000 ms |
コード長 | 2,282 bytes |
コンパイル時間 | 404 ms |
コンパイル使用メモリ | 86,796 KB |
実行使用メモリ | 94,900 KB |
最終ジャッジ日時 | 2023-09-16 07:32:31 |
合計ジャッジ時間 | 7,518 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,244 KB |
testcase_01 | AC | 101 ms
75,860 KB |
testcase_02 | AC | 118 ms
76,720 KB |
testcase_03 | AC | 84 ms
75,592 KB |
testcase_04 | AC | 89 ms
75,836 KB |
testcase_05 | AC | 79 ms
74,956 KB |
testcase_06 | AC | 102 ms
76,048 KB |
testcase_07 | AC | 107 ms
76,484 KB |
testcase_08 | AC | 92 ms
76,032 KB |
testcase_09 | AC | 93 ms
75,868 KB |
testcase_10 | AC | 114 ms
76,636 KB |
testcase_11 | AC | 646 ms
90,916 KB |
testcase_12 | AC | 573 ms
86,840 KB |
testcase_13 | AC | 528 ms
94,516 KB |
testcase_14 | AC | 517 ms
93,032 KB |
testcase_15 | AC | 615 ms
94,900 KB |
testcase_16 | AC | 614 ms
94,644 KB |
testcase_17 | AC | 641 ms
94,584 KB |
testcase_18 | AC | 613 ms
94,820 KB |
ソースコード
n, q = map(int, input().split()) A = list(map(int, input().split())) infi = 10 ** 20 def func(pair1, pair2): idx1, val1 = pair1 idx2, val2 = pair2 if val1 < val2: res = pair1 else: res = pair2 return res class SegmentTree: # 1-index def __init__(self, A: list, ele, func): # Aは0-idx self.A = A self.ele = ele self.func = func self.n = len(self.A) self.num = 2 ** ((n - 1).bit_length()) self.SEG = [self.ele] * (2 * self.num) # self.LAZY=[ele]*(2*num) def search(self, idx): return self.SEG[idx + self.num] def initialize(self): for i in range(self.n): self.SEG[i + self.num] = (i + 1, self.A[i]) for i in range(self.num - 1, 0, -1): self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1]) def update(self, idx, val): # 0-idx idx += self.num self.SEG[idx] = val idx //= 2 while idx: self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1]) idx //= 2 # def delay(self,): def query(self, left, right): # maspy式。開区間のママ処理する # left, rightで値を分けているのは交換法則不成立のときのため # 開区間→Rが奇数→右端が偶数→1ずらしてから計算 # 下から上への遷移は2で割る # juppy氏は閉区間に直していた resleft = self.ele resright = self.ele left += self.num right += self.num while right - left > 0: if left % 2 == 1: resleft = self.func(resleft, self.SEG[left]) left += 1 if right % 2 == 1: right -= 1 resright = self.func(resright, self.SEG[right]) left //= 2 right //= 2 return self.func(resleft, resright)[0] ST = SegmentTree(A, (-1, infi), func) ST.initialize() for _ in range(q): a, l, r = map(int, input().split()) if a == 1: lidx, lval = ST.search(l - 1) ridx, rval = ST.search(r - 1) ST.update(ridx - 1, (ridx, lval)) ST.update(lidx - 1, (lidx, rval)) else: print(ST.query(l - 1, r))