結果
問題 | No.1439 Let's Compare!!!! |
ユーザー | tatt61880 |
提出日時 | 2021-03-28 10:41:35 |
言語 | Kuin (KuinC++ v.2021.9.17) |
結果 |
AC
|
実行時間 | 727 ms / 2,000 ms |
コード長 | 5,094 bytes |
コンパイル時間 | 3,165 ms |
コンパイル使用メモリ | 148,960 KB |
実行使用メモリ | 27,608 KB |
最終ジャッジ日時 | 2024-09-16 12:14:21 |
合計ジャッジ時間 | 8,871 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 15 ms
6,940 KB |
testcase_08 | AC | 16 ms
6,940 KB |
testcase_09 | AC | 6 ms
6,940 KB |
testcase_10 | AC | 727 ms
27,092 KB |
testcase_11 | AC | 438 ms
14,036 KB |
testcase_12 | AC | 428 ms
14,156 KB |
testcase_13 | AC | 708 ms
27,608 KB |
testcase_14 | AC | 721 ms
27,608 KB |
testcase_15 | AC | 375 ms
7,128 KB |
testcase_16 | AC | 285 ms
6,940 KB |
testcase_17 | AC | 247 ms
6,944 KB |
testcase_18 | AC | 202 ms
6,944 KB |
ソースコード
func main()var n: int :: cui@inputInt()var s: []char :: cui@input()var t: []char :: cui@input()var set: @Set :: #@Setfor i(0, n - 1)if(s[i] <> t[i])do set.add(i)end ifend forvar q: int :: cui@inputInt()for(1, q)var c: char :: cui@inputChar()var x: int :: cui@inputInt() - 1var y: int :: cui@inputInt()if(c = 'S')do s[x] :: '0'.offset(y)elsedo t[x] :: '0'.offset(y)end ifif(s[x] = t[x])do set.del(x)elsedo set.add(x)end ifvar begin: @Node :: set.begin()if(begin =& null)do cui@print("=")elsevar i: int :: begin.keyif(s[i] < t[i])do cui@print("<")elif(s[i] > t[i])do cui@print(">")end ifend ifdo cui@print("\n")end forend funcclass Node()+var height: int+var key: int+var prev: Node+var next: Node+var lst: Node+var rst: Node+*func toStr(): []charret me.key.toStr()end func+func init(key: int, prev: Node, next: Node): Nodedo me.height :: 1do me.key :: keydo me.prev :: prevdo me.next :: nextret meend funcend class; AVL Treeclass Set()var root: @Nodevar change: boolvar lMax: intvar num: int+func size(): intret me.numend func+func begin(): @Nodevar t: @Node :: me.rootif(t =& null)ret nullend ifwhile(true)if(t.lst =& null)ret tend ifdo t :: t.lstend whileend func+func add(key: int)do me.root :: me.addSub(me.root, null, key)end funcfunc addSub(t: @Node, parent: @Node, key: int): @Nodeif(t =& null)var a: @Nodedo me.change :: trueif(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 :: aend ifdo parent.prev :: aelif(key > parent.key)do a :: (#@Node).init(key, parent, parent.next)if(parent.next <>& null)do parent.next.prev :: aend ifdo parent.next :: aend ifdo me.num :+ 1ret aelif(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)elsedo me.change :: falseret tend ifend func+func del(key: int)do me.root :: me.delSub(me.root, key)end funcfunc delSub(t: @Node, key: int): @Nodeif(t =& null)do me.change :: falseret nullelif(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)elsedo me.num :- 1if(t.next <>& null)do t.next.prev :: t.prevend ifif(t.prev <>& null)do t.prev.next :: t.nextend ifif(t.lst =& null)do me.change :: trueret t.rstelsedo t.lst :: me.delSubMax(t.lst)do t.key :: me.lMaxret me.balanceR(t)end ifend ifend funcfunc delSubMax(t: @Node): @Nodeif(t.rst <>& null)do t.rst :: me.delSubMax(t.rst)ret me.balanceL(t)elsedo me.change :: truedo me.lMax :: t.keyret t.lstend 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 exist(key: int): boolret me.find(key) <>& nullend func+func lower_bound(key: int): @Nodevar t: @Node :: me.rootif(t =& null)ret nullend ifwhile(true)if(key < t.key)if(t.lst =& null)ret tend ifif(key > t.lst.key & t.lst.rst =& null)ret tend ifdo t :: t.lstelif(key > t.key)if(t.rst =& null)ret t.nextend ifdo t :: t.rstelseret tend ifend whileend funcfunc height(t: @Node): intret t =& null ?(0, t.height)end funcfunc bias(t: @Node): intret me.height(t.lst) - me.height(t.rst)end funcfunc modHeight(t: @Node)do t.height :: 1 + lib@max(me.height(t.lst), me.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 :: me.rotateL(t.lst)ret me.rotateR(t)end funcfunc rotateRL(t: @Node): @Nodedo t.rst :: me.rotateR(t.rst)ret me.rotateL(t)end funcfunc balanceL(t: @Node): @Nodeif(!me.change)ret tend ifvar h: int :: me.height(t)if(me.bias(t) = 2)if(me.bias(t.lst) >= 0)do t :: me.rotateR(t)elsedo t :: me.rotateLR(t)end ifelsedo me.modHeight(t)end ifdo me.change :: h <> me.height(t)ret tend funcfunc balanceR(t: @Node): @Nodeif(!me.change)ret tend ifvar h: int :: me.height(t)if(me.bias(t) = -2)if(me.bias(t.rst) <= 0)do t :: me.rotateL(t)elsedo t :: me.rotateRL(t)end ifelsedo me.modHeight(t)end ifdo me.change :: h <> me.height(t)ret tend funcend class