結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー 小野寺健小野寺健
提出日時 2021-11-04 16:42:24
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 105,844 KB
最終ジャッジ日時 2024-04-22 16:18:07
合計ジャッジ時間 10,476 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
17,792 KB
testcase_01 AC 91 ms
12,160 KB
testcase_02 AC 92 ms
12,160 KB
testcase_03 AC 96 ms
12,160 KB
testcase_04 AC 95 ms
12,416 KB
testcase_05 AC 96 ms
12,160 KB
testcase_06 AC 95 ms
12,288 KB
testcase_07 AC 94 ms
12,288 KB
testcase_08 AC 96 ms
12,288 KB
testcase_09 AC 95 ms
12,288 KB
testcase_10 AC 95 ms
12,288 KB
testcase_11 AC 95 ms
12,160 KB
testcase_12 AC 95 ms
12,160 KB
testcase_13 AC 334 ms
16,512 KB
testcase_14 AC 334 ms
16,512 KB
testcase_15 AC 333 ms
16,640 KB
testcase_16 AC 331 ms
16,384 KB
testcase_17 AC 332 ms
16,384 KB
testcase_18 AC 362 ms
16,256 KB
testcase_19 AC 377 ms
16,512 KB
testcase_20 AC 353 ms
16,512 KB
testcase_21 AC 342 ms
16,384 KB
testcase_22 AC 347 ms
16,384 KB
testcase_23 TLE -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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