結果
問題 | No.875 Range Mindex Query |
ユーザー | pynomi |
提出日時 | 2019-09-07 18:48:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,455 ms / 2,000 ms |
コード長 | 1,177 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 86,756 KB |
実行使用メモリ | 169,108 KB |
最終ジャッジ日時 | 2023-09-09 07:49:22 |
合計ジャッジ時間 | 12,242 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
70,900 KB |
testcase_01 | AC | 111 ms
77,200 KB |
testcase_02 | AC | 126 ms
77,320 KB |
testcase_03 | AC | 80 ms
75,660 KB |
testcase_04 | AC | 98 ms
76,188 KB |
testcase_05 | AC | 86 ms
75,900 KB |
testcase_06 | AC | 110 ms
77,148 KB |
testcase_07 | AC | 112 ms
77,160 KB |
testcase_08 | AC | 98 ms
75,820 KB |
testcase_09 | AC | 97 ms
76,248 KB |
testcase_10 | AC | 123 ms
77,252 KB |
testcase_11 | AC | 1,435 ms
167,888 KB |
testcase_12 | AC | 1,198 ms
142,148 KB |
testcase_13 | AC | 1,169 ms
154,796 KB |
testcase_14 | AC | 1,157 ms
155,572 KB |
testcase_15 | AC | 1,455 ms
169,108 KB |
testcase_16 | AC | 1,004 ms
131,276 KB |
testcase_17 | AC | 1,005 ms
133,152 KB |
testcase_18 | AC | 976 ms
132,508 KB |
ソースコード
N, Q = map(int,input().split()) A = list(map(int,input().split())) queries = [[int(e)-1 for e in input().split()] for _ in range(Q)] # N: 処理する区間の長さ N0 = 2**(N-1).bit_length() INF = 2**31-1 data = [[INF,-1] for _ in range(2*N0)] # a_k の値を x に更新 def update(k, x): data[k+N0-1] = [x, k] k += N0-1 while k >= 0: k = (k - 1) // 2 if data[2*k+1] < data[2*k+2]: data[k] = data[2*k+1][:] else: data[k] = data[2*k+2][:] # 区間[l, r)の(最小値, インデックス) def query(l, r): L = l + N0; R = r + N0 s = [INF,-1] while L < R: if R & 1: R -= 1 if s > data[R-1]: s = data[R-1] if L & 1: if s > data[L-1]: s = data[L-1] L += 1 L >>= 1; R >>= 1 return s # 配列の初期化 for i, a in enumerate(A): update(i, a) def solve(q, l, r): if q == 0: al, li = query(l, l+1) ar, ri = query(r, r+1) update(l, ar) update(r, al) elif q == 1: m, i = query(l,r+1) print(i+1) for q, l, r in queries: solve(q, l, r)