結果
問題 | No.875 Range Mindex Query |
ユーザー | roaris |
提出日時 | 2019-09-20 23:52:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 1,380 bytes |
コンパイル時間 | 1,444 ms |
コンパイル使用メモリ | 86,872 KB |
実行使用メモリ | 94,332 KB |
最終ジャッジ日時 | 2023-10-12 22:41:48 |
合計ジャッジ時間 | 6,828 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,672 KB |
testcase_01 | AC | 111 ms
77,004 KB |
testcase_02 | AC | 124 ms
77,336 KB |
testcase_03 | AC | 102 ms
76,676 KB |
testcase_04 | AC | 110 ms
76,960 KB |
testcase_05 | AC | 102 ms
76,696 KB |
testcase_06 | AC | 111 ms
76,972 KB |
testcase_07 | AC | 112 ms
77,336 KB |
testcase_08 | AC | 105 ms
76,792 KB |
testcase_09 | AC | 108 ms
77,100 KB |
testcase_10 | AC | 126 ms
77,084 KB |
testcase_11 | AC | 395 ms
91,080 KB |
testcase_12 | AC | 355 ms
88,516 KB |
testcase_13 | AC | 361 ms
94,184 KB |
testcase_14 | AC | 356 ms
92,528 KB |
testcase_15 | AC | 405 ms
94,332 KB |
testcase_16 | AC | 347 ms
94,240 KB |
testcase_17 | AC | 365 ms
94,220 KB |
testcase_18 | AC | 361 ms
94,148 KB |
ソースコード
from collections import defaultdict import sys input = sys.stdin.readline class SegmentTree: def __init__(self, n): #a1, a2, ..., an n_ = 1 while n_ < n: n_ *= 2 self.n = n_ self.arr = [10**18] * (2*self.n-1) def update(self, k, a): #0_indexed k += self.n - 1 self.arr[k] = a while k > 0: k = (k-1) // 2 self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2]) def query(self, l, r): #min(a[l:r)) L, R = l+self.n, r+self.n res = 10 ** 18 while L < R: if R & 1: R -= 1 res = min(res, self.arr[R-1]) if L & 1: res = min(res, self.arr[L-1]) L += 1 L >>= 1 R >>= 1 return res N, Q = map(int, input().split()) a = list(map(int, input().split())) st = SegmentTree(N) idx = defaultdict(int) for i in range(N): st.update(i, a[i]) idx[a[i]] = i for _ in range(Q): i, l, r = map(int, input().split()) if i == 1: st.update(l-1, a[r-1]) st.update(r-1, a[l-1]) idx[a[r-1]] = l - 1 idx[a[l-1]] = r - 1 a[l-1], a[r-1] = a[r-1], a[l-1] elif i == 2: m = st.query(l-1, r) print(idx[m] + 1)