Skip to main content

min_plus_convolution_concave_envelope

competitive::math::min_plus_convolution::concave

Function min_plus_convolution_concave_envelope 

Source 
pub fn min_plus_convolution_concave_envelope<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
Expand description

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.

Examples found in repository?
crates/library_checker/src/convolution/min_plus_convolution_concave_arbitrary.rs (line 8)
5pub fn min_plus_convolution_concave_arbitrary(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, a: [i64; n], b: [i64; m]);
8    pp!(@it min_plus_convolution_concave_envelope(&a, &b));
9}