#1152283 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: Naru820
• 提出日時: 2026-03-12 20:23:22
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 490 ms / 2,000 ms
• コード長: 5,417 bytes
• コンパイル時間: 4,456 ms
• コンパイル使用メモリ: 353,612 KB
• 実行使用メモリ: 38,372 KB
• 最終ジャッジ日時: 2026-04-17 19:34:59
• 合計ジャッジ時間: 25,222 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 60

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<long long> cnt;   // 個数
    vector<long long> sum;   // 値の総和
    vector<char> lazy;       // この区間は全消去されたか
    vector<int> vals;        // 1-indexed compressed values

    SegTree() : n(0) {}
    SegTree(const vector<int>& v) { init(v); }

    static long long mul(long long a, long long b) {
        return (long long)((__int128)a * b);
    }

    void init(const vector<int>& v) {
        vals = v;                    // vals[1..n] を使う
        n = (int)vals.size() - 1;
        cnt.assign(4 * max(1, n) + 5, 0);
        sum.assign(4 * max(1, n) + 5, 0);
        lazy.assign(4 * max(1, n) + 5, 0);
    }

    void clear_node(int p) {
        cnt[p] = 0;
        sum[p] = 0;
        lazy[p] = 1;
    }

    void push(int p) {
        if (!lazy[p]) return;
        clear_node(p << 1);
        clear_node(p << 1 | 1);
        lazy[p] = 0;
    }

    void pull(int p) {
        cnt[p] = cnt[p << 1] + cnt[p << 1 | 1];
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }

    void add(int p, int l, int r, int idx, long long delta) {
        if (l == r) {
            cnt[p] += delta;
            sum[p] += mul(delta, vals[l]);
            return;
        }
        push(p);
        int m = (l + r) >> 1;
        if (idx <= m) add(p << 1, l, m, idx, delta);
        else add(p << 1 | 1, m + 1, r, idx, delta);
        pull(p);
    }

    void add(int idx, long long delta) {
        add(1, 1, n, idx, delta);
    }

    // 最小 k 個を削除し、その総和を返す
    long long take_smallest(int p, int l, int r, long long k) {
        if (k == 0 || cnt[p] == 0) return 0;
        if (l == r) {
            long long take = k;
            cnt[p] -= take;
            long long res = mul(take, vals[l]);
            sum[p] -= res;
            return res;
        }
        push(p);
        int m = (l + r) >> 1;
        long long res = 0;

        if (cnt[p << 1] >= k) {
            res = take_smallest(p << 1, l, m, k);
        } else {
            long long leftCnt = cnt[p << 1];
            res += sum[p << 1];
            clear_node(p << 1);
            res += take_smallest(p << 1 | 1, m + 1, r, k - leftCnt);
        }
        pull(p);
        return res;
    }

    long long take_smallest(long long k) {
        if (k == 0) return 0;
        return take_smallest(1, 1, n, k);
    }

    // 最大 k 個を削除し、その総和を返す
    long long take_largest(int p, int l, int r, long long k) {
        if (k == 0 || cnt[p] == 0) return 0;
        if (l == r) {
            long long take = k;
            cnt[p] -= take;
            long long res = mul(take, vals[l]);
            sum[p] -= res;
            return res;
        }
        push(p);
        int m = (l + r) >> 1;
        long long res = 0;

        if (cnt[p << 1 | 1] >= k) {
            res = take_largest(p << 1 | 1, m + 1, r, k);
        } else {
            long long rightCnt = cnt[p << 1 | 1];
            res += sum[p << 1 | 1];
            clear_node(p << 1 | 1);
            res += take_largest(p << 1, l, m, k - rightCnt);
        }
        pull(p);
        return res;
    }

    long long take_largest(long long k) {
        if (k == 0) return 0;
        return take_largest(1, 1, n, k);
    }
};

struct Day {
    int A, C;
    long long B, D;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N;
        long long K;
        cin >> N >> K;

        vector<Day> days(N);
        vector<int> xs;
        xs.reserve(2 * N);

        for (int i = 0; i < N; ++i) {
            cin >> days[i].A;
            xs.push_back(days[i].A);
        }
        for (int i = 0; i < N; ++i) {
            cin >> days[i].B;
        }
        for (int i = 0; i < N; ++i) {
            cin >> days[i].C;
            xs.push_back(days[i].C);
        }
        for (int i = 0; i < N; ++i) {
            cin >> days[i].D;
        }

        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        // 1-indexed にする
        vector<int> vals(1, 0);
        for (int x : xs) vals.push_back(x);

        SegTree seg(vals);

        long long inf_cnt = K;   // 現在残っている「∞ の限界コスト」の個数
        long long ans = 0;       // = 最終的に求める S - 10^100

        auto get_idx = [&](int x) {
            return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
        };

        for (int i = 0; i < N; ++i) {
            int ia = get_idx(days[i].A);
            int ic = get_idx(days[i].C);

            // A_i を B_i 個追加, C_i を D_i 個追加
            seg.add(ia, days[i].B);
            seg.add(ic, days[i].D);

            // 最小 D_i 個を削除して利益更新
            long long removed_small_sum = seg.take_smallest(days[i].D);
            ans += SegTree::mul(days[i].C, days[i].D) - removed_small_sum;

            // 最大 B_i 個を削除
            // まずは ∞ から削る
            long long remove_inf = min(inf_cnt, days[i].B);
            inf_cnt -= remove_inf;

            long long need_remove_finite = days[i].B - remove_inf;
            if (need_remove_finite > 0) {
                seg.take_largest(need_remove_finite);
            }
        }

        cout << ans << '\n';
    }

    return 0;
}