結果
問題 | No.1558 Derby Live |
ユーザー | tatt61880 |
提出日時 | 2021-06-27 23:21:50 |
言語 | Kuin (KuinC++ v.2021.9.17) |
結果 |
AC
|
実行時間 | 825 ms / 2,000 ms |
コード長 | 3,337 bytes |
コンパイル時間 | 3,378 ms |
コンパイル使用メモリ | 148,308 KB |
実行使用メモリ | 10,112 KB |
最終ジャッジ日時 | 2024-09-16 12:38:01 |
合計ジャッジ時間 | 27,816 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 619 ms
10,112 KB |
testcase_01 | AC | 825 ms
10,112 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 517 ms
5,376 KB |
testcase_04 | AC | 248 ms
6,784 KB |
testcase_05 | AC | 290 ms
6,528 KB |
testcase_06 | AC | 499 ms
6,272 KB |
testcase_07 | AC | 9 ms
5,376 KB |
testcase_08 | AC | 501 ms
8,192 KB |
testcase_09 | AC | 519 ms
8,192 KB |
testcase_10 | AC | 535 ms
8,448 KB |
testcase_11 | AC | 550 ms
8,576 KB |
testcase_12 | AC | 583 ms
8,960 KB |
testcase_13 | AC | 599 ms
8,832 KB |
testcase_14 | AC | 617 ms
9,088 KB |
testcase_15 | AC | 637 ms
9,216 KB |
testcase_16 | AC | 656 ms
9,344 KB |
testcase_17 | AC | 682 ms
9,344 KB |
testcase_18 | AC | 720 ms
9,728 KB |
testcase_19 | AC | 742 ms
9,856 KB |
testcase_20 | AC | 757 ms
10,112 KB |
testcase_21 | AC | 736 ms
9,728 KB |
testcase_22 | AC | 766 ms
9,856 KB |
testcase_23 | AC | 770 ms
10,112 KB |
testcase_24 | AC | 733 ms
9,856 KB |
testcase_25 | AC | 757 ms
9,856 KB |
testcase_26 | AC | 756 ms
10,112 KB |
testcase_27 | AC | 746 ms
9,856 KB |
testcase_28 | AC | 750 ms
9,856 KB |
testcase_29 | AC | 750 ms
9,984 KB |
testcase_30 | AC | 723 ms
9,856 KB |
testcase_31 | AC | 744 ms
9,728 KB |
testcase_32 | AC | 750 ms
9,984 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
ソースコード
func main() var n: int :: cui@inputInt() var m: int :: cui@inputInt() var q: int :: cui@inputInt() var seg: @SegmentTree :: (#@SegmentTree).init(m) for(1, q) var type: int :: cui@inputInt() switch(type) case 1 var d: int :: cui@inputInt() - 1 var p: []int :: #[n]int for i(0, n - 1) do p[i] :: cui@inputInt() end for do seg.update(d, (#@Data).init(p)) case 2 var s: int :: cui@inputInt() var data: @Data :: seg.query(0, s) for rank(1, n) for i(0, n - 1) if(data.data[i] = rank) do cui@print("\{i + 1}" ~ (rank = n ?("\n", " "))) break i end if end for end for case 3 var l: int :: cui@inputInt() - 1 var r: int :: cui@inputInt() var data: @Data :: seg.query(l, r) var sum: int :: 0 for i(0, n - 1) do sum :+ (data.data[i] - 1 - i).abs() end for do cui@print("\{sum}\n") end switch end for end func class SegmentTree() var ie: @Data var size: int var node: []@Data var lasy: []@Data +func init(n: int): SegmentTree do me.size :: 1 while(me.size < n) do me.size :* 2 end while do me.node :: #[2 * me.size]@Data do me.lasy :: ##me.node ret me end func func eval(k: int) if(me.lasy[k] =& null) ret end if if(k < me.size - 1) do me.lasy[k * 2 + 1] :: ##me.lasy[k] do me.lasy[k * 2 + 2] :: ##me.lasy[k] end if do me.node[k] :: ##me.lasy[k] do me.lasy[k] :: null end func +func update(idx: int, val: @Data) do me.updateRange(idx, idx + 1, val) end func +func updateRange(a: int, b: int, val: @Data) do me.updateRangeSub(a, b, val, 0, 0, me.size) end func +func updateRangeSub(a: int, b: int, val: @Data, k: int, l: int, r: int) do me.eval(k) if(a <= l & r <= b) do me.lasy[k] :: ##val do me.eval(k) elif(a < r & l < b) do me.updateRangeSub(a, b, val, k * 2 + 1, l, (l + r) / 2) do me.updateRangeSub(a, b, val, k * 2 + 2, (l + r) / 2, r) do me.node[k] :: ##me.op(me.node[k * 2 + 1], me.node[k * 2 + 2]) end if end func +func query(a: int, b: int): @Data ret ##me.querySub(a, b, 0, 0, me.size) end func func querySub(a: int, b: int, k: int, l: int, r: int): @Data do me.eval(k) if(b <= l | r <= a) ret null end if if(a <= l & r <= b) ret ##me.node[k] end if var vl: @Data :: me.querySub(a, b, 2 * k + 1, l, (l + r) / 2) var vr: @Data :: me.querySub(a, b, 2 * k + 2, (l + r) / 2, r) ret ##me.op(vl, vr) end func +*func toStr(): []char var padding: int :: 1 while(padding <= me.size) do padding :* 2 end while do padding :- 1 var res: []char :: "" var s: int :: 0 var e: int :: 0 var n: int :: 1 const digit: int :: 7 var strNull: []char :: " ".repeat(digit - 6) ~ "invalid" while(padding > 0) do padding :/ 2 for i(s, e) do res :~ " ".repeat((digit + 1) * padding) do res :~ "\{me.node[i] =& null ?("null", me.node[i].toStr())}|" end for do res :~ "\n" do n :* 2 do s :: e + 1 do e :: s + n - 1 end while ret res end func func op(d1: @Data, d2: @Data): @Data if(d1 =& null) ret ##d2 elif(d2 =& null) ret ##d1 end if var res: @Data :: ##d1 for i(0, ^d1.data - 1) do res.data[i] :: d2.data[d1.data[i] - 1] end for ret res end func end class class Data() +var data: []int +func init(arr: []int): Data do me.data :: arr ret me end func end class