verify/library_checker/convolution/min_plus_convolution(convex_and_arbitrary).test.cpp

View this file on GitHub
Last update: 2025-07-24 17:37:03+09:00
Problem: https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"
#include "../../../src/template/template.hpp"
#include "../../../src/convolution/min_plus_convolution.hpp"
int main(void) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, m) cin >> b[i];
    vector<int> c = min_plus_convolution(a, b);
    rep(i, 0, n + m - 1) {
        cout << c[i] << " \n"[i + 1 == n + m - 1];
    }
}

#line 1 "verify/library_checker/convolution/min_plus_convolution(convex_and_arbitrary).test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/dp/monotone_minima.hpp"
template <class F>
vector<int> monotone_minima(const int n, const int m, const F& f) {
    vector<int> res(n);
    auto dfs = [&](const auto& dfs, const int is, const int ie, const int l, const int r) -> void {
        if(is == ie) return;
        const int i = (is + ie) / 2;
        int m = l;
        for(int k = l + 1; k < r; ++k) {
            if(!f(i, m, k)) m = k;
        }
        res[i] = m;
        dfs(dfs, is, i, l, m + 1);
        dfs(dfs, i + 1, ie, m, r);
    };
    dfs(dfs, 0, n, 0, m);
    return res;
}
#line 4 "src/convolution/min_plus_convolution.hpp"
template <typename T>
vector<T> min_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] < a[i - k] + b[k];
    };
    const auto argmin = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmin[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}
template <typename T>
vector<T> max_plus_convolution(const vector<T>& a, const vector<T>& b) {
    if(a.empty() or b.empty()) return {};
    const int n = a.size(), m = b.size();
    auto f = [&](const int i, const int j, const int k) -> bool {
        if(i < k) return true;
        if(i - j >= n) return false;
        return a[i - j] + b[j] > a[i - k] + b[k];
    };
    const auto argmax = monotone_minima(n + m - 1, m, f);
    vector<T> res(n + m - 1);
    for(int i = 0; i < n + m - 1; ++i) {
        const int j = argmax[i];
        res[i] = a[i - j] + b[j];
    }
    return res;
}
#line 4 "verify/library_checker/convolution/min_plus_convolution(convex_and_arbitrary).test.cpp"
int main(void) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, m) cin >> b[i];
    vector<int> c = min_plus_convolution(a, b);
    rep(i, 0, n + m - 1) {
        cout << c[i] << " \n"[i + 1 == n + m - 1];
    }
}