#670954 (Kuin) No.1558 Derby Live

• 問題: No.1558 Derby Live
• ユーザー: tatt61880
• 提出日時: 2021-06-27 23:59:49
• 言語: Kuin (KuinC++ v.2021.9.17)
• 結果: AC
• 実行時間: 667 ms / 2,000 ms
• コード長: 3,317 bytes
• コンパイル時間: 3,049 ms
• コンパイル使用メモリ: 150,448 KB
• 実行使用メモリ: 10,368 KB
• 最終ジャッジ日時: 2024-09-16 12:39:15
• 合計ジャッジ時間: 20,977 ms
• ジャッジサーバーID （参考情報）: judge6 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 33

ソースコード

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
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)
            var ans: []int :: #[n]int
            for i(0, n - 1)
                do ans[data.data[i] - 1] :: i
            end for
            for i(0, n - 1)
                do cui@print("\{ans[i] + 1}" ~ (i = n - 1 ?("\n", " ")))
            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 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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX