結果

問題 No.1467 Selling Cars
コンテスト
ユーザー Kanten4205
提出日時 2025-11-20 03:09:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,628 ms / 4,000 ms
コード長 6,442 bytes
コンパイル時間 4,486 ms
コンパイル使用メモリ 107,860 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-20 03:09:31
合計ジャッジ時間 13,209 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const long long INF = 1e18;

// 入力変数
int M, N;
vector<long long> A, B;
vector<long long> ans;

// Slope Trick の実装
// 関数 f(x) の形状を管理するデータ構造
// L: 傾きが減少する点 (max-heap)
// R: 傾きが増加する点 (min-heap)
// min_val: 関数の最小値
struct SlopeTrick {
    using P = pair<long long, long long>; // {座標, 重み(傾きの変化量)}
    priority_queue<P> L;
    priority_queue<P, vector<P>, greater<P>> R;
    long long lazy_L;
    long long lazy_R;
    long long min_val;

    SlopeTrick() : lazy_L(0), lazy_R(0), min_val(0) {}

    // グラフ全体を v だけ平行移動 f(x) -> f(x - v)
    // つまり座標 x が x + v に移動する
    void shift(long long v) {
        lazy_L += v;
        lazy_R += v;
    }

    // 最小値をとる区間の右側を k 拡張する (Min-Convolution with [0, k])
    void expand_right(long long k) {
        lazy_R += k;
    }

    // コスト w * |x| を加算する
    // x=0 で傾きが -w から +w に 2w 変化する (Lにw, Rにw)
    void add_abs_x(long long w) {
        // Lに追加 (内部座標 = 0 - lazy_L)
        L.push({-lazy_L, w});
        // Rに追加 (内部座標 = 0 - lazy_R)
        R.push({-lazy_R, w});

        // Lの最大値 > Rの最小値 となっている場合、整合性を取る（スワップして最小値を持ち上げる）
        while (true) {
            if (L.empty() || R.empty()) break;

            auto l_top = L.top();
            long long l_real = l_top.first + lazy_L;
            long long l_w = l_top.second;

            auto r_top = R.top();
            long long r_real = r_top.first + lazy_R;
            long long r_w = r_top.second;

            if (l_real <= r_real) break;

            // 交換が必要
            L.pop(); R.pop();

            long long move_w = min(l_w, r_w);
            
            // 最小値の上昇分 = (L - R) * weight
            min_val += move_w * (l_real - r_real);

            // 余った重みを戻す
            if (l_w > move_w) L.push({l_top.first, l_w - move_w});
            if (r_w > move_w) R.push({r_top.first, r_w - move_w});

            // スワップして挿入
            // l_real は R に行く
            R.push({l_real - lazy_R, move_w});
            // r_real は L に行く
            L.push({r_real - lazy_L, move_w});
        }
    }

    // x = 0 での値を計算して返す
    long long query_0() {
        long long res = min_val;

        // 0 が最小値区間 [L_max, R_min] の外にある場合、その分の傾きコストを加算
        
        // 左側の壁 (L)
        auto tmp_L = L;
        while (!tmp_L.empty()) {
            auto top = tmp_L.top(); tmp_L.pop();
            long long c = top.first + lazy_L;
            long long w = top.second;
            if (c > 0) {
                res += (c - 0) * w;
            } else {
                break; // 降順なのでこれ以降は c <= 0
            }
        }

        // 右側の壁 (R)
        auto tmp_R = R;
        while (!tmp_R.empty()) {
            auto top = tmp_R.top(); tmp_R.pop();
            long long c = top.first + lazy_R;
            long long w = top.second;
            if (c < 0) {
                res += (0 - c) * w;
            } else {
                break; // 昇順なのでこれ以降は c >= 0
            }
        }
        
        return res;
    }
};

// 容量 k での最小コスト計算
long long calc(int k) {
    if (k <= 0) return INF;
    if (k > M) k = M;

    SlopeTrick st;
    
    // 初期状態: x=0 のみ有効 (コスト0)、他は無限大
    // 十分大きなコストを入れて境界を作る
    const long long BIG_COST = 1e15;
    st.L.push({0, BIG_COST});
    st.R.push({0, BIG_COST});

    // イベント作成: (座標, タイプ)
    // Type 0: A (需要, x -> x-1)
    // Type 1: B (供給, x -> x + [0, k])
    vector<pair<long long, int>> events;
    events.reserve(M + N);
    for (long long x : A) events.push_back({x, 0});
    for (long long x : B) events.push_back({x, 1});

    sort(events.begin(), events.end());

    long long prev_x = events[0].first;

    for (auto& e : events) {
        long long curr_x = e.first;
        int type = e.second;

        // 1. 移動コストの加算: 距離 * |現在の過不足数|
        long long dist = curr_x - prev_x;
        if (dist > 0) {
            st.add_abs_x(dist);
        }

        // 2. イベント処理
        if (type == 0) {
            // A: 需要 (過不足数が 1 減る)
            // F_new(x) = F_old(x+1) => グラフ全体が左に1ずれる
            st.shift(-1);
        } else {
            // B: 供給 (過不足数が 0~k 増える)
            // F_new(x) = min_{0<=t<=k} F_old(x-t) => 最小値区間の右端が k 伸びる
            st.expand_right(k);
        }

        prev_x = curr_x;
    }

    // 最終的に過不足数が 0 である状態のコストが答え
    return st.query_0();
}

// 分割統治 (Divide & Conquer Optimization)
// 解の凸性を利用して計算をスキップ
void solve_dc(int l, int r) {
    if (l + 1 >= r) return;

    int mid = (l + r) / 2;
    ans[mid] = calc(mid);

    // 3点が同一直線上にあるかチェック (傾きが一定か)
    long long dy1 = ans[mid] - ans[l];
    long long dx1 = mid - l;
    long long dy2 = ans[r] - ans[mid];
    long long dx2 = r - mid;

    if (dy1 * dx2 == dy2 * dx1) {
        // 線形補間
        long long slope = dy1 / dx1;
        for (int i = l + 1; i < r; ++i) {
            if (i == mid) continue;
            ans[i] = ans[l] + slope * (long long)(i - l);
        }
        return;
    }

    solve_dc(l, mid);
    solve_dc(mid, r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> M >> N)) return 0;

    A.resize(M);
    for (int i = 0; i < M; ++i) cin >> A[i];
    B.resize(N);
    for (int i = 0; i < N; ++i) cin >> B[i];

    // ソートは必須
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ans.resize(M + 1);

    // 両端を計算
    ans[1] = calc(1);
    ans[M] = calc(M);

    // D&C で間を埋める
    solve_dc(1, M);

    for (int i = 1; i <= M; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}
0