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

• 問題: No.3509 Get More Money
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 22:35:50
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 5,094 bytes
• コンパイル時間: 1,900 ms
• コンパイル使用メモリ: 192,696 KB
• 実行使用メモリ: 19,072 KB
• 最終ジャッジ日時: 2026-04-17 22:36:20
• 合計ジャッジ時間: 21,276 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	WA * 1
other	WA * 24 RE * 36

ソースコード

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

using int64 = long long;
using i128 = __int128_t;

struct Node {
  int left = 0;
  int right = 0;
  int64 cnt = 0;
  int64 sum = 0;
};

struct SegTree {
  int n = 0;
  std::vector<int64> val;
  std::vector<Node> pool;

  explicit SegTree(std::vector<int64> values)
      : n((int)values.size() - 1), val(std::move(values)) {
    pool.reserve(64);
    pool.push_back(Node());
  }

  int new_node() {
    pool.push_back(Node());
    return (int)pool.size() - 1;
  }

  void pull(int p) {
    pool[p].cnt = pool[pool[p].left].cnt + pool[pool[p].right].cnt;
    pool[p].sum = pool[pool[p].left].sum + pool[pool[p].right].sum;
  }

  void point_add(int &p, int l, int r, int idx, int64 delta) {
    if (p == 0)
      p = new_node();
    if (l == r) {
      pool[p].cnt += delta;
      pool[p].sum = pool[p].cnt * val[l];
      return;
    }
    int mid = (l + r) >> 1;
    if (idx <= mid) {
      point_add(pool[p].left, l, mid, idx, delta);
    } else {
      point_add(pool[p].right, mid + 1, r, idx, delta);
    }
    pull(p);
  }

  int64 query_cnt(int p, int l, int r, int ql, int qr) const {
    if (p == 0 || qr < l || r < ql)
      return 0;
    if (ql <= l && r <= qr)
      return pool[p].cnt;
    int mid = (l + r) >> 1;
    return query_cnt(pool[p].left, l, mid, ql, qr) +
           query_cnt(pool[p].right, mid + 1, r, ql, qr);
  }

  int64 query_sum(int p, int l, int r, int ql, int qr) const {
    if (p == 0 || qr < l || r < ql)
      return 0;
    if (ql <= l && r <= qr)
      return pool[p].sum;
    int mid = (l + r) >> 1;
    return query_sum(pool[p].left, l, mid, ql, qr) +
           query_sum(pool[p].right, mid + 1, r, ql, qr);
  }

  int clear_range(int p, int l, int r, int ql, int qr) {
    if (p == 0 || qr < l || r < ql)
      return p;
    if (ql <= l && r <= qr)
      return 0;
    int mid = (l + r) >> 1;
    pool[p].left = clear_range(pool[p].left, l, mid, ql, qr);
    pool[p].right = clear_range(pool[p].right, mid + 1, r, ql, qr);
    pull(p);
    if (pool[p].cnt == 0)
      return 0;
    return p;
  }

  int kth(int p, int l, int r, int64 k) const {
    if (l == r)
      return l;
    int mid = (l + r) >> 1;
    int64 lc = pool[pool[p].left].cnt;
    if (k <= lc)
      return kth(pool[p].left, l, mid, k);
    return kth(pool[p].right, mid + 1, r, k - lc);
  }
};

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

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

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

    std::vector<int64> A(N), B(N), C(N), D(N);
    std::vector<int64> xs;
    xs.reserve(2 * N + 1);
    xs.push_back(0);

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

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

    std::vector<int64> val(1);
    val.insert(val.end(), xs.begin(), xs.end());
    SegTree seg(val);

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

    int root = 0;
    seg.point_add(root, 1, seg.n, idx_of(0), K);

    i128 ans = 0;

    for (int i = N - 1; i >= 0; --i) {
      int idx_c = idx_of(C[i]);
      int idx_a = idx_of(A[i]);

      seg.point_add(root, 1, seg.n, idx_c, D[i]);

      int64 total_cnt = seg.pool[root].cnt;
      int64 cnt_le_a = seg.query_cnt(root, 1, seg.n, 1, idx_a);
      int64 cnt_gt_a = total_cnt - cnt_le_a;
      int64 take = std::min<int64>(B[i], cnt_gt_a);

      if (take > 0) {
        int cut = seg.kth(root, 1, seg.n, total_cnt - take + 1);
        int64 cnt_le_cut = seg.query_cnt(root, 1, seg.n, 1, cut);
        int64 cnt_gt_cut = total_cnt - cnt_le_cut;
        int64 rem_at_cut = take - cnt_gt_cut;

        int64 sum_le_cut = seg.query_sum(root, 1, seg.n, 1, cut);
        int64 sum_gt_cut = seg.pool[root].sum - sum_le_cut;
        int64 removed_sum = sum_gt_cut + rem_at_cut * seg.val[cut];

        ans += (i128)removed_sum - (i128)take * A[i];

        if (cut < seg.n)
          root = seg.clear_range(root, 1, seg.n, cut + 1, seg.n);
        seg.point_add(root, 1, seg.n, cut, -rem_at_cut);
        seg.point_add(root, 1, seg.n, idx_a, take);
      }

      if (D[i] > 0) {
        int cut = seg.kth(root, 1, seg.n, D[i]);
        int64 cnt_lt_cut = seg.query_cnt(root, 1, seg.n, 1, cut - 1);
        int64 rem_at_cut = D[i] - cnt_lt_cut;

        if (cut > 1)
          root = seg.clear_range(root, 1, seg.n, 1, cut - 1);
        seg.point_add(root, 1, seg.n, cut, -rem_at_cut);
      }
    }

    print_i128(ans);
  }

  return 0;
}