sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary" #include <bits/stdc++.h> #include "../../convolution/convex_min_plus_convolution.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<long long> a(N), b(M); for (auto& x : a) cin >> x; for (auto& x : b) cin >> x; auto c = convex_min_plus_convolution(b, a); for (int i = 0; i < N + M - 1; ++i) cout << c[i] << (i < N + M - 2 ? " " : "\n"); }
#line 1 "test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary" #include <bits/stdc++.h> #line 3 "dp/monotone_minima.hpp" template <typename F> std::vector<int> monotone_minima(int n, int m, const F& f) { std::vector<int> idx(n, -1); auto calc = [&](const auto& calc, int l, int r, int optl, int optr) -> void { if (l > r) return; int m = std::midpoint(l, r); auto mi = f(m, optl); idx[m] = optl; for (int i = optl + 1; i <= optr; ++i) { auto v = f(m, i); if (mi > v) { mi = v; idx[m] = i; } } calc(calc, l, m - 1, optl, idx[m]); calc(calc, m + 1, r, idx[m], optr); }; calc(calc, 0, n - 1, 0, m - 1); return idx; } #line 5 "convolution/convex_min_plus_convolution.hpp" // b is convex template <typename T> std::vector<T> convex_min_plus_convolution(const std::vector<T>& a, const std::vector<T>& b) { int len = a.size() + b.size() - 1; auto f = [&](int i, int j) { if (i - j < 0 || (int)b.size() <= i - j) return std::numeric_limits<T>::max(); return a[j] + b[i - j]; }; auto idx = monotone_minima(len, a.size(), f); std::vector<T> res(len); for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]); return res; } // b is concave template <typename T> std::vector<T> concave_max_plus_convolution(std::vector<T> a, std::vector<T> b) { for (auto& x : a) x = -x; for (auto& x : b) x = -x; auto c = convex_min_plus_convolution(a, b); for (auto& x : c) x = -x; return c; } #line 7 "test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<long long> a(N), b(M); for (auto& x : a) cin >> x; for (auto& x : b) cin >> x; auto c = convex_min_plus_convolution(b, a); for (int i = 0; i < N + M - 1; ++i) cout << c[i] << (i < N + M - 2 ? " " : "\n"); }