結果

問題 No.1095 Smallest Kadomatsu Subsequence
コンテスト
ユーザー 小野寺健
提出日時 2021-11-04 20:55:21
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 2,023 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 107,264 KB
最終ジャッジ日時 2024-10-15 03:15:35
合計ジャッジ時間 9,009 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 13 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
m0 = l0 = l1 = r0 = r1 = nil
1.upto(N-2) {|i|
	m1 = A[i]
	update_l = update_r = false
	if not m0 then
		l0 = A[0] if A[0] < m1
		l1 = A[0] if A[0] > m1
		update_r = true
	else
		if not l0 then
			l0 = m0 if m0 < m1
		elsif l0 > m0
			l0 = m0
		end
		if not l1 then
			l1 = m0 if m0 > m1
		elsif l1 < m1 and m0 < m1 then
			update_l = true
		elsif l1 > m1 and m0 > m1 then
			l1 = m0 if m0 < l1
		else
			l1 = m0 if m0 > l1
		end
		
		if not r0 or r0 == m1 then
			update_r = true
		end
		if not r1 or r1 >= m1 or m0 < m1 then
			update_r = true
		end
	end
	l0, l1 = st.query(0, i, m1, 0, 0, N) if update_l
	r0, r1 = st.query(i+1, N, m1, 0, 0, N) if update_r
	if l0 and r0 then
		x = l0 + m1 + r0
		min = x if min > x
	end
	if l1 and r1 then
		x = l1 + m1 + r1
		min = x if min > x
	end
	m0 = m1
}

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