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

• 問題: No.3509 Get More Money
• ユーザー: テナガザル
• 提出日時: 2026-04-19 16:22:49
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 649 ms / 2,000 ms
• コード長: 5,092 bytes
• コンパイル時間: 1,808 ms
• コンパイル使用メモリ: 204,316 KB
• 実行使用メモリ: 28,928 KB
• 最終ジャッジ日時: 2026-04-19 16:23:37
• 合計ジャッジ時間: 38,538 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

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

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>

template <typename T, typename X> class LazySegTree
{
private:
  const T et;
  const X ex;
  int num;
  std::vector<T> dat;
  std::vector<X> lazy;
  T (*const eval)(const T, const T) {};
  T (*const fa)(const T, const X) {};
  X (*const fm)(const X, const X) {};
  X (*const fp)(const X, int) {};
    
public:
  LazySegTree(std::vector<T> &v, T Et, X Ex, T (*valcal)(T, T), T (*lazyupdate)(T, X), X (*lazypropagation)(X, X), X (*rangelazy)(X, int)) : et(Et), ex(Ex), eval(valcal), fa(lazyupdate), fm(lazypropagation), fp(rangelazy)
  {
    int siz = static_cast<int>(v.size());
    for (num = 1; num < siz; num <<= 1);
    dat = std::vector<T> (2 * num - 1, et);
    lazy = std::vector<X> (2 * num - 1, ex);
    for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i];
    for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]);
  }

  LazySegTree(int n, T Et, X Ex, T (*valcal)(T, T), T (*lazyupdate)(T, X), X (*lazypropagation)(X, X), X (*rangelazy)(X, int)) : et(Et), ex(Ex), eval(valcal), fa(lazyupdate), fm(lazypropagation), fp(rangelazy)
  {
    for (num = 1; num < n; num <<= 1);
    dat = std::vector<T> (2 * num - 1, et);
    lazy = std::vector<X> (2 * num - 1, ex);
  }

  //update [left,right)
  void update(int left, int right, X val)
  {
    std::stack<std::pair<int, int>> st;
    std::stack<int> s;
    for (st.push({0, num}); !st.empty();)
    {
      auto v = st.top();
      st.pop();
      int now = (num + v.first) / (v.second - v.first) - 1;
      lazyupdate(now, v.second - v.first);
      if (left <= v.first && v.second <= right)
      {
        lazy[now] = fm(lazy[now], val);
        lazyupdate(now, v.second - v.first);
      }
      else if (!(v.second <= left || right <= v.first))
      {
        st.push({(v.first + v.second) / 2, v.second});
        st.push({v.first, (v.first + v.second) / 2});
        s.push(now);
      }
    }
    while (!s.empty())
    {
      int index = s.top();
      dat[index] = eval(dat[2 * index + 1], dat[2 * index + 2]);
      s.pop();
    }
  }

  //get value [left,right)
  T getval(int left, int right)
  {
    std::stack<std::pair<int, int>> s;
    T ans = et;
    for (s.push({0, num}); !s.empty();)
    {
      auto v = s.top();
      s.pop();
      int now = (num + v.first) / (v.second - v.first) - 1;
      lazyupdate(now, v.second - v.first);
      if (left <= v.first && v.second <= right) ans = eval(ans, dat[now]);
      else if (!(v.second <= left || right <= v.first))
      {
        s.push({(v.first + v.second) / 2, v.second});
        s.push({v.first, (v.first + v.second) / 2});
      }
    }
    return ans;
  }

  //get value [id]
  T getval(int id) {return getval(id, id + 1);}

private:
  void lazyupdate(int index, int len)
  {
    if (lazy[index] == ex) return;
    if (index < num - 1)
    {
      lazy[index * 2 + 1] = fm(lazy[index * 2 + 1], lazy[index]);
      lazy[index * 2 + 2] = fm(lazy[index * 2 + 2], lazy[index]);
    }
    dat[index] = fa(dat[index], fp(lazy[index], len));
    lazy[index] = ex;
  }
};

/*
区間代入区間和
auto eval = [](long long a, long long b) -> long long {return a + b;};
auto fa = [](long long a, long long b) -> long long {return b;};
auto fp = [](long long a, int len) -> long long {return a * len;};
LazySegTree<long long, long long> lsg(v, 0, 使わない値, eval, fa, fa, fp);

*/ 

using namespace std;

void solve()
{
  int n;
  long long k;
  cin >> n >> k;
  vector<int> a(n), b(n), c(n), d(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];
  for (int i = 0; i < n; ++i) cin >> c[i];
  for (int i = 0; i < n; ++i) cin >> d[i];
  auto eval = [](long long a, long long b) -> long long {return max(a, b);};
  auto fa = [](long long a, long long b) -> long long {return a + b;};
  auto fp = [](long long a, int len) -> long long {return a;};
  vector<long long> inif(n, 0);
  LazySegTree<long long, long long> lsg(inif, 0, 0, eval, fa, fa, fp);
  multiset<pair<int, pair<int, int>>> st;
  long long ans = 0;
  for (int i = 0; i < n; ++i)
  {
    int f = 0;
    st.insert({a[i], {-i, b[i]}});
    while (d[i] > 0 && !st.empty())
    {
      auto itr = st.begin();
      auto [v, cid] = *itr;
      if (v >= c[i]) break;
      auto [id, cap] = cid;
      id = -id;
      st.erase(itr);
      if (id == i)
      {
        long long fma = min(cap, d[i]);
        ans += fma * (c[i] - v);
        cap -= fma;
        d[i] -= fma;
        f += fma;
        if (cap > 0) st.insert({v, {-id, cap}});
      }
      else if (id < i)
      {
        long long lrma = lsg.getval(id, i);
        if (lrma >= k) continue;
        long long nok = min(d[i], cap);
        nok = min(nok, k - lrma);
        lsg.update(id, i, nok);
        ans += nok * (c[i] - v);
        d[i] -= nok;
        cap -= nok;
        f += nok;
        if (cap > 0) st.insert({v, {-id, cap}});
      }
    }
    if (f > 0) st.insert({c[i], {-i, f}});
  }
  cout << ans << endl;
}

int main()
{
  int t;
  cin >> t;
  while (t--) solve();
}