結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー 小野寺健
提出日時 2021-11-04 16:42:24
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 65 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 107,392 KB
最終ジャッジ日時 2024-10-14 15:27:09
合計ジャッジ時間 9,763 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

N = gets.to_i
A = gets.split(" ").map{|s| s.to_i}

class SegmentTree
	def initialize(a)
		@a = a
		n = 1
		while n < @a.length do
			n *= 2
		end
		@dat = Array.new(2*n-1) {Array.new}
		init(0, 0, a.length)
	end
	def merge(a, b)
		c = []
		while a.length > 0 and b.length > 0 do
			if a[0] <= b[0] then
				c << a.shift
			else
				c << b.shift
			end
		end
		if a.length > 0 then
			c += a
		else
			c += b
		end
		c
	end
	def init(k, l, r)
		if r - l == 1 then
			@dat[k] << @a[l]
		else
			lch = k * 2 + 1
			rch = k * 2 + 2
			init(lch, l, (l + r) / 2)
			init(rch, (l + r) / 2, r)
			@dat[k] = merge(@dat[lch].dup, @dat[rch].dup)
		end
	end
	def query(i, j, x, k, l, r)
		if j <= l or r <= i then
			return [nil, nil] 
		elsif i <= l and r <= j then
			min0 = @dat[k][0] < x ? @dat[k][0] : nil
			return [min0, @dat[k].bsearch{|y| y > x}]
		end
		lc0, lc1 = query(i, j, x, k * 2 + 1, l, (l + r) / 2)
		rc0, rc1 = query(i, j, x, k * 2 + 2, (l + r) / 2, r)
		min0 = lc0 ? (rc0 ? [lc0, rc0].min : lc0) : (rc0 ? rc0 : nil)
		min1 = lc1 ? (rc1 ? [lc1, rc1].min : lc1) : (rc1 ? rc1 : nil)
		return [min0, min1]
	end
	def dat
		@dat
	end
end

st = SegmentTree.new(A)
min = Float::INFINITY
1.upto(N-2) {|i|
	m = A[i]
	l0, l1 = st.query(0, i, m, 0, 0, N)
	r0, r1 = st.query(i+1, N, m, 0, 0, N)
	if l0 and r0 then
		x = l0 + m + r0
		min = x if min > x
	end
	if l1 and r1 then
		x = l1 + m + r1
		min = x if min > x
	end
}

puts min == Float::INFINITY ? -1 : min
0