LOJR6T2 花团

#include <cstdio>
#include <cstring>

#include <algorithm>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

struct lst {
    int v, w;
    lst* next;
};

struct seg {
    int l, r, lv;
    lst* d;
    seg *ls, *rs;
};

const int N = 15010, LOGN = 18;

int n, maxv, t, lastans, curx;
int dp[LOGN][N];
seg* root;

seg* build(int l, int r, int lv);
lst* create(int v, int w, lst* next);
void dfs(seg* p);
void change(seg* p, int l, int r, int v, int w);

int main() {
//  freopen("test.in", "r", stdin);
    scanf("%d%d%d", &n, &maxv, &t);
    memset(dp[0] + 1, -1, sizeof(int) * maxv);
    root = build(1, n, 1);
    dfs(root);
    return 0;
}

seg* build(int l, int r, int lv) {
    static seg pool[N << 1];
    static int cnt;
    seg* p = pool + cnt;
    ++cnt;
    p->l = l;
    p->r = r;
    p->lv = lv;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    p->ls = build(l, mid, lv + 1);
    p->rs = build(mid + 1, r, lv + 1);
    return p;
}

void dfs(seg* p) {
    int lv = p->lv;
    memcpy(dp[lv], dp[lv - 1], sizeof(int) * (maxv + 1));
    for (lst* q = p->d; q; q = q->next) {
        for (int i = maxv; i >= q->v; --i)
            if (~dp[lv][i - q->v])
                dp[lv][i] = max(dp[lv][i], dp[lv][i - q->v] + q->w);
    }
    if (p->ls) {
        dfs(p->ls);
        dfs(p->rs);
        return;
    }
    int op, v, w, e;
    scanf("%d%d", &op, &v);
    curx = p->l;
    v -= t * lastans;
    if (op == 1) {
        scanf("%d%d", &w, &e);
        LOG("#%d %d %d\n", v, w, e);
        w -= t * lastans;
        e -= t * lastans;
        change(root, curx, e, v, w);
        return;
    }
    LOG("#%d\n", v);
    if (!~dp[lv][v]) {
        puts("0 0");
        lastans = 0;
    } else {
        lastans = dp[lv][v] ^ 1;
        printf("1 %d\n", dp[lv][v]);
    }
}

void change(seg* p, int l, int r, int v, int w) {
    if (p->l == l && p->r == r) {
        p->d = create(v, w, p->d);
        if (p->l <= curx && curx <= p->r)
            for (int j = p->lv; j < LOGN; ++j)
                for (int i = maxv; i >= v; --i)
                    if (~dp[j][i - v])
                        dp[j][i] = max(dp[j][i], dp[j][i - v] + w);
        return;
    }
    if (p->ls->r >= r)
        change(p->ls, l, r, v, w);
    else if (p->rs->l <= l)
        change(p->rs, l, r, v, w);
    else {
        change(p->ls, l, p->ls->r, v, w);
        change(p->rs, p->rs->l, r, v, w);
    }
}

lst* create(int v, int w, lst* next) {
    static lst pool[N * LOGN];
    static lst* p = pool;
    ++p;
    p->v = v;
    p->w = w;
    p->next = next;
    return p;
}