結果
問題 | No.875 Range Mindex Query |
ユーザー | convexineq |
提出日時 | 2019-09-06 22:47:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 474 ms / 2,000 ms |
コード長 | 1,726 bytes |
コンパイル時間 | 629 ms |
コンパイル使用メモリ | 87,196 KB |
実行使用メモリ | 94,144 KB |
最終ジャッジ日時 | 2023-09-07 01:41:38 |
合計ジャッジ時間 | 6,229 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,456 KB |
testcase_01 | AC | 92 ms
76,688 KB |
testcase_02 | AC | 101 ms
76,636 KB |
testcase_03 | AC | 77 ms
75,684 KB |
testcase_04 | AC | 85 ms
76,772 KB |
testcase_05 | AC | 81 ms
75,784 KB |
testcase_06 | AC | 91 ms
76,472 KB |
testcase_07 | AC | 92 ms
76,696 KB |
testcase_08 | AC | 82 ms
76,124 KB |
testcase_09 | AC | 85 ms
76,604 KB |
testcase_10 | AC | 100 ms
76,728 KB |
testcase_11 | AC | 470 ms
93,780 KB |
testcase_12 | AC | 434 ms
91,576 KB |
testcase_13 | AC | 411 ms
90,772 KB |
testcase_14 | AC | 408 ms
90,436 KB |
testcase_15 | AC | 474 ms
94,144 KB |
testcase_16 | AC | 353 ms
91,724 KB |
testcase_17 | AC | 378 ms
92,468 KB |
testcase_18 | AC | 363 ms
92,532 KB |
ソースコード
# coding: utf-8 # Your code here! """ セグメント木(一般化) """ class segment_tree: """ N: 処理する区間の長さ """ def __init__(self, N): #演算子および単位元を定義する。 # max, min, __add__,ラムダ式,関数定義... self.op = min self.UNIT = (1<<32)-1 self.N0 = 2**(N-1).bit_length() self.tree = [self.UNIT]*(2*self.N0) # a_k の値を x に更新 def update(self, k,x): k += self.N0-1 self.tree[k] = x while k >= 0: k = (k - 1) // 2 self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2]) # 区間[l,r]をopでまとめる def query(self, l,r): L = l + self.N0; R = r + self.N0 + 1 s = self.UNIT while L < R: if R & 1: R -= 1 s = self.op(s, self.tree[R-1]) if L & 1: s = self.op(s, self.tree[L-1]) L += 1 L >>= 1; R >>= 1 return s import sys sys.setrecursionlimit(10**6) readline = sys.stdin.readline n,q = [int(i) for i in readline().split()] a = [int(i)-1 for i in readline().split()] ilr = [[int(i) for i in readline().split()] for i in range(q)] seg = segment_tree(n) ra = [0]*(n) for i,ai in enumerate(a): seg.update(i,ai) ra[ai] = i for i,l,r in ilr: l -= 1 r -= 1 if i == 1: al = seg.query(l,l) ar = seg.query(r,r) seg.update(l,ar) seg.update(r,al) # print(al,ar,"al,ar") a[l],a[r]=a[r],a[l] ra[al],ra[ar] = ra[ar],ra[al] # print(ra) else: m = seg.query(l,r) print(ra[m]+1)