#P15863. [Roi2026]火星背包

    ID: 15074 传统题 1000ms 1024MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-按位贪心整体二分单调判定增量维护

[Roi2026]火星背包

题目描述

火星人马文正在整理背包。面前有 nn 个物品,编号为 11 到 nn。每个物品有两个属性:

  • 第 ii 个物品的奇异度为 wiw_i;
  • 第 ii 个物品的价值为 cic_i。

奇异度是一个非负整数,其二进制表示不超过 kk 位,即

0≤wi<2k。0\le w_i<2^k。

价值也是非负整数,且

0≤ci≤109。0\le c_i\le 10^9。

一个物品集合的总价值定义为其中物品价值之和;总奇异度定义为其中所有物品奇异度的按位或(bitwise OR)。

马文称一个物品集合是有价值的,如果它的总价值不小于 CC。

对于每个 i=1,2,…,ni=1,2,\ldots,n,马文想从编号不超过 ii 的物品中选择一个有价值的集合,并使这个集合的总奇异度尽可能小。

请对每个前缀分别求出这个最小总奇异度。

按位或定义如下:考虑若干整数的二进制表示,结果的第 jj 位为 11 当且仅当至少有一个数的第 jj 位为 11。在常见程序语言中,这个运算通常写作 |。例如

$$(10\mid 3\mid 9)=(1010_2\mid 0011_2\mid 1001_2)=1011_2=11。$$

输入格式

第一行包含三个整数 n,k,Cn,k,C:

$$1\le n\le 2\,000\,000, \qquad 1\le k\le 22, \qquad 1\le C\le 10^{15}。$$

接下来 nn 行,每行包含两个整数 wi,ciw_i,c_i:

0≤wi<2k,0≤ci≤109。0\le w_i<2^k, \qquad 0\le c_i\le 10^9。

输出格式

输出 nn 个数。第 ii 个数应等于在前 ii 个物品中选出有价值集合时,可能达到的最小总奇异度。

如果前 ii 个物品中不存在有价值集合,则输出 −1-1。

样例

5 4 12
8 7
2 6
3 6
1 12
3 5
-1
10
3
1
1

样例说明

对于 i=1i=1,只有一个物品,奇异度为 88、价值为 77,无法选出总价值至少为 1212 的集合,所以答案为 −1-1。

对于 i=2i=2,唯一有价值的选择是取两个物品,总奇异度为 8∣2=108\mid 2=10。

对于 i=3i=3,任意两个或更多物品的集合都是有价值的,最优选择是第二、三个物品,总奇异度为 2∣3=32\mid 3=3。

对于 i=4i=4,可以只选第四个物品,它的价值已经足够,奇异度为 11,这是可能的最小值。对于 i=5i=5,仍然可以选择第四个物品,因此答案也是 11。

子任务与评分

子任务 分值 附加限制 必要子任务
1 10 n≤20, k≤10n\le 20,\ k\le 10 样例
2 11 n≤100, k≤10n\le 100,\ k\le 10 样例,1
3 14 n≤50 000, k≤10n\le 50\,000,\ k\le 10 样例,1-2
4 13 n≤1 000 000, k≤19n\le 1\,000\,000,\ k\le 19,所有 wiw_i 都是二的幂 -
5 11 n≤2000n\le 2000 样例,1-2
6 18 n≤500 000, k≤16n\le 500\,000,\ k\le 16 样例,1-3
7 6 n≤1 000 000, k≤19n\le 1\,000\,000,\ k\le 19 样例,1-4,6
8 k≤19k\le 19 样例,1-4,6-7
9 11 无 样例,1-8

评测说明

每个子任务内的全部测试点通过后,才能获得该子任务的分数;还需通过表中列出的必要子任务。「样例」或「题面测试」指子任务 0。