結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2022-11-04 03:02:00 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 1,487 ms / 2,000 ms |
コード長 | 2,243 bytes |
コンパイル時間 | 33 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 35,968 KB |
最終ジャッジ日時 | 2024-07-18 07:28:44 |
合計ジャッジ時間 | 19,958 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
Syntax OK
ソースコード
class RangeUpdateQueryattr_reader :n, :dat, :lazy# @param [Integer] len 区間の長さdef initialize(len, init: -1)@n = 1@n *= 2 while @n < len@dat = Array.new(2 * @n - 1, init)@lazy = Array.new(2 * @n - 1)end# @param [Integer] l 更新範囲の左端# @param [Integer] r 更新範囲の右端# @param [Integer] x 更新する値def update(l, r, x)fill(l, r, x, 0, 0, n - 1)end# @param [Integer] idx 取得したい値の箇所def find(idx)sum(idx, idx, 0, 0, n - 1)enddef find_min(l, r)min(l, r, 0, 0, n - 1)endprivate# @param [Integer] a 探索範囲の左端# @param [Integer] b 探索範囲の右端# @param [Integer] x 更新する値# @param [Integer] idx 現在位置# @param [Integer] l 現在の探索範囲の左端# @param [Integer] r 現在の探索範囲の右端def fill(a, b, x, idx, l, r)return if r < a || b < levaluate(idx, l, r)if a <= l && r <= b@lazy[idx] = xelsefill(a, b, x, idx * 2 + 1, l, (l + r) / 2)fill(a, b, x, idx * 2 + 2, (l + r) / 2 + 1, r)endenddef evaluate(idx, l, r)return if lazy[idx].nil?@dat[idx] = lazy[idx]if r - l > 0@lazy[2 * idx + 1] = lazy[idx]@lazy[2 * idx + 2] = lazy[idx]end@lazy[idx] = nilenddef sum(a, b, idx, l, r)return 0 if r < a || b < levaluate(idx, l, r)if a <= l && r <= bdat[idx]elsevl = sum(a, b, idx * 2 + 1, l, (l + r) / 2)vr = sum(a, b, idx * 2 + 2, (l + r) / 2 + 1, r)vl + vrendenddef min(a, b, idx, l, r)return 0 if r < a || b < levaluate(idx, l, r)if a <= l && r <= bdat[idx]elsevl = sum(a, b, idx * 2 + 1, l, (l + r) / 2)vr = sum(a, b, idx * 2 + 2, (l + r) / 2 + 1, r)vl < vr ? vl : vrendendendN = gets.to_iA = gets.split.map(&:to_i)left = Hash.new(Float::INFINITY)right = Hash.new(-Float::INFINITY)A.each_with_index do |a, i|left[a] = i if left[a] > iright[a] = iendruq = RangeUpdateQuery.new(N)A.uniq.sort.each do |a|l = left[a]r = right[a]ruq.update(l, r, a)endputs (0...N).map { |i| ruq.find(i) }.join(' ')