library_checker/math/
min_of_mod_of_linear.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algorithm::binary_search, math::floor_sum_range_freq};
4
5#[verify::library_checker("min_of_mod_of_linear")]
6pub fn min_of_mod_of_linear(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, t, query: [(i64, u64, i64, i64)]);
10    for (n, m, a, b) in query.take(t) {
11        let x = binary_search(
12            |&x| floor_sum_range_freq(0, n, a, b, m, 0..x + 1) > 0,
13            m as i64 - 1,
14            -1,
15        );
16        writeln!(writer, "{}", x).ok();
17    }
18}