結果

問題 No.1095 Smallest Kadomatsu Subsequence
コンテスト
ユーザー tatt61880
提出日時 2021-03-25 00:17:12
言語 Kuin
(KuinC++ v.2021.9.17)
結果
TLE  
実行時間 -
コード長 3,139 bytes
コンパイル時間 2,841 ms
コンパイル使用メモリ 149,616 KB
実行使用メモリ 49,152 KB
最終ジャッジ日時 2024-09-16 12:06:00
合計ジャッジ時間 10,632 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

func main()
	const invalid: int :: lib@intMax
	var n: int :: cui@inputInt()
	var a: []int :: #[n]int
	for i(0, n - 1)
		do a[i] :: cui@inputInt()
	end for
	var lMin: []int :: #[n]int
	var rMin: []int :: #[n]int
	block
		var min: int :: a[0]
		for i(1, n - 1)
			do lMin[i] :: min
			do min :: [min, a[i]].min()
		end for
	end block
	block
		var min: int :: a[n - 1]
		for i(n - 2, 0, -1)
			do rMin[i] :: min
			do min :: [min, a[i]].min()
		end for
	end block
	var lLow: []int :: #[n]int
	var rLow: []int :: #[n]int
	block
		var bin: BinaryTree :: #BinaryTree
		do bin.ins(a[0])
		for i(1, n - 1)
			var p: Node :: bin.lower_bound(a[i])
			do lLow[i] :: p =& null ?(-1, p.val)
			do bin.ins(a[i])
		end for
	end block
	block
		var bin: BinaryTree :: #BinaryTree
		do bin.ins(a[n - 1])
		for i(n - 2, 0, -1)
			var p: Node :: bin.lower_bound(a[i])
			do rLow[i] :: p =& null ?(-1, p.val)
			do bin.ins(a[i])
		end for
	end block
	
	var ans: int :: invalid
	for i(1, n - 2)
		var v: int :: a[i]
		; ^
		var lm: int :: lMin[i]
		var rm: int :: rMin[i]
		if(lm < v & v > rm)
			do ans :: [ans, lm + v + rm].min()
		end if
		; v
		var ll: int :: lLow[i]
		var rl: int :: rLow[i]
		if(ll > v & v < rl)
			do ans :: [ans, ll + v + rl].min()
		end if
	end for
	if(ans = invalid)
		do ans :: -1
	end if
	do cui@print("\{ans}\n")
	
	class Node()
		+var val: int
		+var left: Node
		+var right: Node
		+var parent: Node
		+*func toStr(): []char
			ret "\{me.val}"
		end func
		+func init(val: int, parent: Node): Node
			do me.val :: val
			do me.parent :: parent
			do me.left :: null
			do me.right :: null
			ret me
		end func
		+func next(): Node
			var n: Node :: me
			if(n.right <>& null)
				ret n.right.min()
			end if
			while(n.parent <>& null & n.parent.left <>& n)
				do n :: n.parent
			end while
			ret n.parent
		end func
		+func min(): Node
			var n: Node :: me
			while(n.left <>& null)
				do n :: n.left
			end while
			ret n
		end func
	end class
	
	class BinaryTree()
		var root: Node
		+func find(elem: int): Node
			var n: Node :: me.root
			while loop(n <>& null)
				if(elem < n.val)
					do n :: n.left
				elif(elem > n.val)
					do n :: n.right
				else
					break loop
				end if
			end while
			ret n
		end func
		+func lower_bound(elem: int): Node
			var n: Node :: me.root
			while loop(n <>& null)
				if(elem < n.val)
					if(n.left =& null)
						if(n.val >= elem)
							ret n
						else
							ret n.parent
						end if
					end if
					do n :: n.left
				elif(elem > n.val)
					if(n.right =& null)
						if(n.val >= elem)
							ret n
						else
							ret n.parent
						end if
					end if
					do n :: n.right
				else
					break loop
				end if
			end while
			ret n
		end func
		+func ins(elem: int)
			if(me.root =& null)
				do me.root :: (#Node).init(elem, null)
				ret
			end if
			var n: Node :: me.root
			var p: Node :: null
			while(n <>& null)
				do p :: n
				if(elem < n.val)
					do n :: n.left
				else
					do n :: n.right
				end if
			end while
			do n :: (#Node).init(elem, p)
			if(elem < p.val)
				do p.left :: n
			else
				do p.right :: n
			end if
		end func
	end class
end func
0