11288: [yosupo] Convolution - Min Plus Convolution (Convex and Convex)
[Creator : ]
Description
Given integer sequences $a_0, a_1, ..., a_{N - 1}$ and $b_0, b_1, ..., b_{M - 1}$. Here, $a$ and $b$ are convex. Calculate an integer sequence $c_0, c_1, ..., c_{(N - 1) + (M - 1)}$ defined as follows:
$c_k = \min_{i+j=k} (a_i+b_j)$
$c_k = \min_{i+j=k} (a_i+b_j)$
Input
$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
Output
$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$
Constraints
- $1 \leq N, M \leq 2^{19}$
- $0 \leq a_i, b_i \leq 10^9$
- $a$ is convex. i.e. $a_{i+1}-a_i\leq a_{i+2}-a_{i+1}$ holds for $0\leq i < N - 2$.
- $b$ is convex. i.e. $b_{i+1}-b_i\leq b_{i+2}-b_{i+1}$ holds for $0\leq i < M - 2$.
- $0 \leq a_i, b_i \leq 10^9$
- $a$ is convex. i.e. $a_{i+1}-a_i\leq a_{i+2}-a_{i+1}$ holds for $0\leq i < N - 2$.
- $b$ is convex. i.e. $b_{i+1}-b_i\leq b_{i+2}-b_{i+1}$ holds for $0\leq i < M - 2$.
Sample 1 Input
4 5
3 1 0 3
5 2 1 1 4
Sample 1 Output
8 5 3 2 1 1 4 7