代码

#include <sys/auxv.h>
#include <stdint.h>
#include <algorithm>
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 int fa[100005];
static int daycnt[100005];
static ll qry[100005];

// breakpoints: batch i starts at sold count bcnt[i] with profit bval[i], units worth bw[i]
static ll bcnt[600005];
static ll bval[600005];
static ll bw[600005];
static int nbp;

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");
}

static inline void pr_ll(char*& o, ll v){
  if (v == 0) { *o++ = '0'; return; }
  char tmp[20]; int n = 0;
  while (v) { tmp[n++] = (char)('0' + (v % 10)); v /= 10; }
  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;
  sort(key, key + ng); // ascending value

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

  ll total = 0;
  ll sold = 0;
  nbp = 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;
      bcnt[nbp] = sold; bval[nbp] = total; bw[nbp] = w; nbp++;
      daycnt[idx] += (int)mn;
      sold += mn;
      total += 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;
    if (need <= 0) { *o++ = '0'; *o++ = '\n'; continue; }
    int lo = 0, hi = nbp - 1;
    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      if (bcnt[mid] < need) lo = mid; else hi = mid - 1;
    }
    ll ans = bval[lo] + (need - bcnt[lo]) * bw[lo];
    pr_ll(o, ans);
    *o++ = '\n';
  }
  di->stdout_size = (uint64_t)(o - di->stdout_ptr);
  exitasm();
  return 0;
}

评测结果