結果
| 問題 | No.2114 01 Matching |
| ユーザー |
 hitonanode
|
| 提出日時 | 2022-12-04 20:23:31 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 538 ms / 5,000 ms |
| コード長 | 6,520 bytes |
| コンパイル時間 | 1,370 ms |
| コンパイル使用メモリ | 130,752 KB |
| 実行使用メモリ | 47,232 KB |
| 最終ジャッジ日時 | 2024-11-24 12:28:37 |
| 合計ジャッジ時間 | 14,426 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 51 |
ソースコード
#line 1 "other_algorithms/test/dual_slope_trick.yuki2114.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/2114"#line 2 "other_algorithms/slope_trick.hpp"#include <algorithm>#include <cassert>#include <limits>#include <queue>#include <utility>// Slope trick: fast operations for convex piecewise-linear functions// Implementation idea:// - https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8// - https://ei1333.github.io/library/structure/others/slope-trick.cpptemplate <class T, T INF = std::numeric_limits<T>::max() / 2> class slope_trick {T min_f;T displacement_l, displacement_r;std::priority_queue<T, std::vector<T>, std::less<T>> L;std::priority_queue<T, std::vector<T>, std::greater<T>> R;void pushR(const T &a) { R.push(a - displacement_r); }T topR() const { return R.empty() ? INF : R.top() + displacement_r; }T popR() {auto ret = topR();if (R.size()) R.pop();return ret;}void pushL(const T &a) { L.push(a + displacement_l); }T topL() const { return L.empty() ? -INF : L.top() - displacement_l; }T popL() {auto ret = topL();if (L.size()) L.pop();return ret;}public:// Initialize, f(x) = 0 everywhere// Complexity: O(1)slope_trick() : min_f(0), displacement_l(0), displacement_r(0) {static_assert(INF > 0, "INF must be greater than 0");}inline int sizeL() const noexcept { return L.size(); }inline int sizeR() const noexcept { return R.size(); }// argmin f(x), min f(x)// Complexity: O(1)using Q = struct { T min, lo, hi; };Q get_min() const { return {min_f, topL(), topR()}; }// f(x) += b// Complexity: O(1)slope_trick &add_const(const T &b) { return min_f += b, *this; }// f(x) += max(x - a, 0) _/// Complexity: O(log n)slope_trick &add_relu(const T &a) {return min_f += std::max(T(0), topL() - a), pushL(a), pushR(popL()), *this;}// f(x) += max(a - x, 0) \_// Complexity: O(log n)slope_trick &add_irelu(const T &a) {return min_f += std::max(T(0), a - topR()), pushR(a), pushL(popR()), *this;}// f(x) += |x - a| \/// Complexity: O(log n)slope_trick &add_abs(const T &a) { return add_relu(a).add_irelu(a); }// f(x) <- min_{0 <= y <= w} f(x + y) .\ -> \_// Complexity: O(1)slope_trick &move_left_curve(const T &w) { return assert(w >= 0), displacement_l += w, *this; }// f(x) <- min_{0 <= y <= w} f(x - y) /. -> _/// Complexity: O(1)slope_trick &move_right_curve(const T &w) {return assert(w >= 0), displacement_r += w, *this;}// f(x) <- f(x - dx) \/. -> .\/// Complexity: O(1)slope_trick &translate(const T &dx) {return displacement_l -= dx, displacement_r += dx, *this;}// return f(x), f destructiveT get_destructive(const T &x) {T ret = get_min().min;while (L.size()) ret += std::max(T(0), popL() - x);while (R.size()) ret += std::max(T(0), x - popR());return ret;}// f(x) += g(x), g destructiveslope_trick &merge_destructive(slope_trick<T, INF> &g) {if (sizeL() + sizeR() > g.sizeL() + g.sizeR()) {std::swap(min_f, g.min_f);std::swap(displacement_l, g.displacement_l);std::swap(displacement_r, g.displacement_r);std::swap(L, g.L);std::swap(R, g.R);}min_f += g.get_min().min;while (g.L.size()) add_irelu(g.popL());while (g.R.size()) add_relu(g.popR());return *this;}};#line 3 "other_algorithms/dual_slope_trick.hpp"// https://maspypy.com/slope-trick-3-slope-trick-%E3%81%AE%E5%87%B8%E5%85%B1%E5%BD%B9template <class T, T INF = std::numeric_limits<T>::max() / 2>class dual_slope_trick : private slope_trick<T, INF> {public:using Base = slope_trick<T, INF>;// Initialize: f(x) = 0 (x == 0), inf (otherwise)// Complexity: O(1)dual_slope_trick() : Base() {}// Get f(0)// Complexity: O(1)T get_at_zero() const { return -Base::get_min().min; }// f(x) <- f(x - d) (Move graph to right by d)// Complexity: O(log n)dual_slope_trick &shift(int d) {while (d > 0) --d, Base::add_relu(-INF).add_const(-INF);while (d < 0) ++d, Base::add_irelu(INF).add_const(-INF);return *this;}// f(x) += ax + b// Complexity: O(1)dual_slope_trick &add_linear(T a, T b) { return Base::translate(a).add_const(b), *this; }// f(x) += max(c(x - a), 0)// Complexity: O(|a| log n + 1)dual_slope_trick &add_linear_or_zero(T c, int a) {shift(-a);if (c > T()) Base::move_right_curve(c);if (c < T()) Base::move_left_curve(-c);return shift(a);}// f(x) <- min f(x - d), a <= d <= b// Complexity: O((|a| + |b|) log n)dual_slope_trick &slide_min(int a, int b) {assert(a <= b);shift(a);for (int t = 0; t < b - a; ++t) Base::add_relu(T());return *this;}};#line 4 "other_algorithms/test/dual_slope_trick.yuki2114.test.cpp"#include <iostream>#include <map>#line 7 "other_algorithms/test/dual_slope_trick.yuki2114.test.cpp"#include <vector>using namespace std;int main() {cin.tie(nullptr), ios::sync_with_stdio(false);int N, M, K;cin >> N >> M >> K;map<int, vector<pair<int, int>>> mp;for (int i = 0; i < N; ++i) {int a;cin >> a;mp[a % K].emplace_back(a / K, 0);}for (int i = 0; i < M; ++i) {int b;cin >> b;mp[b % K].emplace_back(b / K, 1);}long long ret = 0;int nmatch = 0;for (auto [key, vs] : mp) {int n0 = 0, n1 = 0;for (auto [x, t] : vs) (t ? n1 : n0)++;nmatch += min(n0, n1);if (n0 > n1) {swap(n0, n1);for (auto &[x, t] : vs) t ^= 1;}sort(vs.begin(), vs.end());dual_slope_trick<long long, 1LL << 40> dst;int last_x = vs.front().first;for (auto [x, tp] : vs) {int dx = x - last_x;dst.add_linear_or_zero(dx, 0).add_linear_or_zero(-dx, 0);if (tp == 0) {dst.shift(1);} else {dst.slide_min(-1, 0);}last_x = x;}ret += dst.get_at_zero();}if (nmatch < min(N, M)) ret = -1;cout << ret << endl;}