代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned long long u64;
typedef long long i64;

enum { MAXN = 100005, MAXP = 100005, MAXSLOT = 1000005 };

typedef struct {
    unsigned value;
    unsigned id_type;
} Event;

static unsigned va[MAXN], bonus[MAXN], total[MAXN], decay[MAXN];
static unsigned query_day[MAXP];
static Event event_a[MAXN * 2], event_b[MAXN * 2];
static unsigned radix_count[65536];
static int parent_[MAXSLOT];
static i64 answer[MAXP];

static __attribute__((always_inline)) inline int find_slot(int x) {
    int r = x;
    while (parent_[r] != r) r = parent_[r];
    while (parent_[x] != x) {
        int y = parent_[x];
        parent_[x] = r;
        x = y;
    }
    return r;
}

static void radix_sort(Event *a, Event *b, int n) {
    for (int pass = 0; pass < 2; ++pass) {
        unsigned shift = pass << 4;
        for (int i = 0; i < 65536; ++i) radix_count[i] = 0;
        for (int i = 0; i < n; ++i) ++radix_count[(a[i].value >> shift) & 65535];
        unsigned sum = 0;
        for (int i = 0; i < 65536; ++i) {
            unsigned x = radix_count[i];
            radix_count[i] = sum;
            sum += x;
        }
        for (int i = 0; i < n; ++i)
            b[radix_count[(a[i].value >> shift) & 65535]++] = a[i];
        Event *t = a; a = b; b = t;
    }
}

static void solve(DuckInfo *info) {
    const char *p = info->stdin_ptr;
    unsigned n = duck_read_u64(&p);
    unsigned per_day = duck_read_u64(&p);
    unsigned qn = duck_read_u64(&p);
    for (unsigned i = 0; i < n; ++i) {
        va[i] = duck_read_u64(&p);
        bonus[i] = duck_read_u64(&p);
        total[i] = duck_read_u64(&p);
        decay[i] = duck_read_u64(&p);
    }
    unsigned max_day = 0;
    for (unsigned i = 0; i < qn; ++i) {
        query_day[i] = duck_read_u64(&p);
        if (query_day[i] > max_day) max_day = query_day[i];
    }

    int ne = 0;
    for (unsigned i = 0; i < n; ++i) {
        event_a[ne++] = (Event){va[i] + bonus[i], (i << 1) | 1};
        if (total[i] > 1) event_a[ne++] = (Event){va[i], i << 1};
    }
    radix_sort(event_a, event_b, ne);

    unsigned cap = max_day * per_day;
    for (unsigned i = 0; i <= cap; ++i) parent_[i] = i;
    unsigned used = 0;
    i64 sum = 0;
    for (int ei = ne - 1; ei >= 0 && used < cap; --ei) {
        Event ev = event_a[ei];
        unsigned id = ev.id_type >> 1;
        unsigned d;
        if (decay[id]) {
            d = (total[id] + decay[id] - 1) / decay[id];
            if (d > max_day) d = max_day;
        } else d = max_day;

        if (ev.id_type & 1) {
            int slot = find_slot((int)(d * per_day));
            if (slot) {
                parent_[slot] = find_slot(slot - 1);
                ++used;
                sum += ev.value;
                if (!(used % per_day)) answer[used / per_day] = sum;
            }
            continue;
        }

        u64 remain;
        if (!decay[id]) {
            remain = total[id] - 1;
        } else {
            u64 before = (u64)(d - 1) * decay[id];
            remain = total[id] > before ? total[id] - before - 1 : 0;
        }
        for (;;) {
            while (remain) {
                int slot = find_slot((int)(d * per_day));
                if (!slot) goto regular_done;
                parent_[slot] = find_slot(slot - 1);
                --remain;
                ++used;
                sum += ev.value;
                if (!(used % per_day)) answer[used / per_day] = sum;
                if (used == cap) goto all_done;
            }
            if (!decay[id] || d == 1) break;
            --d;
            remain = decay[id];
        }
regular_done:;
    }
all_done:
    {
        unsigned full = used / per_day;
        if (used % per_day) answer[full + 1] = sum;
        for (unsigned d = full + 1 + (used % per_day != 0); d <= max_day; ++d)
            answer[d] = sum;
    }

    char *out = info->stdout_ptr;
    for (unsigned i = 0; i < qn; ++i) {
        out = duck_write_i64(out, answer[query_day[i]]);
        *out++ = '\n';
    }
    info->stdout_size = out - info->stdout_ptr;
}

#ifdef LOCAL
#include <stdio.h>
int main(void) {
    static char in[4000000], out[2000000];
    DuckInfo info = {0};
    info.stdin_size = fread(in, 1, sizeof in, stdin);
    info.stdin_ptr = in;
    info.stdout_ptr = out;
    solve(&info);
    fwrite(out, 1, info.stdout_size, stdout);
}
#else
__attribute__((noreturn)) void __libc_start_main(void *x, long n, char **v) {
    DuckInfo *info = duck_info(n, v);
    solve(info);
    duck_exit();
}
int main(void) {}
#endif

评测结果