← 返回题目列表

AtCoder · past202005_l

L. 超级市场

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

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

高桥的杂货店有一个展示架。 这个架子有 N 个编号为 1 to N的区域,每个区域都有一排产品。 在第 i, K_i 产品从前到后排列,第 j个产品的到期日期是 T_{i,j}.

。这里保证所有产品的到期日期各不相同。

M 位顾客将会一个接一个地光顾商店。第 i位顾客将会查看最前面的产品 a_i 每个部分的产品。(如果某个部分的产品少于 a_i 个,他/她将检查所有这些产品。) 然后,他/她将从检查过的产品中选出保质期最长的产品并购买。

对于每位顾客,找出他/她将购买的产品的保质期。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq K_i \leq 10^5
  • 1 \leq M \leq \sum_{i=1}^{N}K_i \leq 3 \times 10^5
  • 1 \leq T_{i,j} \leq 10^9
  • T_{i,j} 是不同的。
  • 1 \leq a_i \leq 2

输入

输入由标准输入按以下格式给出:

N
K_1 T_{1,1} T_{1,2} \cdots T_{1,K_1}
\vdots
K_N T_{N,1} T_{N,2} \cdots T_{N,K_N}
M
a_1 a_2 \cdots a_M

输出

打印 M 行。的 i第 - 行应包含他/她将购买的产品的保质期。


示例输入 1

2
3 1 200 1000
5 20 30 40 50 2
5
1 1 1 2 2

示例输出 1

20
30
40
200
1000
  • 各部分最前面的产品的保质期 1 和 2 现在 1 和 20。在其中, 20 更大,所以第一个顾客会购买该产品。
  • 各部分最前面的产品的保质期 1 和 2 现在 1 和 30。在其中, 30 更大,所以第二个顾客会购买该产品。
  • 各部分最前面的产品的保质期 1 和 2 现在 1 和 40。在其中, 40 更大,所以第三个顾客会购买该产品。
  • 各部分最前面的产品的保质期 1 和 2 现在 1 和 50,分别为,以及该区第二排最前产品的到期日期 1 和 2 现在 200 和 2,分别为。在这些值中, 200 最大,所以第四个顾客会购买该产品。
  • 各部分最前面的产品的保质期 1 和 2 现在 1 和 50,分别为,以及该区第二排最前产品的到期日期 1 和 2 现在 1000 和 2,分别为。在这些值中, 1000 最大,所以第五个顾客会购买该产品。

示例输入 2

10
6 8 24 47 29 73 13
1 4
5 72 15 68 49 16
5 65 20 93 64 91
6 100 88 63 50 90 44
2 6 1
10 14 2 76 28 21 78 43 11 97 70
5 31 9 62 84 40
8 10 46 96 23 98 19 38 51
2 37 77
20
1 1 1 1 2 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1

示例输出 2

100
88
72
65
93
77
68
63
50
90
64
91
49
46
44
96
37
31
62
20