結果

問題 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0