結果
問題 | No.875 Range Mindex Query |
ユーザー | convexineq |
提出日時 | 2019-09-06 23:02:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 1,823 bytes |
コンパイル時間 | 643 ms |
コンパイル使用メモリ | 87,240 KB |
実行使用メモリ | 92,748 KB |
最終ジャッジ日時 | 2023-09-07 02:15:25 |
合計ジャッジ時間 | 6,216 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,604 KB |
testcase_01 | AC | 92 ms
76,556 KB |
testcase_02 | AC | 98 ms
76,760 KB |
testcase_03 | AC | 79 ms
75,780 KB |
testcase_04 | AC | 87 ms
76,564 KB |
testcase_05 | AC | 83 ms
76,064 KB |
testcase_06 | AC | 89 ms
76,556 KB |
testcase_07 | AC | 93 ms
76,660 KB |
testcase_08 | AC | 85 ms
75,880 KB |
testcase_09 | AC | 87 ms
76,512 KB |
testcase_10 | AC | 101 ms
76,664 KB |
testcase_11 | AC | 374 ms
92,748 KB |
testcase_12 | AC | 339 ms
89,792 KB |
testcase_13 | AC | 328 ms
89,172 KB |
testcase_14 | AC | 321 ms
89,368 KB |
testcase_15 | AC | 375 ms
92,564 KB |
testcase_16 | AC | 343 ms
91,620 KB |
testcase_17 | AC | 361 ms
92,548 KB |
testcase_18 | AC | 360 ms
92,444 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 def get(self, k): #k番目の値を取得。query[k,k]と同じ return self.tree[k+self.N0-1] 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.get(l) ar = seg.get(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)