library_checker/data_structure/
segment_add_get_min.rs

1use competitive::data_structure::OfflineLiChaoTree;
2use competitive::prelude::*;
3
4competitive::define_enum_scan! {
5    enum Query: usize {
6        0 => Add { l: i32, r: i32, a: i32, b: i64 }
7        1 => Get { x: i32 }
8    }
9}
10
11#[verify::library_checker("segment_add_get_min")]
12pub fn segment_add_get_min(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut tree = OfflineLiChaoTree::new();
16    for (l, r, a, b) in sv!([(i32, i32, i32, i64); iter n]) {
17        tree.add_segment(l..r, (a, b));
18    }
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Add { l, r, a, b } => {
23                tree.add_segment(l..r, (a, b));
24            }
25            Query::Get { x } => {
26                tree.query_min(x);
27            }
28        }
29    }
30    for result in tree.execute() {
31        if let Some(value) = result {
32            pp!(value);
33        } else {
34            pp!("INFINITY");
35        }
36    }
37}

library_checker/data_structure/segment_add_get_min.rs

library_checker/data_structure/
segment_add_get_min.rs