結果

問題 No.3509 Get More Money
コンテスト
ユーザー rumblycascade7
提出日時 2026-04-18 06:09:41
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 381 ms / 2,000 ms
コード長 3,010 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,758 ms
コンパイル使用メモリ 350,400 KB
実行使用メモリ 34,860 KB
最終ジャッジ日時 2026-04-18 06:10:06
合計ジャッジ時間 20,005 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

struct S {
    int n;
    vector<ll> mx, lz;
    void init(int n_) {
        n = max(n_, 1);
        mx.assign(4 * n, 0);
        lz.assign(4 * n, 0);
    }
    void ap(int nd, ll v) { mx[nd] += v; lz[nd] += v; }
    void pu(int nd) {
        if (lz[nd]) {
            ap(2 * nd, lz[nd]);
            ap(2 * nd + 1, lz[nd]);
            lz[nd] = 0;
        }
    }
    void up(int nd, int l, int r, int ql, int qr, ll v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { ap(nd, v); return; }
        pu(nd);
        int m = (l + r) >> 1;
        up(2 * nd, l, m, ql, qr, v);
        up(2 * nd + 1, m + 1, r, ql, qr, v);
        mx[nd] = max(mx[2 * nd], mx[2 * nd + 1]);
    }
    ll qr2(int nd, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return mx[nd];
        pu(nd);
        int m = (l + r) >> 1;
        return max(qr2(2 * nd, l, m, ql, qr), qr2(2 * nd + 1, m + 1, r, ql, qr));
    }
    void add(int l, int r, ll v) { if (l > r) return; up(1, 0, n - 1, l, r, v); }
    ll qm(int l, int r) { if (l > r) return 0; return qr2(1, 0, n - 1, l, r); }
};

struct J {
    ll p;
    int s;
    ll q;
    bool operator>(const J &o) const {
        if (p != o.p) return p > o.p;
        return s > o.s;
    }
};

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n; ll K;
        scanf("%d %lld", &n, &K);
        vector<ll> A(n + 2), B(n + 2), C(n + 2), D(n + 2);
        for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
        for (int i = 1; i <= n; i++) scanf("%lld", &B[i]);
        for (int i = 1; i <= n; i++) scanf("%lld", &C[i]);
        for (int i = 1; i <= n; i++) scanf("%lld", &D[i]);

        S sg;
        sg.init(n + 2);

        priority_queue<J, vector<J>, greater<J>> H;

        ll g = 0;

        for (int i = 1; i <= n; i++) {
            if (B[i] > 0) H.push({A[i], i, B[i]});
            ll d = D[i];
            while (d > 0) {
                while (!H.empty()) {
                    J e = H.top();
                    if (e.q == 0) { H.pop(); continue; }
                    if (e.s < i) {
                        ll m = sg.qm(e.s, i - 1);
                        if (m >= K) { H.pop(); continue; }
                    }
                    break;
                }
                if (H.empty()) break;
                J e = H.top();
                if (e.p >= C[i]) break;
                ll sl;
                if (e.s >= i) sl = (ll)4e18;
                else sl = K - sg.qm(e.s, i - 1);
                ll tk = min({e.q, d, sl});
                if (tk <= 0) { H.pop(); continue; }
                g += (C[i] - e.p) * tk;
                if (e.s < i) sg.add(e.s, i - 1, tk);
                d -= tk;
                H.pop();
                if (e.q - tk > 0) H.push({e.p, e.s, e.q - tk});
                H.push({C[i], i, tk});
            }
        }

        printf("%lld\n", g);
    }
    return 0;
}
0