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

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 21:17:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,016 bytes
• コンパイル時間: 2,622 ms
• コンパイル使用メモリ: 197,104 KB
• 実行使用メモリ: 38,400 KB
• 最終ジャッジ日時: 2026-04-18 21:18:26
• 合計ジャッジ時間: 22,885 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 2e15; // Safe INF to prevent overflow during intermediate calculations

struct Node {
    ll min_buy, max_sell, best_pair;
    int buy_idx, sell_idx, p_buy_idx, p_sell_idx;
    ll min_cap, lazy;

    Node() : min_buy(INF), max_sell(-INF), best_pair(-INF), 
             buy_idx(-1), sell_idx(-1), p_buy_idx(-1), p_sell_idx(-1), 
             min_cap(INF), lazy(0) {}
};

struct SegTree {
    int n;
    vector<Node> tree;

    SegTree(int _n, const vector<ll>& A, const vector<ll>& C, ll K) {
        n = 1; while (n < _n) n <<= 1;
        tree.resize(2 * n);
        for (int i = 0; i < _n; i++) {
            int v = i + n;
            tree[v].min_buy = A[i]; tree[v].buy_idx = i;
            tree[v].max_sell = C[i]; tree[v].sell_idx = i;
            tree[v].best_pair = C[i] - A[i];
            tree[v].p_buy_idx = i; tree[v].p_sell_idx = i;
            tree[v].min_cap = (i < _n - 1 ? K : INF);
        }
        for (int i = n - 1; i > 0; i--) pull(i);
    }

    void pull(int v) {
        Node &l = tree[2 * v], &r = tree[2 * v + 1];
        
        // 1. Standard Min/Max updates
        if (l.min_buy <= r.min_buy) { tree[v].min_buy = l.min_buy; tree[v].buy_idx = l.buy_idx; }
        else { tree[v].min_buy = r.min_buy; tree[v].buy_idx = r.buy_idx; }
        
        if (l.max_sell >= r.max_sell) { tree[v].max_sell = l.max_sell; tree[v].sell_idx = l.sell_idx; }
        else { tree[v].max_sell = r.max_sell; tree[v].sell_idx = r.sell_idx; }

        tree[v].min_cap = min(l.min_cap, r.min_cap);

        // 2. Best Pair (Internal to children)
        if (l.best_pair >= r.best_pair) {
            tree[v].best_pair = l.best_pair;
            tree[v].p_buy_idx = l.p_buy_idx;
            tree[v].p_sell_idx = l.p_sell_idx;
        } else {
            tree[v].best_pair = r.best_pair;
            tree[v].p_buy_idx = r.p_buy_idx;
            tree[v].p_sell_idx = r.p_sell_idx;
        }

        // 3. Cross-node matching (Buy in Left, Sell in Right)
        // If min_cap > 0, there is at least some capacity to move items between the two halves
        if (l.min_cap > 0) {
            ll cross_profit = r.max_sell - l.min_buy;
            if (cross_profit > tree[v].best_pair) {
                tree[v].best_pair = cross_profit;
                tree[v].p_buy_idx = l.buy_idx;
                tree[v].p_sell_idx = r.sell_idx;
            }
        }
    }

    void apply(int v, ll val) {
        tree[v].min_cap += val;
        tree[v].lazy += val;
    }

    void push(int v) {
        if (tree[v].lazy != 0) {
            apply(2 * v, tree[v].lazy);
            apply(2 * v + 1, tree[v].lazy);
            tree[v].lazy = 0;
        }
    }

    void add_cap(int v, int tl, int tr, int l, int r, ll val) {
        if (l > r) return;
        if (l == tl && r == tr) { apply(v, val); return; }
        push(v);
        int tm = (tl + tr) / 2;
        add_cap(2 * v, tl, tm, l, min(r, tm), val);
        add_cap(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
        pull(v);
    }

    void update_point(int v, int tl, int tr, int pos, ll buy, ll sell) {
        if (tl == tr) {
            tree[v].min_buy = buy;
            tree[v].max_sell = sell;
            tree[v].best_pair = sell - buy;
            return;
        }
        push(v);
        int tm = (tl + tr) / 2;
        if (pos <= tm) update_point(2 * v, tl, tm, pos, buy, sell);
        else update_point(2 * v + 1, tm + 1, tr, pos, buy, sell);
        pull(v);
    }

    ll query_cap(int v, int tl, int tr, int l, int r) {
        if (l > r) return INF;
        if (l == tl && r == tr) return tree[v].min_cap;
        push(v);
        int tm = (tl + tr) / 2;
        return min(query_cap(2 * v, tl, tm, l, min(r, tm)),
                   query_cap(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
    }
};

void solve() {
    int N; ll K;
    if (!(cin >> N >> K)) return;
    vector<ll> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];

    SegTree st(N, A, C, K);
    ll ans = 0;

    while (st.tree[1].best_pair > 0) {
        int i = st.tree[1].p_buy_idx;
        int j = st.tree[1].p_sell_idx;
        
        ll flow = min(B[i], D[j]);
        if (i < j) flow = min(flow, st.query_cap(1, 0, st.n - 1, i, j - 1));
        
        if (flow <= 0) break; // Should not happen given best_pair > 0 logic, but safe

        ans += flow * (C[j] - A[i]);
        B[i] -= flow; D[j] -= flow;
        
        if (i < j) st.add_cap(1, 0, st.n - 1, i, j - 1, -flow);
        
        st.update_point(1, 0, st.n - 1, i, (B[i] > 0 ? A[i] : INF), (D[i] > 0 ? C[i] : -INF));
        if (i != j) st.update_point(1, 0, st.n - 1, j, (B[j] > 0 ? A[j] : INF), (D[j] > 0 ? C[j] : -INF));
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}