fn first_position_of_new_source<T>(
values: &[T],
previous_source: usize,
new_source: usize,
) -> TExamples found in repository?
crates/competitive/src/math/min_plus_convolution/squared_distance.rs (line 54)
39pub fn min_plus_convolution_with_squared_distance<T>(values: &[T]) -> Vec<T>
40where
41 T: Signed + TryFrom<usize>,
42{
43 if values.is_empty() {
44 return Vec::new();
45 }
46 let mut sources = Vec::with_capacity(values.len());
47 let mut first_positions = Vec::with_capacity(values.len());
48 for (new_source, &value) in values.iter().enumerate() {
49 if value.is_maximum() {
50 continue;
51 }
52 let mut first_position = T::zero();
53 while let Some(&previous_source) = sources.last() {
54 first_position = first_position_of_new_source(values, previous_source, new_source);
55 if first_position > first_positions[first_positions.len() - 1] {
56 break;
57 }
58 sources.pop();
59 first_positions.pop();
60 }
61 if sources.is_empty() {
62 first_position = T::zero();
63 }
64 if first_position < index_as_value(values.len()) {
65 sources.push(new_source);
66 first_positions.push(first_position.max(T::zero()));
67 }
68 }
69 if sources.is_empty() {
70 return vec![T::maximum(); values.len()];
71 }
72 let mut active_source_index = 0;
73 let mut result = Vec::with_capacity(values.len());
74 for position in 0..values.len() {
75 while active_source_index + 1 < sources.len()
76 && first_positions[active_source_index + 1] <= index_as_value(position)
77 {
78 active_source_index += 1;
79 }
80 let source = sources[active_source_index];
81 let distance: T = index_as_value(source.abs_diff(position));
82 result.push(values[source] + distance * distance);
83 }
84 result
85}