結果

問題 No.318 学学学学学
ユーザー siman
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

class RangeUpdateQuery
attr_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)
end
def find_min(l, r)
min(l, r, 0, 0, n - 1)
end
private
# @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 < l
evaluate(idx, l, r)
if a <= l && r <= b
@lazy[idx] = x
else
fill(a, b, x, idx * 2 + 1, l, (l + r) / 2)
fill(a, b, x, idx * 2 + 2, (l + r) / 2 + 1, r)
end
end
def 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] = nil
end
def sum(a, b, idx, l, r)
return 0 if r < a || b < l
evaluate(idx, l, r)
if a <= l && r <= b
dat[idx]
else
vl = sum(a, b, idx * 2 + 1, l, (l + r) / 2)
vr = sum(a, b, idx * 2 + 2, (l + r) / 2 + 1, r)
vl + vr
end
end
def min(a, b, idx, l, r)
return 0 if r < a || b < l
evaluate(idx, l, r)
if a <= l && r <= b
dat[idx]
else
vl = 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 : vr
end
end
end
N = gets.to_i
A = 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] > i
right[a] = i
end
ruq = RangeUpdateQuery.new(N)
A.uniq.sort.each do |a|
l = left[a]
r = right[a]
ruq.update(l, r, a)
end
puts (0...N).map { |i| ruq.find(i) }.join(' ')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0