結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2021-03-26 02:57:53 |
言語 | Kuin (KuinC++ v.2021.9.17) |
結果 |
AC
|
実行時間 | 660 ms / 2,000 ms |
コード長 | 4,120 bytes |
コンパイル時間 | 2,848 ms |
コンパイル使用メモリ | 149,624 KB |
実行使用メモリ | 49,024 KB |
最終ジャッジ日時 | 2024-09-16 12:06:38 |
合計ジャッジ時間 | 10,297 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
func main()const invalid: int :: lib@intMaxvar n: int :: cui@inputInt()var a: []int :: #[n]intfor i(0, n - 1)do a[i] :: cui@inputInt()end forvar lMin: []int :: #[n]intvar rMin: []int :: #[n]intblockvar min: int :: a[0]for i(1, n - 1)do lMin[i] :: mindo min :: [min, a[i]].min()end forend blockblockvar min: int :: a[n - 1]for i(n - 2, 0, -1)do rMin[i] :: mindo min :: [min, a[i]].min()end forend blockvar lLow: []int :: #[n]intvar rLow: []int :: #[n]intblockvar set: Set :: #Setdo set.ins(a[0])for i(1, n - 1)var p: Node :: set.lower_bound(a[i])do lLow[i] :: p =& null ?(-1, p.key)do set.ins(a[i])end forend blockblockvar set: Set :: #Setdo set.ins(a[n - 1])for i(n - 2, 0, -1)var p: Node :: set.lower_bound(a[i])do rLow[i] :: p =& null ?(-1, p.key)do set.ins(a[i])end forend blockvar ans: int :: invalidfor 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; vvar ll: int :: lLow[i]var rl: int :: rLow[i]if(ll > v & v < rl)do ans :: [ans, ll + v + rl].min()end ifend forif(ans = invalid)do ans :: -1end ifdo cui@print("\{ans}\n")class Node()+var height: int+var key: int+var lst: Node+var rst: Node+*func toStr(): []charret "\{me.key}"end func+func init(height: int, key: int): Nodedo me.height :: heightdo me.key :: keydo me.lst :: nulldo me.rst :: nullret meend funcend classfunc height(t: Node): intif(t =& null)ret 0elseret t.heightend ifend funcfunc bias(t: Node): intret height(t.lst) - height(t.rst)end funcfunc modHeight(t: Node)do t.height :: 1 + lib@max(height(t.lst), height(t.rst))end funcfunc rotateL(v: Node): Nodevar u: Node :: v.rstvar t: Node :: u.lstdo u.lst :: vdo v.rst :: tret uend funcfunc rotateR(u: Node): Nodevar v: Node :: u.lstvar t: Node :: v.rstdo v.rst :: udo u.lst :: tret vend funcfunc rotateLR(t: Node): Nodedo t.lst :: rotateL(t.lst)ret rotateR(t)end funcfunc rotateRL(t: Node): Nodedo t.rst :: rotateR(t.rst)ret rotateL(t)end func; AVL Setclass Set()var root: Nodevar change: boolvar lmax: int+func balanceL(t: Node): Nodeif(!me.change)ret tend ifvar h: int :: height(t)if(bias(t) = 2)if(bias(t.lst) >= 0)do t :: rotateR(t)elsedo t :: rotateLR(t)end ifelsedo modHeight(t)end ifdo me.change :: (h <> height(t))ret tend func+func balanceR(t: Node): Nodeif(!me.change)ret tend ifvar h: int :: height(t)if(bias(t) = -2)if(bias(t.rst) <= 0)do t :: rotateL(t)elsedo t :: rotateRL(t)end ifelsedo modHeight(t)end ifdo me.change :: (h <> height(t))ret tend func+func ins(key: int)do me.root :: me.insSub(me.root, key)end func+func insSub(t: Node, key: int): Nodeif(t =& null)do me.change :: trueret(#Node).init(1, key)elif(key < t.key)do t.lst :: me.insSub(t.lst, key)ret me.balanceL(t)elif(key > t.key)do t.rst :: me.insSub(t.rst, key)ret me.balanceR(t)elsedo me.change :: falseret tend ifend func+func find(key: int): Nodevar t: Node :: me.rootwhile loop(t <>& null)if(key < t.key)do t :: t.lstelif(key > t.key)do t :: t.rstelsebreak loopend ifend whileret tend func+func lower_bound(key: int): Nodevar t: Node :: me.rootvar last: Nodewhile loop(t <>& null)if(key < t.key)if(t.lst =& null)if(t.key >= key)ret telseret lastend ifend ifdo t :: t.lstelif(key > t.key)if(t.rst =& null)if(t.key >= key)ret telseret lastend ifend ifdo t :: t.rstelsebreak loopend ifdo last :: tend whileret tend funcend classend func