534 「LibreOJ Round #6」花团

内存限制:256 MB 时间限制:3000 ms

题目描述

「Alice —— !」「Karen —— !」

Alice 和 Karen 家边的大花坛给了她们无尽的欢乐。

这天 Karen 想重新规划一下花坛在一年里的外观。但是由于花朵各有其花期,而且花市上的选择实在太多了,所以她把问题进行了一些抽象,希望擅长程序设计的你可以为她解决。

物品集合 $S$ 初始为空,按时间递增顺序依次给出 $q$ 次操作,操作如下:

  • $\texttt{1 v w e}$ 表示在 $S$ 中加入一个体积为 $v$ 价值为 $w$ 的物品,第 $e$ 次操作结束之后移除该物品。
  • $\texttt{2 v}$ 表示询问。你需要回答:
    1. 当前 $S$ 是否存在一个子集使得子集中物品体积和为 $v$。
    2. 当前 $S$ 的所有物品体积和为 $v$ 的子集中,价值和最大是多少(空集的价值和为 0)。

输入格式

第一行三个正整数 $q,\text{maxv},T$ 表示操作数、最大可能的 $v$、及是否强制在线。

接下来 $q$ 行每行描述一个操作。
设修正值 $d=T\times \text{lastans}$。这里 $\text{lastans}$ 表示上次询问的两个答案的异或和,若没有上次询问则 $\text{lastans}=0$。
则第 $i$ 行中,第一个整数 $\text{op}$ 表示操作类型;
若操作类型为 $1$,则接下来三个整数 $v',w',e'$ 表示加入一个体积为 $v_i=v'-d$,价值为 $w_i=w'-d$,在第 $e_i=e'-d$ 时间后被移除的物品;
若操作类型为 $2$,则接下来一个整数 $v'$ 表示询问 $v_i=v'-d$。
一行中相邻整数以单个空格分隔。

输出格式

对于每个询问($2$ 类型的操作)输出一行两个整数 $e$ 和 $\text{maxw}$,由空格分隔。

若不存在这样的子集,$e=\text{maxw}=0$;
否则 $e=1$,$\text{maxw}$ 为最大的价值和。

样例 1

样例 2

数据范围与提示

对于所有数据,$1\le q\le 15000,1\le v_i\le \text{maxv}\le 15000,0\le w_i\le 15000,i\le e_i\le q$。

对于每个测试点,若问题 1 回答全对,则得 $40\%$ 的分数;若问题 2 回答全对,则另得 $60\%$ 的分数。每个子任务的得分是其中各测试点的最小值。
注意,即使你只回答了一个问题,每次仍要输出两个整数,以免答案错位。

Subtask # 分值 $q,v$ 的限制 $T$ 的限制
1 $15$ $q\le 18,v\le 15000$ $T=0$
2 $20$ $q,v\le 1000$ $T\in{0,1}$
3 $20$ $q,v\le 6000$ $T=0$
4 $20$ $q,v\le 10000$ $T=0$
5 $25$ $q,v\le 15000$ $T\in{0,1}$

样例

样例输入 1

12 10 0 1 1 1 12 1 6 0 12 1 10 7 8 1 3 8 7 2 6 2 9 2 10 2 10 2 10 1 3 2 11 2 4 2 4

样例输出 1

1 0 1 8 1 9 1 7 0 0 1 3 0 0

样例输入 2

19 20 1 1 2 19 11 2 2 1 27 27 22 1 20 34 36 2 29 1 9 8 9 1 5 19 8 1 1 15 19 2 3 1 36 40 54 1 37 50 52 2 40 2 62 1 1 17 16 1 1 7 16 1 13 16 18 1 9 11 19 2 10 2 34

样例输出 2

1 19 0 0 1 34 1 46 0 0 1 26 0 0