#534. 「LibreOJ Round #6」花团

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: liu_cheng_ao

题目描述

「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

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

数据范围与提示

对于所有数据, 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 q,v\le 6000 T=0
4 q,v\le 10000
5 25 q,v\le 15000 T\in\{0,1\}