Function output_len 

pub(super) fn output_len(a_len: usize, b_len: usize) -> usize

Examples found in repository

crates/competitive/src/math/min_plus_convolution/convex.rs (line 40)

pub fn min_plus_convolution_convex_merge<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    assert_finite(a);
    assert_finite(b);
    assert!(is_convex(a) && is_convex(b), "both inputs must be convex");
    convex_merge(a, b)
}

pub(super) fn convex_merge<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    let mut a_slopes = a.windows(2).map(|window| window[1] - window[0]);
    let mut b_slopes = b.windows(2).map(|window| window[1] - window[0]);
    let mut next_a = a_slopes.next();
    let mut next_b = b_slopes.next();
    let mut current = a[0] + b[0];
    let mut result = Vec::with_capacity(len);
    result.push(current);
    while next_a.is_some() || next_b.is_some() {
        let slope = match (next_a, next_b) {
            (Some(left), Some(right)) if left <= right => {
                next_a = a_slopes.next();
                left
            }
            (Some(_), Some(right)) => {
                next_b = b_slopes.next();
                right
            }
            (Some(left), None) => {
                next_a = a_slopes.next();
                left
            }
            (None, Some(right)) => {
                next_b = b_slopes.next();
                right
            }
            (None, None) => break,
        };
        current += slope;
        result.push(current);
    }
    result
}

/// Computes convolution when one input is convex using monotone divide and conquer.
///
/// # Panics
///
/// Panics unless both inputs are finite and at least one is convex.
pub fn min_plus_convolution_convex_divide_and_conquer<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    assert_finite(a);
    assert_finite(b);
    let (arbitrary, convex) = orient_one_convex(a, b);
    convex_divide_and_conquer(arbitrary, convex)
}

pub(super) fn convex_divide_and_conquer<T>(arbitrary: &[T], convex: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(arbitrary.len(), convex.len());
    let mut result = vec![T::zero(); len];

    fn solve<T>(
        arbitrary: &[T],
        convex: &[T],
        result: &mut [T],
        rows: Range<usize>,
        options: RangeInclusive<usize>,
    ) where
        T: Signed,
    {
        if rows.is_empty() {
            return;
        }
        let row = (rows.start + rows.end) / 2;
        let first = (*options.start()).max(row.saturating_sub(convex.len() - 1));
        let last = (*options.end()).min(row).min(arbitrary.len() - 1);
        let mut best_col = first;
        let mut best_value = arbitrary[first] + convex[row - first];
        for col in first + 1..=last {
            let value = arbitrary[col] + convex[row - col];
            if value < best_value {
                best_value = value;
                best_col = col;
            }
        }
        result[row] = best_value;
        solve(
            arbitrary,
            convex,
            result,
            rows.start..row,
            *options.start()..=best_col,
        );
        solve(
            arbitrary,
            convex,
            result,
            row + 1..rows.end,
            best_col..=*options.end(),
        );
    }

    solve(
        arbitrary,
        convex,
        &mut result,
        0..len,
        0..=arbitrary.len() - 1,
    );
    result
}

#[derive(Clone, Copy, Eq, PartialEq)]
enum MatrixValue<T> {
    Finite(T),
    Infinite,
}

impl<T> Ord for MatrixValue<T>
where
    T: Ord,
{
    fn cmp(&self, other: &Self) -> Ordering {
        match (self, other) {
            (Self::Finite(left), Self::Finite(right)) => left.cmp(right),
            (Self::Finite(_), Self::Infinite) => Ordering::Less,
            (Self::Infinite, Self::Finite(_)) => Ordering::Greater,
            (Self::Infinite, Self::Infinite) => Ordering::Equal,
        }
    }
}

impl<T> PartialOrd for MatrixValue<T>
where
    T: Ord,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn smawk<T, F>(rows: usize, cols: usize, cost: &F) -> Vec<usize>
where
    T: Ord,
    F: Fn(usize, usize) -> T,
{
    fn solve<T, F>(rows: &[usize], cols: &[usize], cost: &F, argmins: &mut [usize])
    where
        T: Ord,
        F: Fn(usize, usize) -> T,
    {
        if rows.is_empty() {
            return;
        }
        let mut reduced = Vec::with_capacity(rows.len().min(cols.len()));
        for &col in cols {
            while let Some(&previous) = reduced.last() {
                let row = rows[reduced.len() - 1];
                if cost(row, col) <= cost(row, previous) {
                    reduced.pop();
                } else {
                    break;
                }
            }
            if reduced.len() < rows.len() {
                reduced.push(col);
            }
        }
        let odd_rows: Vec<_> = rows.iter().copied().skip(1).step_by(2).collect();
        solve(&odd_rows, &reduced, cost, argmins);
        let mut lower = 0;
        for row_position in (0..rows.len()).step_by(2) {
            let upper = if row_position + 1 < rows.len() {
                let target = argmins[rows[row_position + 1]];
                lower
                    + reduced[lower..]
                        .iter()
                        .position(|&col| col == target)
                        .expect("SMAWK odd-row minimum must remain in the reduced columns")
            } else {
                reduced.len() - 1
            };
            let row = rows[row_position];
            let mut best = lower;
            for position in lower + 1..=upper {
                if cost(row, reduced[position]) <= cost(row, reduced[best]) {
                    best = position;
                }
            }
            argmins[row] = reduced[best];
            lower = upper;
        }
    }

    let row_indices: Vec<_> = (0..rows).collect();
    let col_indices: Vec<_> = (0..cols).collect();
    let mut argmins = vec![0; rows];
    solve(&row_indices, &col_indices, cost, &mut argmins);
    argmins
}

/// Computes convolution when one input is convex using SMAWK in `O(n + m)`.
///
/// # Panics
///
/// Panics unless both inputs are finite and at least one is convex.
pub fn min_plus_convolution_convex_smawk<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    assert_finite(a);
    assert_finite(b);
    let (arbitrary, convex) = orient_one_convex(a, b);
    convex_smawk(arbitrary, convex)
}

pub(super) fn convex_smawk<T>(arbitrary: &[T], convex: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(arbitrary.len(), convex.len());
    let cost = |row: usize, col: usize| {
        row.checked_sub(col)
            .filter(|&index| index < convex.len())
            .map_or(MatrixValue::Infinite, |index| {
                MatrixValue::Finite(arbitrary[col] + convex[index])
            })
    };
    let argmins = smawk(len, arbitrary.len(), &cost);
    argmins
        .into_iter()
        .enumerate()
        .map(|(row, col)| {
            row.checked_sub(col)
                .filter(|&index| index < convex.len())
                .map(|index| arbitrary[col] + convex[index])
                .expect("SMAWK minimum must be a valid convolution entry")
        })
        .collect()
}

crates/competitive/src/math/min_plus_convolution/concave.rs (line 30)

    fn new(arbitrary: &'a [T], concave: &'a [T]) -> Self {
        let output_len = output_len(arbitrary.len(), concave.len());
        let leaf_count = 1_usize
            .checked_shl(bit_width(output_len))
            .expect("min-plus convolution envelope size must fit usize");
        ConcaveEnvelope {
            arbitrary,
            concave,
            leaf_count,
            query_root: leaf_count >> bit_width(concave.len() - 1),
            node_curves: vec![None; leaf_count],
            result: vec![T::maximum(); output_len],
        }
    }

    #[inline]
    fn value(&self, curve: usize, output: usize) -> T {
        self.arbitrary[curve] + self.concave[output - curve]
    }

    #[inline]
    fn query(&mut self, output: usize) {
        let mut best = self.result[output];
        let mut node = (output + self.leaf_count) >> 1;
        while node >= self.query_root {
            if let Some(curve) = self.node_curves[node] {
                best = best.min(self.value(curve, output));
            }
            node >>= 1;
        }
        self.result[output] = best;
    }

    #[inline]
    fn insert_from_left(&mut self, left: usize) {
        let mut right = left + self.concave.len();
        let block = 1_usize << (left ^ right).ilog2();
        right &= !(block - 1);
        let mut depth = bit_width(right - left - 1);
        let mut node = (self.leaf_count + left) >> depth;
        let mut pending = (!self.arbitrary[left].is_maximum()).then_some(left);
        while depth != 0 {
            let Some(curve) = pending else {
                break;
            };
            depth -= 1;
            let middle = ((node << 1 | 1) << depth) - self.leaf_count - 1;
            if middle < left {
                node = node << 1 | 1;
            } else if self.node_curves[node]
                .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
            {
                node <<= 1;
            } else {
                std::mem::swap(&mut self.node_curves[node], &mut pending);
                node = node << 1 | 1;
            }
        }
        if let Some(curve) = pending {
            let output = node - self.leaf_count;
            self.result[output] = self.result[output].min(self.value(curve, output));
        }
    }

    #[inline]
    fn insert_from_right(&mut self, right: usize) {
        let curve = right - self.concave.len();
        let block = 1_usize << (curve ^ right).ilog2();
        let left = right & !(block - 1);
        if left == right {
            return;
        }
        let mut depth = bit_width(right - left - 1);
        let mut node = (self.leaf_count + left) >> depth;
        let mut pending = (!self.arbitrary[curve].is_maximum()).then_some(curve);
        while depth != 0 {
            let Some(curve) = pending else {
                break;
            };
            depth -= 1;
            let middle = ((node << 1 | 1) << depth) - self.leaf_count;
            if middle >= right {
                node <<= 1;
            } else if self.node_curves[node]
                .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
            {
                node = node << 1 | 1;
            } else {
                std::mem::swap(&mut self.node_curves[node], &mut pending);
                node <<= 1;
            }
        }
        if let Some(curve) = pending {
            let output = node - self.leaf_count;
            self.result[output] = self.result[output].min(self.value(curve, output));
        }
    }

    fn convolve(mut self) -> Vec<T> {
        // Curve i is valid on [i, i + concave.len()). The two passes insert
        // opposite sides of each validity interval into the segment envelope.
        for left in 0..self.arbitrary.len() {
            self.insert_from_left(left);
            self.query(left);
        }
        for output in self.arbitrary.len()..self.result.len() {
            self.query(output);
        }

        self.node_curves.fill(None);
        let mut right = self.result.len();
        while right >= self.concave.len() {
            self.insert_from_right(right);
            right -= 1;
            self.query(right);
        }
        for output in 0..self.concave.len() {
            self.query(output);
        }
        self.result
    }
}

/// Computes convolution when one finite input is concave using offline envelopes.
///
/// The running time is `O((n + m) log(n + m))`. The arbitrary input may
/// contain `T::maximum()`.
///
/// # Panics
///
/// Panics unless at least one input is finite and concave, or if the
/// interval-tree size cannot be represented.
pub fn min_plus_convolution_concave_envelope<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    let a_is_concave = !a.iter().any(T::is_maximum) && is_concave(a);
    let b_is_concave = !b.iter().any(T::is_maximum) && is_concave(b);
    let (arbitrary, concave) = if b_is_concave {
        (a, b)
    } else if a_is_concave {
        (b, a)
    } else {
        panic!("at least one min-plus convolution input must be finite and concave")
    };
    concave_envelope(arbitrary, concave)
}

pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>
where
    T: Signed,
{
    if concave.len() == 1 {
        return arbitrary
            .iter()
            .map(|&value| {
                if value.is_maximum() {
                    T::maximum()
                } else {
                    value + concave[0]
                }
            })
            .collect();
    }
    if arbitrary.len() == 1 {
        return if arbitrary[0].is_maximum() {
            vec![T::maximum(); concave.len()]
        } else {
            concave.iter().map(|&value| arbitrary[0] + value).collect()
        };
    }

    ConcaveEnvelope::new(arbitrary, concave).convolve()
}

/// Computes convolution of two concave inputs from antidiagonal endpoints.
///
/// The running time is `O(n + m)`.
///
/// # Panics
///
/// Panics unless both inputs are finite and concave.
pub fn min_plus_convolution_concave_both<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    assert_finite(a);
    assert_finite(b);
    assert!(
        is_concave(a) && is_concave(b),
        "both inputs must be concave"
    );
    concave_both(a, b)
}

pub(super) fn concave_both<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    let mut result = Vec::with_capacity(len);
    for output in 0..len {
        let first = output.saturating_sub(b.len() - 1);
        let last = output.min(a.len() - 1);
        result.push((a[first] + b[output - first]).min(a[last] + b[output - last]));
    }
    result
}

crates/competitive/src/math/min_plus_convolution/piecewise_linear.rs (line 131)

pub fn min_plus_convolution_linear<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    let a_piece = finite_pieces(a).filter(|pieces| pieces.len() == 1);
    let b_piece = finite_pieces(b).filter(|pieces| pieces.len() == 1);
    let (arbitrary, piece) = if let Some(pieces) = b_piece {
        (a, pieces[0])
    } else if let Some(pieces) = a_piece {
        (b, pieces[0])
    } else {
        panic!("at least one min-plus convolution input must be finite and linear")
    };
    convolve_pieces(arbitrary, std::iter::once(piece), len)
}

pub(super) fn linear<T>(arbitrary: &[T], structured: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
{
    let len = output_len(arbitrary.len(), structured.len());
    convolve_pieces(arbitrary, pieces(structured), len)
}

/// Computes convolution using the input with fewer maximal linear pieces.
///
/// If that input has `p` pieces, the running time is `O(p * (n + m))`.
///
/// # Panics
///
/// Panics unless at least one input is finite, or an index cannot be
/// represented by `T`.
pub fn min_plus_convolution_piecewise_linear<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    let a_pieces = finite_pieces(a);
    let b_pieces = finite_pieces(b);
    let (arbitrary, structured) = match (a_pieces, b_pieces) {
        (Some(a_pieces), Some(b_pieces)) if a_pieces.len() < b_pieces.len() => (b, a_pieces),
        (Some(_), Some(b_pieces)) => (a, b_pieces),
        (Some(a_pieces), None) => (b, a_pieces),
        (None, Some(b_pieces)) => (a, b_pieces),
        (None, None) => {
            panic!("at least one min-plus convolution input must be finite")
        }
    };
    convolve_pieces(arbitrary, structured, len)
}

pub(super) fn piecewise_linear<T>(arbitrary: &[T], structured: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
{
    let len = output_len(arbitrary.len(), structured.len());
    convolve_pieces(arbitrary, pieces(structured), len)
}

crates/competitive/src/math/min_plus_convolution/monotone.rs (line 28)

pub fn min_plus_convolution_monotone_runs<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    assert_finite(a);
    assert_finite(b);
    let increasing = if a.windows(2).all(|window| window[0] >= window[1])
        && b.windows(2).all(|window| window[0] >= window[1])
    {
        false
    } else if a.windows(2).all(|window| window[0] <= window[1])
        && b.windows(2).all(|window| window[0] <= window[1])
    {
        true
    } else {
        panic!("both inputs must be monotone in the same direction")
    };
    monotone_runs(a, b, increasing)
}

pub(super) fn monotone_runs<T>(a: &[T], b: &[T], increasing: bool) -> Vec<T>
where
    T: Signed,
{
    monotone_runs_from_entries(
        &run_entries(a),
        &run_entries(b),
        a.len(),
        b.len(),
        increasing,
    )
}

pub(super) fn monotone_runs_from_entries<T>(
    a_runs: &[(usize, T)],
    b_runs: &[(usize, T)],
    a_len: usize,
    b_len: usize,
    increasing: bool,
) -> Vec<T>
where
    T: Signed,
{
    let normalize = |runs: &[(usize, T)], len: usize| {
        if increasing {
            runs.iter()
                .enumerate()
                .rev()
                .map(|(index, &(_, value))| {
                    (
                        len - runs.get(index + 1).map_or(len, |&(start, _)| start),
                        value,
                    )
                })
                .collect()
        } else {
            runs.to_vec()
        }
    };
    let a_runs = normalize(a_runs, a_len);
    let b_runs = normalize(b_runs, b_len);
    let len = output_len(a_len, b_len);
    let mut result = vec![T::maximum(); len];
    for &(left_start, left_value) in &a_runs {
        for &(right_start, right_value) in &b_runs {
            let output = left_start + right_start;
            result[output] = result[output].min(left_value + right_value);
        }
    }
    for output in 1..len {
        result[output] = result[output].min(result[output - 1]);
    }
    if increasing {
        result.reverse();
    }
    result
}

crates/competitive/src/math/min_plus_convolution/mod.rs (line 60)

pub fn min_plus_convolution_naive<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    let (outer, inner) = if a.len() <= b.len() { (a, b) } else { (b, a) };
    let inner_is_finite = !inner.iter().any(T::is_maximum);
    let mut result = vec![T::maximum(); len];
    for (index, &left) in outer.iter().enumerate() {
        if left.is_maximum() {
            continue;
        }
        let output = &mut result[index..index + inner.len()];
        if inner_is_finite {
            for (slot, &right) in output.iter_mut().zip(inner) {
                *slot = (*slot).min(left + right);
            }
        } else {
            for (slot, &right) in output.iter_mut().zip(inner) {
                if !right.is_maximum() {
                    *slot = (*slot).min(left + right);
                }
            }
        }
    }
    result
}

/// Computes min-plus convolution by enumerating finite input pairs only.
///
/// If the inputs have `s_a` and `s_b` finite values, the running time is
/// `O(s_a * s_b + n + m)`.
///
/// # Panics
///
/// Panics if the output length does not fit [`usize`]. Arithmetic overflow is
/// the caller's responsibility.
pub fn min_plus_convolution_sparse<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    let a: Vec<_> = a
        .iter()
        .copied()
        .enumerate()
        .filter(|(_, value)| !value.is_maximum())
        .collect();
    let b: Vec<_> = b
        .iter()
        .copied()
        .enumerate()
        .filter(|(_, value)| !value.is_maximum())
        .collect();
    sparse(a.iter().copied(), b.iter().copied(), len)
}

fn sparse<T>(
    a: impl IntoIterator<Item = (usize, T)>,
    b: impl IntoIterator<Item = (usize, T)> + Clone,
    len: usize,
) -> Vec<T>
where
    T: Signed,
{
    let mut result = vec![T::maximum(); len];
    for (i, left) in a {
        for (j, right) in b.clone() {
            result[i + j] = result[i + j].min(left + right);
        }
    }
    result
}

const MAX_NTT_SIZE: usize = 1 << 23;

#[derive(Clone, Copy, Debug)]
struct BoundedRequirements<T> {
    a_min: T,
    b_min: T,
    base: usize,
    transform_len: usize,
}

fn finite_extrema<T>(values: &[T]) -> Option<(T, T)>
where
    T: Signed,
{
    let mut finite = values.iter().copied().filter(|value| !value.is_maximum());
    let first = finite.next()?;
    Some(finite.fold((first, first), |(minimum, maximum), value| {
        (minimum.min(value), maximum.max(value))
    }))
}

fn bounded_transform_len(a_len: usize, b_len: usize, base: usize) -> Option<usize> {
    let left_len = a_len.checked_mul(base)?;
    let right_len = b_len.checked_mul(base)?;
    let coefficient_len = left_len
        .checked_add(right_len)
        .and_then(|len| len.checked_sub(1))?;
    let transform_len = coefficient_len.checked_next_power_of_two()?;
    (transform_len <= MAX_NTT_SIZE).then_some(transform_len)
}

fn bounded_requirements_from_extrema<T>(
    a_len: usize,
    b_len: usize,
    (a_min, a_max): (T, T),
    (b_min, b_max): (T, T),
) -> Option<BoundedRequirements<T>>
where
    T: Signed,
    T::Unsigned: TryInto<usize>,
{
    let a_span = a_max.abs_diff(a_min).try_into().ok()?;
    let b_span = b_max.abs_diff(b_min).try_into().ok()?;
    let base = a_span
        .checked_add(b_span)
        .and_then(|span| span.checked_add(1))?;
    let transform_len = bounded_transform_len(a_len, b_len, base)?;
    Some(BoundedRequirements {
        a_min,
        b_min,
        base,
        transform_len,
    })
}

/// Computes exact min-plus convolution for small integer value spans using NTT.
///
/// # Panics
///
/// Panics if the encoded range cannot be represented or requires a transform
/// longer than `2^23`. Arithmetic overflow is the caller's responsibility.
pub fn min_plus_convolution_bounded_ntt<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed + TryFrom<usize>,
    T::Unsigned: TryInto<usize>,
{
    let output_len = output_len(a.len(), b.len());
    if output_len == 0 {
        return Vec::new();
    }
    let (Some(a_extrema), Some(b_extrema)) = (finite_extrema(a), finite_extrema(b)) else {
        return vec![T::maximum(); output_len];
    };
    let requirements = bounded_requirements_from_extrema(a.len(), b.len(), a_extrema, b_extrema)
        .expect("bounded min-plus convolution encoding must fit the 2^23 NTT limit");
    let mut left = vec![MInt998244353::from(0_u32); a.len() * requirements.base];
    let mut right = vec![MInt998244353::from(0_u32); b.len() * requirements.base];
    for (index, &value) in a.iter().enumerate() {
        if !value.is_maximum() {
            let normalized: usize = value
                .abs_diff(requirements.a_min)
                .try_into()
                .ok()
                .expect("bounded min-plus convolution value span must fit usize");
            left[index * requirements.base + normalized] = MInt998244353::from(1_u32);
        }
    }
    for (index, &value) in b.iter().enumerate() {
        if !value.is_maximum() {
            let normalized: usize = value
                .abs_diff(requirements.b_min)
                .try_into()
                .ok()
                .expect("bounded min-plus convolution value span must fit usize");
            right[index * requirements.base + normalized] = MInt998244353::from(1_u32);
        }
    }
    let coefficients = Convolve998244353::convolve(left, right);
    let encoded_len = output_len
        .checked_mul(requirements.base)
        .expect("bounded min-plus convolution encoded length must fit usize");
    let mut result = Vec::with_capacity(output_len);
    for chunk in coefficients[..encoded_len].chunks_exact(requirements.base) {
        let value = if let Some(normalized) = chunk.iter().position(|&value| u32::from(value) != 0)
        {
            requirements.a_min
                + requirements.b_min
                + T::try_from(normalized)
                    .ok()
                    .expect("bounded min-plus convolution value must fit the output type")
        } else {
            T::maximum()
        };
        result.push(value);
    }
    result
}

crates/competitive/src/math/min_plus_convolution/near_convex.rs (line 75)

pub fn min_plus_convolution_near_convex_scan<T>(
    a: &[T],
    b: &[T],
    convex_a: &[T],
    convex_b: &[T],
    delta: T,
) -> Vec<T>
where
    T: Signed,
{
    let len = output_len(a.len(), b.len());
    if len == 0 {
        return Vec::new();
    }
    validate_witness(a, convex_a, delta);
    validate_witness(b, convex_b, delta);
    let (convex_output, witnesses) = convex_convolution_witnesses(convex_a, convex_b);
    let tolerance = delta + delta;
    let relevant = |output: usize, i: usize| {
        convex_a[i] + convex_b[output - i] <= convex_output[output] + tolerance
    };
    let mut result = Vec::with_capacity(len);
    for output in 0..len {
        let first = output.saturating_sub(b.len() - 1);
        let last = output.min(a.len() - 1);
        let witness = witnesses[output];
        let mut low = first;
        let mut high = witness;
        while low < high {
            let middle = low + (high - low) / 2;
            if relevant(output, middle) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        let first_relevant = low;
        low = witness;
        high = last;
        while low < high {
            let middle = low + (high - low).div_ceil(2);
            if relevant(output, middle) {
                low = middle;
            } else {
                high = middle - 1;
            }
        }
        let mut best = T::maximum();
        for i in first_relevant..=low {
            best = best.min(a[i] + b[output - i]);
        }
        result.push(best);
    }
    result
}

Additional examples can be found in:

• crates/competitive/src/math/min_plus_convolution/selector.rs