結果
問題 | No.789 範囲の合計 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-04-05 20:39:33 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 168 ms / 1,000 ms |
コード長 | 6,149 bytes |
コンパイル時間 | 12,314 ms |
コンパイル使用メモリ | 231,532 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-10-02 02:42:20 |
合計ジャッジ時間 | 13,274 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 161 ms
6,784 KB |
testcase_03 | AC | 113 ms
5,248 KB |
testcase_04 | AC | 168 ms
7,168 KB |
testcase_05 | AC | 151 ms
7,168 KB |
testcase_06 | AC | 155 ms
6,656 KB |
testcase_07 | AC | 104 ms
5,248 KB |
testcase_08 | AC | 144 ms
6,400 KB |
testcase_09 | AC | 148 ms
7,168 KB |
testcase_10 | AC | 159 ms
6,144 KB |
testcase_11 | AC | 141 ms
6,272 KB |
testcase_12 | AC | 142 ms
6,784 KB |
testcase_13 | AC | 1 ms
5,248 KB |
testcase_14 | AC | 1 ms
5,248 KB |
ソースコード
package main import ( "bufio" "fmt" "os" ) func demo() { seg := NewDynamicSegTreeSparse(0, 10, false) root := seg.NewRoot() root = seg.Set(root, 1, 1) fmt.Println(seg.Query(root, 0, 1), seg.GetAll(root)) } func main() { // https://yukicoder.me/problems/no/789 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() seg := NewDynamicSegTreeSparse(0, 1e9+10, false) root := seg.NewRoot() var n int fmt.Fscan(in, &n) res := 0 for i := 0; i < n; i++ { var op int fmt.Fscan(in, &op) if op == 0 { var a, b int fmt.Fscan(in, &a, &b) root = seg.Update(root, a, b) } else { var left, right int fmt.Fscan(in, &left, &right) res += seg.Query(root, left, right+1) } } fmt.Fprintln(out, res) } type E = int func e() E { return 0 } func op(a, b E) E { return a + b } type DynamicSegTreeSparse struct { L, R int persistent bool unit E } type SegNode struct { idx int l, r *SegNode x, prod E } func NewDynamicSegTreeSparse(left, right int, persistent bool) *DynamicSegTreeSparse { return &DynamicSegTreeSparse{ L: left, R: right, persistent: persistent, unit: e(), } } func (ds *DynamicSegTreeSparse) NewRoot() *SegNode { return nil } // L<=left<=right<=R func (ds *DynamicSegTreeSparse) Query(root *SegNode, left, right int) E { if left == right { return ds.unit } x := ds.unit ds._queryRec(root, ds.L, ds.R, left, right, &x) return x } func (ds *DynamicSegTreeSparse) QueryAll(root *SegNode) E { return ds.Query(root, ds.L, ds.R) } // L<=index<R func (ds *DynamicSegTreeSparse) Set(root *SegNode, index int, value E) *SegNode { return ds._setRec(root, ds.L, ds.R, index, value) } func (ds *DynamicSegTreeSparse) Get(root *SegNode, index int) E { return ds._getRec(root, index) } // L<=left<R func (ds *DynamicSegTreeSparse) Update(root *SegNode, index int, value E) *SegNode { return ds._updateRec(root, ds.L, ds.R, index, value) } // L<=right<=R func (ds *DynamicSegTreeSparse) MinLeft(root *SegNode, right int, check func(E) bool) int { x := ds.unit return ds._minLeftRec(root, ds.L, ds.R, right, check, &x) } // L<=left<=R func (ds *DynamicSegTreeSparse) MaxRight(root *SegNode, left int, check func(E) bool) int { x := ds.unit return ds._maxRightRec(root, ds.L, ds.R, left, check, &x) } func (ds *DynamicSegTreeSparse) GetAll(root *SegNode) []struct { index int value E } { res := make([]struct { index int value E }, 0) ds._getAllRec(root, &res) return res } func (ds *DynamicSegTreeSparse) _pushUp(node *SegNode) { node.prod = node.x if node.l != nil { node.prod = op(node.l.prod, node.prod) } if node.r != nil { node.prod = op(node.prod, node.r.prod) } } func (ds *DynamicSegTreeSparse) _newNode(idx int, x E) *SegNode { return &SegNode{idx: idx, x: x, prod: x} } func (ds *DynamicSegTreeSparse) _copyNode(node *SegNode) *SegNode { if node == nil || !ds.persistent { return node } return &SegNode{idx: node.idx, l: node.l, r: node.r, x: node.x, prod: node.prod} } func (ds *DynamicSegTreeSparse) _setRec(root *SegNode, l, r, i int, x E) *SegNode { if root == nil { root = ds._newNode(i, x) return root } root = ds._copyNode(root) if root.idx == i { root.x = x ds._pushUp(root) return root } m := (l + r) >> 1 if i < m { if root.idx < i { root.idx, i = i, root.idx root.x, x = x, root.x } root.l = ds._setRec(root.l, l, m, i, x) } else { if i < root.idx { root.idx, i = i, root.idx root.x, x = x, root.x } root.r = ds._setRec(root.r, m, r, i, x) } ds._pushUp(root) return root } func (ds *DynamicSegTreeSparse) _updateRec(root *SegNode, l, r, i int, x E) *SegNode { if root == nil { root = ds._newNode(i, x) return root } root = ds._copyNode(root) if root.idx == i { root.x = op(root.x, x) ds._pushUp(root) return root } m := (l + r) >> 1 if i < m { if root.idx < i { root.idx, i = i, root.idx root.x, x = x, root.x } root.l = ds._updateRec(root.l, l, m, i, x) } else { if i < root.idx { root.idx, i = i, root.idx root.x, x = x, root.x } root.r = ds._updateRec(root.r, m, r, i, x) } ds._pushUp(root) return root } func (ds *DynamicSegTreeSparse) _queryRec(root *SegNode, l, r, ql, qr int, x *E) { ql = max(ql, l) qr = min(qr, r) if ql >= qr || root == nil { return } if l == ql && r == qr { *x = op(*x, root.prod) return } m := (l + r) >> 1 ds._queryRec(root.l, l, m, ql, qr, x) if ql <= root.idx && root.idx < qr { *x = op(*x, root.x) } ds._queryRec(root.r, m, r, ql, qr, x) } func (ds *DynamicSegTreeSparse) _minLeftRec(root *SegNode, l, r, qr int, check func(E) bool, x *E) int { if root == nil || qr <= l { return ds.L } if check(op(root.prod, *x)) { *x = op(root.prod, *x) return ds.L } m := (l + r) >> 1 k := ds._minLeftRec(root.r, m, r, qr, check, x) if k != ds.L { return k } if root.idx < qr { *x = op(root.x, *x) if !check(*x) { return root.idx + 1 } } return ds._minLeftRec(root.l, l, m, qr, check, x) } func (ds *DynamicSegTreeSparse) _maxRightRec(root *SegNode, l, r, ql int, check func(E) bool, x *E) int { if root == nil || r <= ql { return ds.R } if check(op(*x, root.prod)) { *x = op(*x, root.prod) return ds.R } m := (l + r) >> 1 k := ds._maxRightRec(root.l, l, m, ql, check, x) if k != ds.R { return k } if ql <= root.idx { *x = op(*x, root.x) if !check(*x) { return root.idx } } return ds._maxRightRec(root.r, m, r, ql, check, x) } func (ds *DynamicSegTreeSparse) _getAllRec(root *SegNode, res *[]struct { index int value E }) { if root == nil { return } ds._getAllRec(root.l, res) *res = append(*res, struct { index int value E }{root.idx, root.x}) ds._getAllRec(root.r, res) } func (ds *DynamicSegTreeSparse) _getRec(root *SegNode, idx int) E { if root == nil { return ds.unit } if idx == root.idx { return root.x } if idx < root.idx { return ds._getRec(root.l, idx) } return ds._getRec(root.r, idx) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b }