結果
問題 | No.875 Range Mindex Query |
ユーザー | anagohirame |
提出日時 | 2019-09-06 21:39:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,521 ms / 2,000 ms |
コード長 | 1,204 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 87,308 KB |
実行使用メモリ | 98,468 KB |
最終ジャッジ日時 | 2023-09-06 23:07:36 |
合計ジャッジ時間 | 11,885 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,348 KB |
testcase_01 | AC | 125 ms
77,820 KB |
testcase_02 | AC | 125 ms
77,480 KB |
testcase_03 | AC | 84 ms
76,068 KB |
testcase_04 | AC | 101 ms
77,248 KB |
testcase_05 | AC | 89 ms
76,260 KB |
testcase_06 | AC | 120 ms
78,524 KB |
testcase_07 | AC | 127 ms
77,492 KB |
testcase_08 | AC | 113 ms
77,848 KB |
testcase_09 | AC | 114 ms
78,452 KB |
testcase_10 | AC | 150 ms
78,252 KB |
testcase_11 | AC | 1,110 ms
92,120 KB |
testcase_12 | AC | 884 ms
89,988 KB |
testcase_13 | AC | 802 ms
93,812 KB |
testcase_14 | AC | 758 ms
92,112 KB |
testcase_15 | AC | 938 ms
93,436 KB |
testcase_16 | AC | 1,274 ms
95,220 KB |
testcase_17 | AC | 1,521 ms
98,468 KB |
testcase_18 | AC | 1,449 ms
97,116 KB |
ソースコード
INF = 10**30 class Rmin(): def __init__(self, size): #the number of nodes is 2n-1 self.n = 1 while self.n < size: self.n *= 2 self.node = [INF] * (2*self.n-1) def Access(self, x): return self.node[x+self.n-1] def Update(self, x, val): x += self.n-1 self.node[x] = val while x > 0: x = (x-1)//2 self.node[x] = min(self.node[2*x+1], self.node[2*x+2]) return #[a, b) def Get(self, a, b, k=0, l=0, r=-1): if r < 0: r = self.n if a >= r or b <= l: return INF elif a <= l and b >= r: return self.node[k] else: vl = self.Get(a, b, 2*k+1, l, (l+r)//2) vr = self.Get(a, b, 2*k+2, (l+r)//2, r) return min(vl, vr) import sys def input(): return sys.stdin.readline()[:-1] n, q = map(int, input().split()) a = list(map(int, input().split())) ind = [-1 for _ in range(n+1)] segtree = Rmin(n) for i, x in enumerate(a): segtree.Update(i, x) ind[x] = i #print(ind) for _ in range(q): k, l, r = map(int, input().split()) if k == 1: ind[a[l-1]], ind[a[r-1]] = ind[a[r-1]], ind[a[l-1]] a[l-1], a[r-1] = a[r-1], a[l-1] #print(a, ind) segtree.Update(l-1, a[l-1]) segtree.Update(r-1, a[r-1]) else: res = segtree.Get(l-1, r) print(ind[res]+1)