examples/aizu_online_judge_range_minimum_query.rs

• View this file on GitHub
• Last update: 2024-04-26 00:50:11+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

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://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

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

const INF: usize = (1 << 31) - 1;

fn main() {
    input! {
        n: usize,
        q: usize,
    }

    let mut seg = SegmentTree::new(n, INF, |x, y| x.min(y));
    seg.construct(&vec![INF; n]);

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

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

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

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

Test cases

Env	Name	Status	Elapsed	Memory
Rust	00_small_00.in	AC	5 ms	2 MB
Rust	00_small_01.in	AC	5 ms	2 MB
Rust	00_small_02.in	AC	5 ms	2 MB
Rust	00_small_03.in	AC	5 ms	2 MB
Rust	01_rand_00.in	AC	5 ms	2 MB
Rust	01_rand_01.in	AC	5 ms	2 MB
Rust	01_rand_02.in	AC	5 ms	2 MB
Rust	01_rand_03.in	AC	5 ms	2 MB
Rust	02_biased_00.in	AC	5 ms	2 MB
Rust	02_biased_01.in	AC	5 ms	2 MB
Rust	02_biased_02.in	AC	5 ms	2 MB
Rust	02_biased_03.in	AC	53 ms	4 MB
Rust	03_rand_00.in	AC	6 ms	2 MB
Rust	03_rand_01.in	AC	11 ms	2 MB
Rust	03_rand_02.in	AC	14 ms	2 MB
Rust	03_rand_03.in	AC	12 ms	2 MB
Rust	03_rand_04.in	AC	101 ms	6 MB
Rust	03_rand_05.in	AC	73 ms	6 MB
Rust	04_maximum_00.in	AC	99 ms	6 MB
Rust	04_maximum_01.in	AC	101 ms	6 MB

Back to top page