← 返回题目列表

AtCoder · past202004_m

M. 自助餐厅

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

分数: 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