#635281 (Kuin) No.1095 Smallest Kadomatsu Subsequence

• 問題: No.1095 Smallest Kadomatsu Subsequence
• ユーザー: tatt61880
• 提出日時: 2021-03-28 11:30:51
• 言語: Kuin (KuinC++ v.2021.9.17)
• 結果: AC
• 実行時間: 719 ms / 2,000 ms
• コード長: 5,932 bytes
• コンパイル時間: 3,200 ms
• コンパイル使用メモリ: 149,464 KB
• 実行使用メモリ: 61,568 KB
• 最終ジャッジ日時: 2024-09-16 12:14:57
• 合計ジャッジ時間: 11,370 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
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 set: @Set :: #@Set
        do set.add(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.add(a[i])
        end for
    end block
    block
        var set: @Set :: #@Set
        do set.add(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.add(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")
end func
class Node()
    +var height: int
    +var key: int
    +var prev: Node
    +var next: Node
    +var lst: Node
    +var rst: Node
    +*func toStr(): []char
        ret me.key.toStr()
    end func
    +func init(key: int, prev: Node, next: Node): Node
        do me.height :: 1
        do me.key :: key
        do me.prev :: prev
        do me.next :: next
        ret me
    end func
end class
; AVL Tree
class Set()
    var root: @Node
    var change: bool
    var lMax: int
    var num: int
    +*func toStr(): []char
        ret me.toGraph(me.root, "", "")
    end func
    func toGraph(t: @Node, head: []char, bar: []char): []char
        var res: []char :: ""
        if(t <>& null)
            do res :~ me.toGraph(t.rst, head ~ "  ", "/")
            do res :~ head ~ bar ~ t.key.toStr() ~ "\n"
            do res :~ me.toGraph(t.lst, head ~ "  ", "`")
        end if
        ret res
    end func
    +func size(): int
        ret me.num
    end func
    +func begin(): @Node
        var t: @Node :: me.root
        if(t =& null)
            ret null
        end if
        while(true)
            if(t.lst =& null)
                ret t
            end if
            do t :: t.lst
        end while
    end func
    +func add(key: int)
        do me.root :: me.addSub(me.root, null, key)
    end func
    func addSub(t: @Node, parent: @Node, key: int): @Node
        if(t =& null)
            var a: @Node
            do me.change :: true
            if(parent =& null)
                do a :: (#@Node).init(key, null, null)
            elif(key < parent.key)
                do a :: (#@Node).init(key, parent.prev, parent)
                if(parent.prev <>& null)
                    do parent.prev.next :: a
                end if
                do parent.prev :: a
            elif(key > parent.key)
                do a :: (#@Node).init(key, parent, parent.next)
                if(parent.next <>& null)
                    do parent.next.prev :: a
                end if
                do parent.next :: a
            end if
            do me.num :+ 1
            ret a
        elif(key < t.key)
            do t.lst :: me.addSub(t.lst, t, key)
            ret me.balanceL(t)
        elif(key > t.key)
            do t.rst :: me.addSub(t.rst, t, key)
            ret me.balanceR(t)
        else
            do me.change :: false
            ret t
        end if
    end func
    +func del(key: int)
        do me.root :: me.delSub(me.root, key)
    end func
    func delSub(t: @Node, key: int): @Node
        if(t =& null)
            do me.change :: false
            ret null
        elif(key < t.key)
            do t.lst :: me.delSub(t.lst, key)
            ret me.balanceR(t)
        elif(key > t.key)
            do t.rst :: me.delSub(t.rst, key)
            ret me.balanceL(t)
        else
            do me.num :- 1
            if(t.next <>& null)
                do t.next.prev :: t.prev
            end if
            if(t.prev <>& null)
                do t.prev.next :: t.next
            end if
            if(t.lst =& null)
                do me.change :: true
                ret t.rst
            else
                do t.lst :: me.delSubMax(t.lst)
                do t.key :: me.lMax
                ret me.balanceR(t)
            end if
        end if
    end func
    func delSubMax(t: @Node): @Node
        if(t.rst <>& null)
            do t.rst :: me.delSubMax(t.rst)
            ret me.balanceL(t)
        else
            do me.change :: true
            do me.lMax :: t.key
            ret t.lst
        end if
    end func
    +func find(key: int): @Node
        var t: @Node :: me.root
        while loop(t <>& null)
            if(key < t.key)
                do t :: t.lst
            elif(key > t.key)
                do t :: t.rst
            else
                break loop
            end if
        end while
        ret t
    end func
    +func exist(key: int): bool
        ret me.find(key) <>& null
    end func
    +func lower_bound(key: int): @Node
        var t: @Node :: me.root
        if(t =& null)
            ret null
        end if
        while(true)
            if(key < t.key)
                if(t.lst =& null)
                    ret t
                end if
                do t :: t.lst
            elif(key > t.key)
                if(t.rst =& null)
                    ret t.next
                end if
                do t :: t.rst
            else
                ret t
            end if
        end while
    end func
    func height(t: @Node): int
        ret t =& null ?(0, t.height)
    end func
    func bias(t: @Node): int
        ret me.height(t.lst) - me.height(t.rst)
    end func
    func modHeight(t: @Node)
        do t.height :: 1 + lib@max(me.height(t.lst), me.height(t.rst))
    end func
    func rotateL(v: @Node): @Node
        var u: @Node :: v.rst
        var t: @Node :: u.lst
        do u.lst :: v
        do v.rst :: t
        ret u
    end func
    func rotateR(u: @Node): @Node
        var v: @Node :: u.lst
        var t: @Node :: v.rst
        do v.rst :: u
        do u.lst :: t
        ret v
    end func
    func rotateLR(t: @Node): @Node
        do t.lst :: me.rotateL(t.lst)
        ret me.rotateR(t)
    end func
    func rotateRL(t: @Node): @Node
        do t.rst :: me.rotateR(t.rst)
        ret me.rotateL(t)
    end func
    func balanceL(t: @Node): @Node
        if(!me.change)
            ret t
        end if
        var h: int :: me.height(t)
        if(me.bias(t) = 2)
            if(me.bias(t.lst) >= 0)
                do t :: me.rotateR(t)
            else
                do t :: me.rotateLR(t)
            end if
        else
            do me.modHeight(t)
        end if
        do me.change :: h <> me.height(t)
        ret t
    end func
    func balanceR(t: @Node): @Node
        if(!me.change)
            ret t
        end if
        var h: int :: me.height(t)
        if(me.bias(t) = -2)
            if(me.bias(t.rst) <= 0)
                do t :: me.rotateL(t)
            else
                do t :: me.rotateRL(t)
            end if
        else
            do me.modHeight(t)
        end if
        do me.change :: h <> me.height(t)
        ret t
    end func
end class
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX