← 返回题目列表

AtCoder · abc314_g

G. 护身符

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

有 N 山洞里的怪物:怪物 1,怪物 2, \ldots,怪物 N。每个怪物都有一个正整数 攻击力 和 黑板上写着 类型 由介于之间的整数表示 1 和 M,包括在内。 具体来说,对于 i = 1, 2, \ldots, N,怪物的攻击力和类型 i 是 A_i 和 B_i。

高桥将与一个人一起在这个洞穴里冒险 健康 of H 和一些 M 护身符:护身符 1,护身符 2, \ldots,护身符 M.

在冒险中,高桥执行以下步骤: i = 1, 2, \ldots, N 按此顺序(只要他的生命值不下降到 0 或以下)。

  • 如果高桥没有带护身符 B_i 和他一起,怪物 i 会攻击他并降低他的生命值 A_i.
  • 然后,
    • 如果他的生命值大于 0,他打败了怪物 i;
    • 否则,他在没有击败怪物的情况下就死了 i 并结束了他的冒险。

解决以下每个问题 K = 0, 1, \ldots, M 独立。

找出高桥选择时可以击败的最大怪物数量 K 的 M 带来冒险的护身符。

约束保证至少有一个类型的怪物 i 对于每个 i = 1, 2, \ldots, M.

约束

  • 1 \leq M \leq N \leq 3 \times 10^5
  • 1 \leq H \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq M
  • 对于每个 1 \leq i \leq M,有 1 \leq j \leq N 这样 B_j = i.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M H
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

对于每个 i = 0, 1, 2, \ldots, M,让 X_i 是高桥可以击败的最大怪物数量 K = i。 打印 X_0, X_1, \ldots, X_M 以空格分隔,格式如下:

X_0 X_1 \ldots X_M

样本输入 1

7 3 7
3 2
1 1
4 2
1 2
5 1
9 3
2 3

示例输出 1

2 5 7 7

考虑这种情况 K = 1。在这里,高桥可以带护身符 2 击败尽可能多的怪物,即 5。 冒险的进行如下。

  • 对于 i = 1,他躲避了怪物的攻击 1 因为他有护身符 2。然后,他打败了怪物 1.
  • 对于 i = 2,他受到怪物的攻击 2 他的健康状况变得 6 因为他没有护身符 1。然后,他打败了怪物 2.
  • 对于 i = 3,他躲避了怪物的攻击 3 因为他有护身符 2。然后,他打败了怪物 3.
  • 对于 i = 4,他躲避了怪物的攻击 4 因为他有护身符 2。然后,他打败了怪物 4.
  • 对于 i = 5,他受到怪物的攻击 5 他的健康状况变得 1 因为他没有护身符 1。然后,他打败了怪物 5.
  • 对于 i = 6,他受到怪物的攻击 6 他的健康状况变得 -8 因为他没有护身符 3。然后,他没有打败怪物就死了 6 并结束了他的冒险。

同样,当 K=0,他可以击败 2 怪物;当 K=2,他可以打败一切 7 怪物通过携带护身符 2 和 3;当 K=3,他可以打败一切 7 怪物通过携带护身符 1, 2,和 3.


示例输入 2

15 5 400
29 5
27 4
79 1
27 2
30 3
4 1
89 2
88 3
75 5
3 1
39 4
12 1
62 4
38 2
49 1

示例输出 2

8 12 15 15 15 15