結果
問題 | No.875 Range Mindex Query |
ユーザー | qsako6 |
提出日時 | 2019-09-07 16:35:14 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 1,400 ms / 2,000 ms |
コード長 | 1,278 bytes |
コンパイル時間 | 88 ms |
コンパイル使用メモリ | 11,288 KB |
実行使用メモリ | 29,964 KB |
最終ジャッジ日時 | 2023-09-09 04:31:24 |
合計ジャッジ時間 | 11,752 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 81 ms
15,220 KB |
testcase_01 | AC | 86 ms
15,144 KB |
testcase_02 | AC | 91 ms
15,300 KB |
testcase_03 | AC | 84 ms
15,176 KB |
testcase_04 | AC | 85 ms
15,180 KB |
testcase_05 | AC | 83 ms
15,272 KB |
testcase_06 | AC | 86 ms
15,052 KB |
testcase_07 | AC | 89 ms
15,352 KB |
testcase_08 | AC | 88 ms
15,116 KB |
testcase_09 | AC | 86 ms
15,340 KB |
testcase_10 | AC | 90 ms
15,184 KB |
testcase_11 | AC | 1,218 ms
26,828 KB |
testcase_12 | AC | 963 ms
23,244 KB |
testcase_13 | AC | 933 ms
29,372 KB |
testcase_14 | AC | 919 ms
27,400 KB |
testcase_15 | AC | 1,178 ms
29,572 KB |
testcase_16 | AC | 1,297 ms
29,644 KB |
testcase_17 | AC | 1,400 ms
29,864 KB |
testcase_18 | AC | 1,385 ms
29,964 KB |
コンパイルメッセージ
Main.rb:43: warning: mismatched indentations at 'end' with 'class' at 1 Syntax OK
ソースコード
class RMQ def initialize(n, inf = (1<<31) - 1) @n = n, @l = 1, @inf = inf while @l < n @l <<= 1 end @data = Array.new(@l * 2, @inf) end def update(i, x) i += @l @data[i] = x i >>= 1 while i > 0 @data[i] = min(@data[i * 2], @data[i * 2 + 1]) i >>= 1 end true end # minimum of [l, r) def query(l, r) _query(l, r, 1, 0, @l) end def [](k) @data[@l + k] end private def _query(l, r, k, sl, sr) return @inf if sr <= l || r <= sl return @data[k] if l <= sl && sr <= r dl = _query(l, r, k * 2, sl, (sl + sr) / 2) dr = _query(l, r, k * 2 + 1, (sl + sr) / 2, sr) min(dl, dr) end def min(a, b) return (a > b ? b : a) end end h = {} n, q = gets.split.map(&:to_i) a = gets.split.map(&:to_i) rmq = RMQ.new(n) n.times do |i| h[a[i]] = i rmq.update(i, a[i]) end ans = [] q.times do c, l, r = gets.split.map(&:to_i) l -= 1 r -= 1 if c == 1 tmpl = rmq[l] tmpr = rmq[r] rmq.update(l, tmpr) rmq.update(r, tmpl) h[tmpr] = l h[tmpl] = r else ans << h[rmq.query(l, r + 1)] + 1 end end puts ans