代码

#include <sys/auxv.h>
#include <stdint.h>
#include <string.h>
using namespace std;

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

#define AT_DUCK 0x6b637564UL

typedef long long ll;
typedef unsigned long long ull;

static ll varr[200005];
static ll cnta[200005];
static ll suba[200005];
static ll dla[200005];
static ull key[200005];
static ull keytmp[200005];
static int cnt16[65536];

static int fa[100005];
static int daycnt[100005];
static ll qry[100005];
static ll ans[1000005];

static char dg4[40004];

static int P, M;

static inline ll rd(const char*& p){
  ll x = 0;
  while (*p < '0' || *p > '9') ++p;
  while (*p >= '0' && *p <= '9') { x = x*10 + (*p - '0'); ++p; }
  return x;
}

static inline int findf(int x){
  while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
  return x;
}

static inline void exitasm(){
  __asm__ __volatile__("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax","rdi","rcx","r11","memory");
}

// LSD radix sort 64-bit ascending, 4 passes of 16 bits
static void radix64(ull* a, int n){
  ull* src = a; ull* dst = keytmp;
  for (int shift = 0; shift < 64; shift += 16) {
    memset(cnt16, 0, sizeof(cnt16));
    for (int i = 0; i < n; i++) cnt16[(src[i] >> shift) & 0xFFFF]++;
    int sum = 0;
    for (int i = 0; i < 65536; i++) { int c = cnt16[i]; cnt16[i] = sum; sum += c; }
    for (int i = 0; i < n; i++) { ull x = src[i]; dst[cnt16[(x >> shift) & 0xFFFF]++] = x; }
    ull* t = src; src = dst; dst = t;
  }
  if (src != a) memcpy(a, src, (size_t)n * 8);
}

static inline void pr_ll(char*& o, ll v){
  if (v == 0) { *o++ = '0'; return; }
  char tmp[20]; int n = 0;
  while (v >= 10000) {
    int d = (int)(v % 10000);
    tmp[n++] = dg4[d*4+3]; tmp[n++] = dg4[d*4+2]; tmp[n++] = dg4[d*4+1]; tmp[n++] = dg4[d*4];
    v /= 10000;
  }
  int d = (int)v;
  if (d >= 1000) { tmp[n++] = dg4[d*4+3]; tmp[n++] = dg4[d*4+2]; tmp[n++] = dg4[d*4+1]; tmp[n++] = dg4[d*4]; }
  else if (d >= 100) { tmp[n++] = dg4[d*4+3]; tmp[n++] = dg4[d*4+2]; tmp[n++] = dg4[d*4+1]; }
  else if (d >= 10) { tmp[n++] = dg4[d*4+3]; tmp[n++] = dg4[d*4+2]; }
  else tmp[n++] = (char)('0' + d);
  while (n) *o++ = tmp[--n];
}

#ifdef DUCK_RENAME_MAIN
extern "C" int duck_solve()
#else
int main()
#endif
{
  struct DuckInfo *di = (struct DuckInfo *)getauxval(AT_DUCK);
  const char *p = di->stdin_ptr;
  int n = (int)rd(p);
  M = (int)rd(p);
  int k = (int)rd(p);

  int ng = 0;
  for (int i = 0; i < n; i++) {
    ll a = rd(p), s = rd(p), c = rd(p), x = rd(p);
    ll d1 = (x == 0) ? 1000000000000LL : ((c - 1) / x + 1);
    varr[ng] = a + s; cnta[ng] = 1; suba[ng] = 0; dla[ng] = d1; ng++;
    if (c - 1 > 0) {
      ll d2 = (x == 0) ? 1000000000000LL : ((c - 2) / x + 1);
      varr[ng] = a; cnta[ng] = c - 1; suba[ng] = x; dla[ng] = d2; ng++;
    }
  }

  P = 0;
  for (int i = 0; i < k; i++) { qry[i] = rd(p); if (qry[i] > P) P = (int)qry[i]; }

  for (int i = 0; i < ng; i++) key[i] = ((ull)varr[i] << 20) | (ull)i;
  radix64(key, ng);

  for (int i = 0; i <= P; i++) { fa[i] = i; daycnt[i] = 0; }

  // build 4-digit table
  for (int i = 0; i < 10000; i++) {
    int v = i;
    dg4[i*4+3] = (char)('0' + v % 10); v /= 10;
    dg4[i*4+2] = (char)('0' + v % 10); v /= 10;
    dg4[i*4+1] = (char)('0' + v % 10); v /= 10;
    dg4[i*4+0] = (char)('0' + v % 10);
  }

  ll total = 0;
  ll sold = 0;

  for (int gi = ng - 1; gi >= 0; gi--) {
    int ii = (int)(key[gi] & 0xFFFFF);
    ll w = varr[ii], cnt = cnta[ii], sub = suba[ii], dl = dla[ii];
    if (dl > P) dl = P;
    if (dl <= 0) continue;
    int idx = findf((int)dl);
    ll ssum = sub ? (ll)(idx - 1) * sub : 0;
    ll r = cnt - ssum;
    while (idx && r > 0) {
      int cap = M - daycnt[idx];
      ll mn = cap < r ? (ll)cap : r;
      ll s0 = sold, t0 = total;
      for (ll j = 1; j <= mn; j++) ans[s0 + j] = t0 + j * w;
      daycnt[idx] += (int)mn;
      sold = s0 + mn;
      total = t0 + mn * w;
      r -= mn;
      if (daycnt[idx] == M) { fa[idx] = findf(idx - 1); }
      int pidx = idx;
      idx = findf(idx - 1);
      int skipped = pidx - idx;
      if (sub && ssum > 0) {
        r += (ll)skipped * sub;
        ssum -= (ll)skipped * sub;
      }
    }
  }

  char *o = di->stdout_ptr;
  for (int i = 0; i < k; i++) {
    ll need = qry[i] * (ll)M;
    if (need > sold) need = sold;
    pr_ll(o, ans[need]);
    *o++ = '\n';
  }
  di->stdout_size = (uint64_t)(o - di->stdout_ptr);
  exitasm();
  return 0;
}

评测结果