test/smawk.test.cpp

test/smawk.test.cpp · GitHub で見る

依存ライブラリ

SMAWK

コード

#define PROBLEM "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"
#include "../components/smawk.hpp"
#include <cstdint>
#include <iostream>
#include <vector>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	std::cin >> n >> m;
	std::vector<std::int64_t> a(n), b(m);
	for (auto &x : a) std::cin >> x;
	for (auto &x : b) std::cin >> x;
	auto best = smawk(n + m - 1, m, [&](int row, int x, int y) {
		if (row < y) return false;
		if (row - x >= n) return true;
		return a[row - y] + b[y] < a[row - x] + b[x];
	});
	for (int i = 0; i < n + m - 1; ++i) std::cout << a[i - best[i]] + b[best[i]] << ' ';
	std::cout << '\n';
}

#line 1 "test/smawk.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary"
#line 1 "components/smawk.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <vector>

template <class Better>
std::vector<int> smawk(int length, const std::vector<int> &columns, Better better) {
	assert(length >= 0 && (!length || !columns.empty()));
	if (!length) return {};
	std::vector<int> best(length);
	auto solve = [&](auto &&self, std::size_t first, std::size_t stride, const std::vector<int> &cols) -> void {
		int rows = (length - 1 - first) / stride + 1;
		std::vector<int> reduced;
		reduced.reserve(std::min<std::size_t>(rows, cols.size()));
		for (int col : cols) {
			while (!reduced.empty() && better(first + (int(reduced.size()) - 1) * stride, reduced.back(), col)) reduced.pop_back();
			if (int(reduced.size()) < rows) reduced.push_back(col);
		}
		if (rows > 1) self(self, first + stride, stride * 2, reduced);
		std::size_t left = 0;
		for (std::size_t row = first; row < std::size_t(length); row += 2 * stride) {
			std::size_t right = left;
			if (row + stride < std::size_t(length))
				while (reduced[right] != best[row + stride]) ++right;
			else right = reduced.size() - 1;
			best[row] = reduced[left];
			for (std::size_t i = left + 1; i <= right; ++i)
				if (better(row, best[row], reduced[i])) best[row] = reduced[i];
			left = right;
		}
	};
	solve(solve, 0, 1, columns);
	return best;
}

template <class Better>
std::vector<int> smawk(int rows, int columns, Better better) {
	assert(columns >= 0);
	std::vector<int> cols(columns);
	std::iota(cols.begin(), cols.end(), 0);
	return smawk(rows, cols, better);
}


#line 3 "test/smawk.test.cpp"
#include <cstdint>
#include <iostream>
#line 6 "test/smawk.test.cpp"

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	std::cin >> n >> m;
	std::vector<std::int64_t> a(n), b(m);
	for (auto &x : a) std::cin >> x;
	for (auto &x : b) std::cin >> x;
	auto best = smawk(n + m - 1, m, [&](int row, int x, int y) {
		if (row < y) return false;
		if (row - x >= n) return true;
		return a[row - y] + b[y] < a[row - x] + b[x];
	});
	for (int i = 0; i < n + m - 1; ++i) std::cout << a[i - best[i]] + b[best[i]] << ' ';
	std::cout << '\n';
}