結果
問題 | No.875 Range Mindex Query |
ユーザー | convexineq |
提出日時 | 2019-09-07 16:13:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 337 ms / 2,000 ms |
コード長 | 2,333 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 87,204 KB |
実行使用メモリ | 92,832 KB |
最終ジャッジ日時 | 2023-09-09 04:08:01 |
合計ジャッジ時間 | 5,342 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,392 KB |
testcase_01 | AC | 90 ms
76,300 KB |
testcase_02 | AC | 94 ms
76,460 KB |
testcase_03 | AC | 75 ms
75,736 KB |
testcase_04 | AC | 82 ms
76,328 KB |
testcase_05 | AC | 74 ms
71,272 KB |
testcase_06 | AC | 87 ms
76,560 KB |
testcase_07 | AC | 91 ms
76,480 KB |
testcase_08 | AC | 80 ms
75,584 KB |
testcase_09 | AC | 82 ms
76,252 KB |
testcase_10 | AC | 94 ms
76,328 KB |
testcase_11 | AC | 337 ms
92,832 KB |
testcase_12 | AC | 310 ms
90,224 KB |
testcase_13 | AC | 286 ms
89,416 KB |
testcase_14 | AC | 294 ms
89,544 KB |
testcase_15 | AC | 325 ms
92,560 KB |
testcase_16 | AC | 303 ms
91,588 KB |
testcase_17 | AC | 319 ms
92,748 KB |
testcase_18 | AC | 313 ms
92,484 KB |
ソースコード
# coding: utf-8 # Your code here! """ セグメント木(区間演算、1点更新) 0-indexed, 関数は閉区間 """ class segment_tree: """ N: 処理する区間の長さ 長さNの配列 a で初期化 a を与えない場合、単位元で初期化 """ def __init__(self, N, a=None): #演算子および単位元をここで定義する。 # 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) if a != None: self.tree[self.N0-1:self.N0-1+N] = a[:] for k in range(self.N0-2,-1,-1): self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2]) # 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(self.tree[R-1],s) 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] ########################################################################### # ARC008D # https://atcoder.jp/contests/arc008/submissions/7368792 ########################################################################### 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,a) ra = [0]*(n) for i,ai in enumerate(a): 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)