結果
問題 | No.875 Range Mindex Query |
ユーザー | 6soukiti29 |
提出日時 | 2019-09-06 21:40:55 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 339 ms / 2,000 ms |
コード長 | 1,630 bytes |
コンパイル時間 | 2,968 ms |
コンパイル使用メモリ | 68,660 KB |
実行使用メモリ | 17,316 KB |
最終ジャッジ日時 | 2023-09-15 12:52:01 |
合計ジャッジ時間 | 6,107 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,088 KB |
testcase_01 | AC | 3 ms
5,100 KB |
testcase_02 | AC | 4 ms
5,144 KB |
testcase_03 | AC | 2 ms
5,188 KB |
testcase_04 | AC | 3 ms
5,288 KB |
testcase_05 | AC | 2 ms
5,096 KB |
testcase_06 | AC | 3 ms
5,100 KB |
testcase_07 | AC | 4 ms
5,260 KB |
testcase_08 | AC | 3 ms
5,096 KB |
testcase_09 | AC | 3 ms
5,080 KB |
testcase_10 | AC | 4 ms
5,176 KB |
testcase_11 | AC | 227 ms
13,856 KB |
testcase_12 | AC | 185 ms
11,268 KB |
testcase_13 | AC | 157 ms
15,928 KB |
testcase_14 | AC | 153 ms
15,132 KB |
testcase_15 | AC | 214 ms
16,456 KB |
testcase_16 | AC | 310 ms
16,348 KB |
testcase_17 | AC | 339 ms
16,620 KB |
testcase_18 | AC | 329 ms
17,316 KB |
ソースコード
import sequtils,strutils type item = tuple[a, i : int] segmenttree[I:static[int]] = array[2 shl I,item] # segT[0] にはnを入れる,要素数 <= 1 shl n proc update(ST : var segmenttree, index : int, n : item)= var j = index + (1 shl ST[0].a) flag = true ST[j] = n while flag and j > 1: if ST[j shr 1] != min(ST[j], ST[j xor 1]): ST[j shr 1] = min(ST[j], ST[j xor 1]) j = j shr 1 else: flag = false proc Rmin(ST : segmenttree; l : int ;r : int; a = 1 ; cnt = 0):item= if a shl (ST[0].a - cnt) - (1 shl ST[0].a) == l and ((a + 1) shl (ST[0].a - cnt)) - 1 - (1 shl ST[0].a) == r: return ST[a] else: var n : int n = (a shl 1) + 1 n = n shl (ST[0].a - cnt - 1) if n - (1 shl ST[0].a) <= l: return Rmin(ST, l, r, (a shl 1) + 1, cnt + 1) elif n - (1 shl ST[0].a) > r: return Rmin(ST, l, r, a shl 1, cnt + 1) else: return min(Rmin(ST, l, n - 1 - (1 shl ST[0].a), a shl 1, cnt + 1), Rmin(ST, n - (1 shl ST[0].a), r, (a shl 1) + 1, cnt + 1)) var N, Q : int (N, Q) = stdin.readline.split.map(parseInt) var A = stdin.readline.split.map(parseInt) st : segmenttree[18] st[0].a = 18 for i,a in A: st.update(i + 1, (a, i + 1)) for i in 1..Q: var line = stdin.readline.split.map(parseInt) var l = line[1] var r = line[2] if line[0] == 1: (A[l - 1], A[r - 1]) = (A[r - 1], A[l - 1]) st.update(l, (A[l - 1], l)) st.update(r, (A[r - 1], r)) else: echo st.Rmin(line[1], line[2]).i