P15258 [USACO26JAN2] Declining Invitations S

$N$ contestants participated in a contest, each placing a distinct rank from $1$ to $N$. There are $C$ criteria used to invite contestants to participate in the final round, and the $i$th-ranked contestant satisfies a specified $n_i$ of them ($1\le n_i\le C$). The invitation process runs as follows. First, the top $f_1$ students who satisfy the $1$st criteria will be invited. Then, out of all students who haven't yet been invited, the top $f_2$ (or all remaining if there are fewer than $f_2$ remaining) students who satisfy the $2$nd criterion will be invited. This process repeats, for each $i$ from $1$ to $C$ ($1\le f_i\le N$). However, some contestants will decline to participate in the final round, in which case they will be ignored when determining who to invite. You are given a permutation $p_1, p_2, \dots, p_N$ of $1\dots N$. For each $i$ from $0$ to $N-1$, determine the sum of the ranks of the contestants who will be invited if the participants with ranks given by the first $i$ elements of $p$ decline to attend.

The first line contains $N$ and $C$ ($1\le N,C\le 10^5$). The next line contains $f_1,f_2, \dots, f_C$. The next line contains $p_1, \dots, p_N$. The next $N$ lines each contain $n_i$ ($1\le n_i\le C$), followed by $n_i$ distinct integers in $[1, C]$, representing the criteria that the $i$th-ranked contestant satisfies. It is guaranteed that $\sum n_i\le 10^6$.

Output $N$ lines, the sum of ranks of invitees before each declination.

#### Sample 1 Explanation There is only one criterion. The top three remaining contestants who have not declined will be invited. #### Sample 2 Explanation Initially, the $i$th contestant gets invited under criterion $i$ for all $1\le i\le 4$. After the first declination, the $i+1$th contestant gets invited under criterion $i$ for all $1\le i\le 4$. SCORING: - Inputs 4-6: $N, C \le 10^3, \sum n_i \le 10^4$ - Inputs 7-8: $C=1$ - Inputs 9-10: $C=2$ - Inputs 11-16: No additional constraints.