P15258 [USACO26JAN2] Declining Invitations S

题目描述

有 $N$ 名选手参加了一场比赛，每人获得一个从 $1$ 到 $N$ 的不同排名。主办方使用 $C$ 条标准来邀请选手参加决赛，排名第 $i$ 的选手满足其中指定的 $n_i$ 条标准（$1\le n_i\le C$）。

邀请流程如下：首先，邀请满足第 $1$ 条标准且排名最高的 $f_1$ 名学生。然后，在所有尚未被邀请的选手中，邀请满足第 $2$ 条标准且排名最高的 $f_2$ 名学生（如果剩余人数少于 $f_2$，则邀请所有剩余满足条件的选手）。此过程对 $i$ 从 $1$ 到 $C$ 重复进行（$1\le f_i\le N$）。

然而，有些选手可能会拒绝参加决赛。在这种情况下，在决定邀请谁时，这些选手将被忽略。

给定一个 $1\dots N$ 的排列 $p_1, p_2, \dots, p_N$。对于每个 $i$ 从 $0$ 到 $N-1$，确定如果排名为 $p$ 的前 $i$ 个元素的选手拒绝参赛时，最终被邀请的选手的排名之和。

输入格式

第一行包含两个整数 $N$ 和 $C$（$1\le N,C\le 10^5$）。

第二行包含 $C$ 个整数 $f_1,f_2, \dots, f_C$。

第三行包含 $N$ 个整数 $p_1, \dots, p_N$。

接下来的 $N$ 行，每行首先包含一个整数 $n_i$（$1\le n_i\le C$），随后是 $n_i$ 个 $[1, C]$ 范围内互不相同的整数，表示排名第 $i$ 的选手满足的标准。保证所有 $n_i$ 之和不超过 $10^6$，即 $\sum n_i\le 10^6$。

输出格式

输出 $N$ 行，表示在每次拒绝发生前（即从 $i=0$ 到 $i=N-1$ 的情况）被邀请选手的排名之和。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

6 10
5 6 4 1 3 3 3 6 5 3
1 4 6 5 2 3
1 9
5 4 3 9 5 10
10 6 2 10 1 7 8 3 9 4 5
10 4 5 3 1 2 9 10 6 7 8
2 3 1
8 1 9 7 4 3 10 6 2

输出 #3

说明/提示

样例 1 解释

只有一条标准。每次邀请时，从尚未拒绝的选手中选择满足该标准且排名最高的三位。

样例 2 解释

初始时，第 $i$ 名选手在第 $i$ 条标准下被邀请（对于所有 $1\le i\le 4$）。

第一次拒绝后，第 $i+1$ 名选手在第 $i$ 条标准下被邀请（对于所有 $1\le i\le 4$）。

评分

输入 4-6：$N, C \le 10^3$，$\sum n_i \le 10^4$
输入 7-8：$C=1$
输入 9-10：$C=2$
输入 11-16：无额外约束。

翻译由 DeepSeek 完成

Wy Online Judge

WyOJ

#706. P15258 [USACO26JAN2] Declining Invitations S