examples/library_checker_point_add_range_sum.rs

• View this file on GitHub
• Last update: 2024-04-26 00:50:11+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• src/data_structure.rs
• src/data_structure/prefix_sum.rs
• src/data_structure/range_set.rs
• セグメント木 (src/data_structure/segment_tree.rs)
• src/data_structure/sorted_set.rs
• Union Find（素集合データ構造） (src/data_structure/union_find.rs)
• src/lib.rs
• src/math.rs
• src/math/binomial.rs
• src/utils.rs
• src/utils/binary_search.rs
• src/utils/compression.rs

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/point_add_range_sum

use proconio::input;
use rust_procon_lib::data_structure::segment_tree::segment_tree::SegmentTree;

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
    }

    let mut seg = SegmentTree::new(n, 0, |x, y| x + y);
    seg.construct(&a);

    for _ in 0..q {
        input! {
            t: usize,
        }

        match t {
            0 => {
                input! {
                    p: usize,
                    x: usize,
                }

                seg.update(p, seg.get(p) + x);
            }
            1 => {
                input! {
                    l: usize,
                    r: usize,
                }

                println!("{}", seg.prod(l, r));
            }
            _ => unreachable!(),
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	example_00	AC	5 ms	2 MB
Rust	max_random_00	AC	406 ms	27 MB
Rust	max_random_01	AC	360 ms	27 MB
Rust	max_random_02	AC	360 ms	27 MB
Rust	max_random_03	AC	380 ms	27 MB
Rust	max_random_04	AC	365 ms	27 MB
Rust	random_00	AC	346 ms	22 MB
Rust	random_01	AC	327 ms	24 MB
Rust	random_02	AC	268 ms	10 MB
Rust	random_03	AC	50 ms	17 MB
Rust	random_04	AC	90 ms	13 MB
Rust	small_00	AC	6 ms	2 MB
Rust	small_01	AC	6 ms	2 MB
Rust	small_02	AC	6 ms	2 MB
Rust	small_03	AC	6 ms	2 MB
Rust	small_04	AC	5 ms	2 MB
Rust	small_05	AC	6 ms	2 MB
Rust	small_06	AC	6 ms	2 MB
Rust	small_07	AC	5 ms	2 MB
Rust	small_08	AC	6 ms	2 MB
Rust	small_09	AC	6 ms	2 MB

Back to top page