library_checker/data_structure/line_add_get_min.rs
1use competitive::data_structure::OfflineLiChaoTree;
2use competitive::prelude::*;
3
4competitive::define_enum_scan! {
5 enum Query: usize {
6 0 => Add { a: i32, b: i64 }
7 1 => Get { x: i32 }
8 }
9}
10
11#[verify::library_checker("line_add_get_min")]
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}