代码

#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;

static ll varr[200005];
static ll cnta[200005];
static ll suba[200005];
static ll dla[200005];
static int idx[200005];
static int idxtmp[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){
  while (*p < '0') ++p;
  ll x = 0;
  do { x = x*10 + (*p - '0'); ++p; } while (*p >= '0');
  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: sort idx[0..n-1] ascending by varr[idx[i]] (31-bit value), 2 passes of 16 bits
static void radix_idx(int n){
  int* src = idx; int* dst = idxtmp;
  for (int shift = 0; shift < 32; shift += 16) {
    memset(cnt16, 0, sizeof(cnt16));
    for (int i = 0; i < n; i++) cnt16[(varr[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++) { int x = src[i]; dst[cnt16[(varr[x] >> shift) & 0xFFFF]++] = x; }
    int* t = src; src = dst; dst = t;
  }
  if (src != idx) memcpy(idx, src, (size_t)n * 4);
}

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;
  int allx0 = 1;
  for (int i = 0; i < n; i++) {
    ll a = rd(p), s = rd(p), c = rd(p), x = rd(p);
    if (x != 0) allx0 = 0;
    varr[ng] = a + s; cnta[ng] = 1; suba[ng] = 0; dla[ng] = (x == 0) ? 1000000000000LL : ((c - 1) / x + 1); ng++;
    if (c - 1 > 0) {
      varr[ng] = a; cnta[ng] = c - 1; suba[ng] = x; dla[ng] = (x == 0) ? 1000000000000LL : ((c - 2) / x + 1); 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++) idx[i] = i;
  radix_idx(ng);

  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;

  if (allx0) {
    ll cap = (ll)P * (ll)M;
    for (int gi = ng - 1; gi >= 0 && sold < cap; gi--) {
      int ii = idx[gi];
      ll w = varr[ii], cnt = cnta[ii];
      ll rem = cap - sold;
      ll take = cnt < rem ? cnt : rem;
      ll t0 = total;
      ll* ap = ans + sold + 1;
      ll cur = t0 + w;
      for (ll j = 0; j < take; j++) { *ap++ = cur; cur += w; }
      sold += take;
      total = t0 + take * w;
    }
  } else {
    for (int i = 0; i <= P; i++) { fa[i] = i; daycnt[i] = 0; }
    for (int gi = ng - 1; gi >= 0; gi--) {
      int ii = idx[gi];
      ll w = varr[ii], cnt = cnta[ii], sub = suba[ii], dl = dla[ii];
      if (dl > P) dl = P;
      if (dl <= 0) continue;
      int fd = findf((int)dl);
      ll ssum = sub ? (ll)(fd - 1) * sub : 0;
      ll r = cnt - ssum;
      while (fd && r > 0) {
        int capd = M - daycnt[fd];
        ll mn = capd < r ? (ll)capd : r;
        ll s0 = sold, t0 = total;
        ll* ap = ans + s0 + 1;
        ll cur = t0 + w;
        for (ll j = 0; j < mn; j++) { *ap++ = cur; cur += w; }
        daycnt[fd] += (int)mn;
        sold = s0 + mn;
        total = t0 + mn * w;
        r -= mn;
        if (daycnt[fd] == M) { fa[fd] = findf(fd - 1); }
        int pidx = fd;
        fd = findf(fd - 1);
        int skipped = pidx - fd;
        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;
}

评测结果