#1159547 (C++17) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: 왕지후
• 提出日時: 2026-04-18 13:02:01
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,632 bytes
• コンパイル時間: 2,796 ms
• コンパイル使用メモリ: 234,944 KB
• 実行使用メモリ: 35,440 KB
• 最終ジャッジ日時: 2026-04-18 13:02:37
• 合計ジャッジ時間: 30,049 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

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

using int64 = long long;
using i128 = __int128_t;

struct SegTree {
    int n;
    const vector<int>* vals; // 1-indexed compressed values
    vector<int64> cnt;
    vector<int64> sum;

    SegTree() {}
    SegTree(int n, const vector<int>* vals) : n(n), vals(vals) {
        cnt.assign(4 * n + 5, 0);
        sum.assign(4 * n + 5, 0);
    }

    void add(int node, int l, int r, int idx, int64 delta) {
        if (l == r) {
            cnt[node] += delta;
            sum[node] += delta * (int64)(*vals)[l];
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) add(node << 1, l, mid, idx, delta);
        else add(node << 1 | 1, mid + 1, r, idx, delta);
        cnt[node] = cnt[node << 1] + cnt[node << 1 | 1];
        sum[node] = sum[node << 1] + sum[node << 1 | 1];
    }

    void add(int idx, int64 delta) {
        if (delta == 0) return;
        add(1, 1, n, idx, delta);
    }

    // remove up to k largest elements in [ql, qr]
    pair<int64, int64> removeLargest(int node, int l, int r, int ql, int qr, int64 &k) {
        if (k == 0 || r < ql || qr < l || cnt[node] == 0) return {0, 0};

        if (ql <= l && r <= qr && cnt[node] <= k) {
            int64 rc = cnt[node];
            int64 rs = sum[node];
            cnt[node] = 0;
            sum[node] = 0;
            k -= rc;
            return {rc, rs};
        }

        if (l == r) {
            int64 take = min(k, cnt[node]);
            cnt[node] -= take;
            sum[node] -= take * (int64)(*vals)[l];
            k -= take;
            return {take, take * (int64)(*vals)[l]};
        }

        int mid = (l + r) >> 1;
        auto right = removeLargest(node << 1 | 1, mid + 1, r, ql, qr, k);
        auto left  = removeLargest(node << 1, l, mid, ql, qr, k);

        cnt[node] = cnt[node << 1] + cnt[node << 1 | 1];
        sum[node] = sum[node << 1] + sum[node << 1 | 1];
        return {left.first + right.first, left.second + right.second};
    }

    pair<int64, int64> removeLargest(int ql, int qr, int64 k) {
        if (ql > qr || k <= 0) return {0, 0};
        return removeLargest(1, 1, n, ql, qr, k);
    }

    // remove up to k smallest elements in [ql, qr]
    pair<int64, int64> removeSmallest(int node, int l, int r, int ql, int qr, int64 &k) {
        if (k == 0 || r < ql || qr < l || cnt[node] == 0) return {0, 0};

        if (ql <= l && r <= qr && cnt[node] <= k) {
            int64 rc = cnt[node];
            int64 rs = sum[node];
            cnt[node] = 0;
            sum[node] = 0;
            k -= rc;
            return {rc, rs};
        }

        if (l == r) {
            int64 take = min(k, cnt[node]);
            cnt[node] -= take;
            sum[node] -= take * (int64)(*vals)[l];
            k -= take;
            return {take, take * (int64)(*vals)[l]};
        }

        int mid = (l + r) >> 1;
        auto left  = removeSmallest(node << 1, l, mid, ql, qr, k);
        auto right = removeSmallest(node << 1 | 1, mid + 1, r, ql, qr, k);

        cnt[node] = cnt[node << 1] + cnt[node << 1 | 1];
        sum[node] = sum[node << 1] + sum[node << 1 | 1];
        return {left.first + right.first, left.second + right.second};
    }

    pair<int64, int64> removeSmallest(int ql, int qr, int64 k) {
        if (ql > qr || k <= 0) return {0, 0};
        return removeSmallest(1, 1, n, ql, qr, k);
    }

    int64 totalCount() const {
        return cnt[1];
    }
};

static void print_i128(i128 x) {
    if (x == 0) {
        cout << 0 << '\n';
        return;
    }
    string s;
    while (x > 0) {
        int d = (int)(x % 10);
        s.push_back(char('0' + d));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s << '\n';
}

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

    int T;
    cin >> T;

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

        vector<int> A(N + 1), C(N + 1);
        vector<int64> B(N + 1), D(N + 1);

        for (int i = 1; i <= N; i++) cin >> A[i];
        for (int i = 1; i <= N; i++) cin >> B[i];
        for (int i = 1; i <= N; i++) cin >> C[i];
        for (int i = 1; i <= N; i++) cin >> D[i];

        vector<int> xs;
        xs.reserve(2 * N);
        for (int i = 1; i <= N; i++) {
            xs.push_back(A[i]);
            xs.push_back(C[i]);
        }
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());

        vector<int> vals(1, 0); // 1-indexed
        for (int v : xs) vals.push_back(v);

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

        int M = (int)xs.size();
        SegTree seg(M, &vals);

        i128 answer = 0;

        for (int i = N; i >= 1; i--) {
            int idxA = getIdx(A[i]);
            int idxC = getIdx(C[i]);

            // 1) add D_i copies of C_i
            seg.add(idxC, D[i]);

            // 2) choose up to B_i largest values strictly greater than A_i
            auto rem = seg.removeLargest(idxA + 1, M, B[i]);
            int64 removedCnt = rem.first;
            int64 removedSum = rem.second;

            // gain = sum(value - A_i)
            answer += (i128)removedSum - (i128)removedCnt * (i128)A[i];

            // those chosen values turn into A_i
            seg.add(idxA, removedCnt);

            // 3) keep only top K marginals
            int64 excess = seg.totalCount() - K;
            if (excess > 0) {
                seg.removeSmallest(1, M, excess);
            }
        }

        print_i128(answer);
    }

    return 0;
}