competitive::data_structure::li_chao_tree

Struct OfflineLiChaoTree

pub struct OfflineLiChaoTree<X, L> {
    events: Vec<LiChaoEvent<X, L>>,
    queries: usize,
}

Fields§

§events: Vec<LiChaoEvent<X, L>>§queries: usize

Implementations§

Source §

impl<X, L> OfflineLiChaoTree<X, L>
where X: Copy + Ord + RadixSortKey, L: LiChaoLine<X>,

Source

pub fn new() -> Self

Examples found in repository ?

crates/library_checker/src/data_structure/line_add_get_min.rs (line 15)

12pub fn line_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 (a, b) in sv!([(i32, i64); iter n]) {
17        tree.add_line((a, b));
18    }
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Add { a, b } => {
23                tree.add_line((a, b));
24            }
25            Query::Get { x } => {
26                tree.query_min(x);
27            }
28        }
29    }
30    pp!(@lf @it tree.execute().into_iter().map(Option::unwrap));
31}

More examples

Hide additional examples

crates/library_checker/src/data_structure/segment_add_get_min.rs (line 15)

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}

Source

pub fn add_line(&mut self, line: L)

Examples found in repository ?

crates/library_checker/src/data_structure/line_add_get_min.rs (line 17)

12pub fn line_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 (a, b) in sv!([(i32, i64); iter n]) {
17        tree.add_line((a, b));
18    }
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Add { a, b } => {
23                tree.add_line((a, b));
24            }
25            Query::Get { x } => {
26                tree.query_min(x);
27            }
28        }
29    }
30    pp!(@lf @it tree.execute().into_iter().map(Option::unwrap));
31}

Source

pub fn add_segment(&mut self, range: Range<X>, line: L)

Examples found in repository ?

crates/library_checker/src/data_structure/segment_add_get_min.rs (line 17)

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}

Source

pub fn query_min(&mut self, x: X) -> usize

Examples found in repository ?

crates/library_checker/src/data_structure/line_add_get_min.rs (line 26)

12pub fn line_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 (a, b) in sv!([(i32, i64); iter n]) {
17        tree.add_line((a, b));
18    }
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Add { a, b } => {
23                tree.add_line((a, b));
24            }
25            Query::Get { x } => {
26                tree.query_min(x);
27            }
28        }
29    }
30    pp!(@lf @it tree.execute().into_iter().map(Option::unwrap));
31}

More examples

Hide additional examples

crates/library_checker/src/data_structure/segment_add_get_min.rs (line 26)

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}

Source

pub fn execute(self) -> Vec<Option<L::Output>>

Examples found in repository ?

crates/library_checker/src/data_structure/line_add_get_min.rs (line 30)

12pub fn line_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 (a, b) in sv!([(i32, i64); iter n]) {
17        tree.add_line((a, b));
18    }
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Add { a, b } => {
23                tree.add_line((a, b));
24            }
25            Query::Get { x } => {
26                tree.query_min(x);
27            }
28        }
29    }
30    pp!(@lf @it tree.execute().into_iter().map(Option::unwrap));
31}

More examples

Hide additional examples

crates/library_checker/src/data_structure/segment_add_get_min.rs (line 30)

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}