CF1765L Project Manager
题目描述
B公司有 $ n $ 名员工,编号从 $ 1 $ 到 $ n $ 。每个员工每周都有工作日和休息日。给定每个员工的工作日列表。工作日分为正常工作日和假日。在正常工作日,只有那些在当天工作日列表中的员工才工作。
在假日中,没有人工作。给定一组假日列表。第一天从星期一开始,编号为 1 。公司收到了 $ k $ 个项目的投标,需要完成这些项目。这些项目按照优先级从高到低编号为从 1 到 $ k $ 。每个项目由多个部分组成,第 $ i $ 部分必须由第 $ a_i $ 名员工完成。各个部分必须按顺序完成(即只有在第 $ i $ 部分完成后,才能开始完成第 $ i+1 $ 部分)。每个部分需要相应的员工花费一天的时间来完成。项目可以同时进行。
然而,每个员工在一天内只能完成一个项目的一部分。如果他们有多个项目可以选择完成一部分,他们总是优先选择优先级最高(索引最小)的项目。对于每个项目,输出该项目完成的天数。
输入格式
第一行包含三个整数 $ n, m $ 和 $ k $表示员工数量、假日数量和项目数量( $ 1 \le n, m, k \le 2 \cdot 10^5 $ )
接下来的 $ n $ 行中,第 $ i $ 行包含第 $ i $ 名员工的工作日列表。首先是一个整数 $ t $表示 工作日数量( $ 1 \le t \le 7 $ ) 然后按递增顺序列出 $ t $ 个工作日。工作日可能是: “Monday”,“Tuesday”,Wednesday”, “Thursday”, “Friday”, “Saturday”, Sunday”。
接下来一行包含 $ m $ 个整数 $ h_1, h_2, \dots, h_m $表示假日列表 ( $ 1 \le h_1 < h_2 < \dots < h_m \le 10^9 $ )
最后的 $ k $ 行中,第 $ j $ 行描述第 $ j $ 个项目。首先是一个整数 $ p $表示项目的部分数量 ( $ 1 \le p \le 2 \cdot 10^5 $ )。然后给出长度为$ p $ 的数组 $ a_1, a_2, \dots, a_p $ ( $ 1 \le a_x \le n $ ) ,其中 $ p_i $ 是完成第 $ i $ 部分的员工的索引。
所有项目的总部分数量不超过 $ 2 \cdot 10^5 $ 。
输出格式
输出 $ k $ 个整数,第 $ j $ 个整数表示第 $ j $ 个项目完成的天数