#1171219 (C++23(gnu拡張gcc16)) No.2114 01 Matching

• 問題: No.2114 01 Matching
• ユーザー: baluteshih
• 提出日時: 2026-07-12 02:27:09
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 305 ms / 5,000 ms
• コード長: 6,060 bytes
• コンパイル時間: 5,272 ms
• コンパイル使用メモリ: 364,880 KB
• 実行使用メモリ: 47,488 KB
• 最終ジャッジ日時: 2026-07-12 02:27:27
• 合計ジャッジ時間: 15,682 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	AC * 2
other	AC * 51

ソースコード

#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2114"
#line 2 "cplibrary/assumption.hpp"

#include <cassert>
#include <bits/stdc++.h>
#line 3 "test.cpp"

#line 2 "cplibrary/DataStructure/Convex/ConjugateSlopeTrick.hpp"

#line 2 "cplibrary/DataStructure/Convex/SlopeTrick.hpp"

/*
reference: https://maspypy.com/slope-trick-1-解説編
maintaining f(x) = min_f + sum_{l \in pq_l} (l - x) + sum_{r \in pq_r} (x - r)
*/

template<typename T, T INF = std::numeric_limits<T>::max() / 2>
class SlopeTrick {
    using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    using max_heap = std::priority_queue<T>;
    max_heap pq_l;
    min_heap pq_r;
    T min_f;
    T top_l() const { return pq_l.empty() ? -INF : pq_l.top() + add_l; }
    T top_r() const { return pq_r.empty() ? INF : pq_r.top() + add_r; }
    T pop_l() { T res = top_l(); if (!pq_l.empty()) pq_l.pop(); return res; }
    T pop_r() { T res = top_r(); if (!pq_r.empty()) pq_r.pop(); return res; }
    void push_l(T a) { pq_l.push(a - add_l); }
    void push_r(T a) { pq_r.push(a - add_r); }
protected:
    T add_l, add_r; 
public:
    SlopeTrick() : min_f(), add_l(), add_r() {}
    bool is_inf(T v) { return v >= INF || v <= -INF; }
    int size_l() { return pq_l.size(); }
    int size_r() { return pq_r.size(); }
    int size() { return size_l() + size_r(); }
    T top() { return min_f; }
    std::pair<T, T> top_interval() { return {top_l(), top_r()}; }
    SlopeTrick& add_const(T a) { return min_f += a, *this; }
    // add (x - a)+
    SlopeTrick& add_x_minus_a(T a) {
        min_f += std::max(T(0), top_l() - a);
        push_l(a), push_r(pop_l());
        return *this;
    }
    // add (a - x)+
    SlopeTrick& add_a_minus_x(T a) {
        min_f += std::max(T(0), a - top_r());
        push_r(a), push_l(pop_r());
        return *this;
    }
    // add |x - a|
    SlopeTrick& add_abs(T a) { return add_x_minus_a(a).add_a_minus_x(a); } 
    // add ax + b, O(|a| log n)
    SlopeTrick& add_linear(int a, T b) {
        for (min_f += b; a > 0; --a) {
            T x = pop_l();
            min_f += x, push_r(x);
        }
        for (; a < 0; ++a) {
            T x = pop_r();
            min_f -= x, push_l(x);
        }
        return *this;
    }
    // f(x) = f(x - a)
    SlopeTrick& shift(T a) { return add_l += a, add_r += a, *this; }
    // g(x) = min_{x-b <= y <= x-a} f(y)
    SlopeTrick& sliding_window_minimum(T a, T b) {
        assert(a <= b);
        add_l += a, add_r += b;
        return *this;
    }
    SlopeTrick& prefix_min() { return min_heap().swap(pq_r), *this; }
    SlopeTrick& suffix_min() { return max_heap().swap(pq_l), *this; }
    T eval(T x) {
        T res = min_f;
        auto tl = pq_l; auto tr = pq_r;
        for (; !tl.empty(); tl.pop()) res += std::max(T(0), (tl.top() + add_l) - x);
        for (; !tr.empty(); tr.pop()) res += std::max(T(0), x - (tr.top() + add_r));
        return res;
    }
};
#line 4 "cplibrary/DataStructure/Convex/ConjugateSlopeTrick.hpp"

/*
reference: https://maspypy.com/slope-trick-3-slope-trick-の凸共役 
Let f(x) = min_f + sum_{l \in pq_l} (l - x) + sum_{r \in pq_r} (x - r)
maintaining f(x) using its convex conjugate f*(p)
f*(p) is maintained by the standard SlopeTrick
*/

template<typename T, T INF = std::numeric_limits<T>::max() / 2>
class ConjugateSlopeTrick : private SlopeTrick<T, INF> {
    using super = SlopeTrick<T, INF>;
public:
    ConjugateSlopeTrick() : super() {}
    using super::is_inf;
    T f0() { return -super::top(); }
    ConjugateSlopeTrick& add_const(T a) { super::add_const(a); }
    // add c(x - a)+
    ConjugateSlopeTrick& add_x_minus_a(T c, T a = 0) {
        if (a) shift(-a);
        if (c > 0) super::add_r += c;
        if (c < 0) super::add_l += c;
        if (a) shift(a);
        return *this;
    }
    // add c|x - a|
    ConjugateSlopeTrick& add_abs(T c, T a = 0) { return add_x_minus_a(c, a).add_x_minus_a(-c, a); }
    // add ax + b, O(1)
    ConjugateSlopeTrick& add_linear(T a, T b = 0) { return super::shift(a).add_const(b), *this; }
    // f(x) = f(x - a), O(|a| log n)
    ConjugateSlopeTrick& shift(int a) { return super::add_linear(a, 0), *this; }
    // g(x) = min_{x-b <= y <= x-a} f(y)
    ConjugateSlopeTrick& sliding_window_minimum(T a, T b) {
        assert(a <= b);
        shift(a);
        for (int i = 0; i < b - a; ++i) super::add_x_minus_a(0);
        return *this;
    }
    // f(x) = min_i(f(x + (i + base)) + g[i]), g[i + 1] - g[i] >= g[i] - g[i - 1]
    ConjugateSlopeTrick& convolve(const std::vector<T>& g, int base = 0) {
        for (int i = 1; i < int(g.size()); ++i) super::add_x_minus_a(g[i] - g[i - 1]);
        if (base != 0) shift(-base);
        return *this;
    }
    ConjugateSlopeTrick& clear_left() { return super::suffix_min(), *this; }
    ConjugateSlopeTrick& clear_right() { return super::prefix_min(), *this; }
    // find min_x(f(x) - px)
    T min_val(T p = 0) {
        return -super::eval(p);
    }
};
#line 5 "test.cpp"

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    int n, m, k;
    std::cin >> n >> m >> k;
    long long ans = 0;
    std::map<int, std::vector<std::pair<int, int>>> arr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        arr[x % k].emplace_back(x / k, n > m);
    }
    for (int i = 0; i < m; ++i) {
        int x;
        std::cin >> x;
        arr[x % k].emplace_back(x / k, n <= m);
    }
    for (auto [_, vec] : arr) {
        std::ranges::sort(vec);
        int tot = 0;
        ConjugateSlopeTrick<long long> slope;
        for (int i = 0; i < int(vec.size()); ++i) {
            if (vec[i].second == 1) {
                ++tot;
                slope.convolve({0, 0});
            }
            else {
                --tot;
                slope.shift(-1);
            }
            if (i + 1 < int(vec.size()))
                slope.add_abs(vec[i + 1].first - vec[i].first);
        }
        if (tot < 0) return std::cout << "-1\n", 0;
        ans += slope.f0();
    }
    std::cout << ans << "\n";
}