#1158932 (C) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: Nakanishi Hiro
• 提出日時: 2026-04-18 02:10:31
• 言語: C (gcc 15.2.0)
• 結果: WA
• 実行時間: -
• コード長: 5,832 bytes
• コンパイル時間: 409 ms
• コンパイル使用メモリ: 43,188 KB
• 実行使用メモリ: 25,680 KB
• 最終ジャッジ日時: 2026-04-18 02:10:55
• 合計ジャッジ時間: 17,244 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 38 WA * 22

ソースコード

#include <stdio.h>
#include <stdlib.h>

typedef long long i64;

static int *g_vals;
static i64 *seg_cnt;
static i64 *seg_sum;
static unsigned char *seg_lazy;

static inline int next_int(void) {
  int c = getchar_unlocked();
  while (c <= ' ') c = getchar_unlocked();
  int x = 0;
  while (c > ' ') {
    x = x * 10 + (c - '0');
    c = getchar_unlocked();
  }
  return x;
}

static int cmp_int(const void *pa, const void *pb) {
  int a = *(const int *)pa;
  int b = *(const int *)pb;
  return (a > b) - (a < b);
}

static void bit_add(i64 *bit, int n, int idx, i64 delta) {
  while (idx <= n) {
    bit[idx] += delta;
    idx += idx & -idx;
  }
}

static i64 bit_sum(const i64 *bit, int idx) {
  i64 s = 0;
  while (idx > 0) {
    s += bit[idx];
    idx -= idx & -idx;
  }
  return s;
}

static int bit_kth(const i64 *bit, int n, int topbit, i64 k) {
  int idx = 0;
  for (int step = topbit; step > 0; step >>= 1) {
    int nxt = idx + step;
    if (nxt <= n && bit[nxt] < k) {
      idx = nxt;
      k -= bit[nxt];
    }
  }
  return idx + 1;
}

static int lower_bound_int(const int *arr, int n, int x) {
  int lo = 0;
  int hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

static inline void seg_clear(int node) {
  seg_cnt[node] = 0;
  seg_sum[node] = 0;
  seg_lazy[node] = 1;
}

static inline void seg_pull(int node) {
  seg_cnt[node] = seg_cnt[node << 1] + seg_cnt[node << 1 | 1];
  seg_sum[node] = seg_sum[node << 1] + seg_sum[node << 1 | 1];
}

static inline void seg_push(int node) {
  if (!seg_lazy[node]) return;
  seg_clear(node << 1);
  seg_clear(node << 1 | 1);
  seg_lazy[node] = 0;
}

static void seg_add_point(int node, int l, int r, int idx, i64 delta) {
  if (l == r) {
    seg_cnt[node] += delta;
    seg_sum[node] += (i64)g_vals[l - 1] * delta;
    seg_lazy[node] = 0;
    return;
  }
  seg_push(node);
  int mid = (l + r) >> 1;
  if (idx <= mid) seg_add_point(node << 1, l, mid, idx, delta);
  else seg_add_point(node << 1 | 1, mid + 1, r, idx, delta);
  seg_pull(node);
}

static i64 seg_query_prefix_count(int node, int l, int r, int q) {
  if (q < l || seg_cnt[node] == 0) return 0;
  if (r <= q) return seg_cnt[node];
  seg_push(node);
  int mid = (l + r) >> 1;
  return seg_query_prefix_count(node << 1, l, mid, q)
       + seg_query_prefix_count(node << 1 | 1, mid + 1, r, q);
}

static i64 seg_remove_small(int node, int l, int r, i64 need) {
  if (need == 0 || seg_cnt[node] == 0) return 0;
  if (need >= seg_cnt[node]) {
    i64 ret = seg_sum[node];
    seg_clear(node);
    return ret;
  }
  if (l == r) {
    seg_cnt[node] -= need;
    i64 dec = (i64)g_vals[l - 1] * need;
    seg_sum[node] -= dec;
    return dec;
  }
  seg_push(node);
  int mid = (l + r) >> 1;
  i64 take_left = seg_cnt[node << 1] < need ? seg_cnt[node << 1] : need;
  i64 ret = seg_remove_small(node << 1, l, mid, take_left);
  ret += seg_remove_small(node << 1 | 1, mid + 1, r, need - take_left);
  seg_pull(node);
  return ret;
}

static i64 seg_remove_large(int node, int l, int r, i64 need) {
  if (need == 0 || seg_cnt[node] == 0) return 0;
  if (need >= seg_cnt[node]) {
    i64 ret = seg_sum[node];
    seg_clear(node);
    return ret;
  }
  if (l == r) {
    seg_cnt[node] -= need;
    i64 dec = (i64)g_vals[l - 1] * need;
    seg_sum[node] -= dec;
    return dec;
  }
  seg_push(node);
  int mid = (l + r) >> 1;
  i64 take_right = seg_cnt[node << 1 | 1] < need ? seg_cnt[node << 1 | 1] : need;
  i64 ret = seg_remove_large(node << 1 | 1, mid + 1, r, take_right);
  ret += seg_remove_large(node << 1, l, mid, need - take_right);
  seg_pull(node);
  return ret;
}

int main(void) {
  int T = next_int();
  while (T--) {
    int N = next_int();
    i64 K = next_int();

    int *a = (int *)malloc((size_t)N * sizeof(int));
    int *b = (int *)malloc((size_t)N * sizeof(int));
    int *c = (int *)malloc((size_t)N * sizeof(int));
    int *d = (int *)malloc((size_t)N * sizeof(int));
    int *vals = (int *)malloc((size_t)(2 * N) * sizeof(int));

    for (int i = 0; i < N; ++i) {
      a[i] = next_int();
      vals[i] = a[i];
    }
    for (int i = 0; i < N; ++i) b[i] = next_int();
    for (int i = 0; i < N; ++i) {
      c[i] = next_int();
      vals[N + i] = c[i];
    }
    for (int i = 0; i < N; ++i) d[i] = next_int();

    qsort(vals, (size_t)(2 * N), sizeof(int), cmp_int);
    int m = 0;
    for (int i = 0; i < 2 * N; ++i) {
      if (i == 0 || vals[i] != vals[i - 1]) {
        vals[m++] = vals[i];
      }
    }

    int *aid = (int *)malloc((size_t)N * sizeof(int));
    int *cid = (int *)malloc((size_t)N * sizeof(int));
    for (int i = 0; i < N; ++i) {
      aid[i] = lower_bound_int(vals, m, a[i]) + 1;
      cid[i] = lower_bound_int(vals, m, c[i]) + 1;
    }

    g_vals = vals;
    seg_cnt = (i64 *)calloc((size_t)(m * 4 + 5), sizeof(i64));
    seg_sum = (i64 *)calloc((size_t)(m * 4 + 5), sizeof(i64));
    seg_lazy = (unsigned char *)calloc((size_t)(m * 4 + 5), sizeof(unsigned char));

    i64 total = 0;
    i64 profit = 0;

    for (int i = N - 1; i >= 0; --i) {
      if (d[i] > 0) {
        seg_add_point(1, 1, m, cid[i], d[i]);
        total += d[i];
      }

      i64 profitable = total - seg_query_prefix_count(1, 1, m, aid[i]);
      i64 take = b[i] < profitable ? b[i] : profitable;
      if (take > 0) {
        i64 removed = seg_remove_large(1, 1, m, take);
        profit += removed - (i64)a[i] * take;
        seg_add_point(1, 1, m, aid[i], take);
      }

      i64 excess = total - K;
      if (excess > 0) {
        seg_remove_small(1, 1, m, excess);
        total -= excess;
      }
    }

    printf("%lld\n", profit);

    free(seg_lazy);
    free(seg_sum);
    free(seg_cnt);
    free(cid);
    free(aid);
    free(vals);
    free(d);
    free(c);
    free(b);
    free(a);
  }

  return 0;
}