結果
問題 | No.875 Range Mindex Query |
ユーザー | yuly3 |
提出日時 | 2020-04-21 08:09:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 374 ms / 2,000 ms |
コード長 | 2,254 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 93,312 KB |
最終ジャッジ日時 | 2024-04-16 09:31:57 |
合計ジャッジ時間 | 4,435 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
52,608 KB |
testcase_01 | AC | 63 ms
65,152 KB |
testcase_02 | AC | 71 ms
68,224 KB |
testcase_03 | AC | 50 ms
59,136 KB |
testcase_04 | AC | 57 ms
62,080 KB |
testcase_05 | AC | 45 ms
53,504 KB |
testcase_06 | AC | 63 ms
64,640 KB |
testcase_07 | AC | 66 ms
66,176 KB |
testcase_08 | AC | 56 ms
61,696 KB |
testcase_09 | AC | 56 ms
61,824 KB |
testcase_10 | AC | 72 ms
67,840 KB |
testcase_11 | AC | 374 ms
89,216 KB |
testcase_12 | AC | 345 ms
84,352 KB |
testcase_13 | AC | 329 ms
92,416 KB |
testcase_14 | AC | 324 ms
90,752 KB |
testcase_15 | AC | 359 ms
93,056 KB |
testcase_16 | AC | 256 ms
93,312 KB |
testcase_17 | AC | 264 ms
93,312 KB |
testcase_18 | AC | 268 ms
92,800 KB |
ソースコード
import sys sys.setrecursionlimit(10 ** 7) rl = sys.stdin.readline class SegmentTree: def __init__(self, init_value: list, segfunc, ide_ele): n = len(init_value) self.N0 = 1 << (n - 1).bit_length() self.ide_ele = ide_ele self.data = [ide_ele] * (2 * self.N0) self.segfunc = segfunc for i, x in enumerate(init_value): self.data[i + self.N0 - 1] = x for i in range(self.N0 - 2, -1, -1): self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2]) def update(self, k, x): k += self.N0 - 1 ################################################################ self.data[k] = x ################################################################ while k: k = (k - 1) // 2 self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2]) def query(self, left, right): L = left + self.N0 R = right + self.N0 res = self.ide_ele ################################################################ while L < R: if L & 1: res = self.segfunc(res, self.data[L - 1]) L += 1 if R & 1: R -= 1 res = self.segfunc(res, self.data[R - 1]) L >>= 1 R >>= 1 ################################################################ return res def solve(): N, Q = map(int, rl().split()) a = list(map(int, rl().split())) seg_tree = SegmentTree(a, min, 10 ** 7) a_to_idx = [0] * (N + 1) for i in range(N): a_to_idx[a[i]] = i ans = [] for _ in range(Q): com, left, right = map(int, rl().split()) left, right = left - 1, right - 1 if com == 1: tmp_l = seg_tree.query(left, left + 1) tmp_r = seg_tree.query(right, right + 1) a_to_idx[tmp_l] = right a_to_idx[tmp_r] = left seg_tree.update(right, tmp_l) seg_tree.update(left, tmp_r) else: ans.append(a_to_idx[seg_tree.query(left, right + 1)] + 1) print(*ans, sep='\n') if __name__ == '__main__': solve()