分数: 6 点
警告
2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
一些公司食堂的菜单是基于 D天周期。它的菜品用整数表示,它提供Dish C_i 当天 i, 日 i + D, 日 i + 2D,依此类推,今天是 Day 1.
的 N 使用该食堂的员工对食物很讲究,并且员工 j 爱菜 K_j。每个员工总是在最喜欢的菜肴上桌的那一天使用自助餐厅并享用。在其他日子里,员工只有在他/她使用自助餐厅的最后一天是 L 天前。但是,如果是第一次使用(如下所述),则不适用上述规定。
对于每个整数 1 \leq j \leq N,回答以下问题:
- 假设该员工 j 当天使用自助餐厅 F_j 第一次。 (仅限这一天,即使提供的菜肴不是他/她最喜欢的菜,他/她也会使用它。此外,假设他/她在这一天之前不能使用自助餐厅,即使提供了他/她最喜欢的菜。) 找出员工的次数 j 得到最喜欢的菜肴,直到他/她使用自助餐厅 T_j 次。
约束
- 1 \leq N \leq 10^5
- 1 \leq D \leq 10^5
- 1 \leq L \leq 10^9
- 1 \leq C_i, K_j \leq 10^5
- 1 \leq F_j \leq D
- 1 \leq T_j \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
D L N C_1 C_2 \cdots C_D K_1 F_1 T_1 K_2 F_2 T_2 : K_N F_N T_N
输出
打印 N 行。的 j- 第行应包含 Employee 的次数 j 得到最喜欢的菜。
示例输入 1
4 2 3 2 3 1 3 1 2 2 3 3 1 3 4 3
示例输出 1
1 0 3
自助餐厅提供的菜肴有 4天周期: \{ 2, 3, 1, 3 \}.
- 员工 1 爱菜 1。他先吃菜 3 当天 2,然后吃 Dish 1 当天 3。因此,他得到了一次他最喜欢的菜,我们应该打印 1.
- 员工 2 爱菜 3。他吃菜 1 当天 3,就是这样。因此,他吃他最喜欢的菜的次数为零,我们应该打印 0.
- 员工 3 爱菜 3。他先吃菜 3 当天 4,然后吃 Dish 3 当天 6,然后吃 Dish 3 当天 8。因此,我们应该打印 3.
示例输入 2
3 1 3 1 1 1 2 1 3 1 2 3 1 3 3
示例输出 2
0 3 3
食堂提供菜品 1 每天。
- 员工 1 爱菜 2。他先吃菜 1 当天 1,然后也吃Dish 1 当天 2 和 3 自从 L = 1。自助餐厅从来不提供他最喜欢的食物,所以我们应该打印 0.
- 员工 2 和 3 爱菜 1,他们每天都会得到他们最喜欢的,所以我们应该打印 3 对于他们每个人。
示例输入 3
10 4 4 4 4 4 3 1 1 5 2 2 1 2 5 2 2 9 10 2 3 3 2 7 13
示例输出 3
1 5 1 6