/ 
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
高橋君のスーパーマーケットには陳列棚があります。 この陳列棚には商品を並べられる列が N 本あり、それぞれの列には 1,2,\ldots,N の番号がついています。 列 i には K_i 個の商品が手前から奥へと一列に並べられており、手前から j 番目の商品の消費期限は T_{i,j} です。
ここで、全ての商品の消費期限は相異なることが保証されます。
M 人の客が順番にやってきます。 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 行目では 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 番手前にある商品の消費期限は列 1 が 1、列 2 が 20 です。これらのうち値が最大である 20 の商品を 1 番目にやってきた客は購入します。
- 現在、棚の 1 番手前にある商品の消費期限は列 1 が 1、列 2 が 30 です。これらのうち値が最大である 30 の商品を 2 番目にやってきた客は購入します。
- 現在、棚の 1 番手前にある商品の消費期限は列 1 が 1、列 2 が 40 です。これらのうち値が最大である 40 の商品を 3 番目にやってきた客は購入します。
- 現在、棚の 1 番手前にある商品の消費期限は列 1 が 1、列 2 が 50 です。棚の 2 番目に手前にある商品の消費期限は列 1 が 200、列 2 が 2 です。これらのうち値が最大である 200 の商品を 4 番目にやってきた客は購入します。
- 現在、棚の 1 番手前にある商品の消費期限は列 1 が 1、列 2 が 50 です。棚の 2 番目に手前にある商品の消費期限は列 1 が 1000、列 2 が 2 です。これらのうち値が最大である 1000 の商品を 5 番目にやってきた客は購入します。
入力例 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
Score : 6 points
Warning
Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Takahashi's grocery store has a display rack. The rack has N sections numbered 1 to N, each of which contains a queue of products. In Section i, K_i products line up from front to back, and the expiry date of the j-th product from the front is T_{i,j}.
Here, it is guaranteed that all the products have distinct expiry dates.
M customers will visit the store one by one. The i-th customer will check the frontmost a_i products for every section. (If a section has less than a_i products, he/she will check all those products.) Then, he/she will pick up the product with the greatest value of the expiry date among the products checked, and buy it.
For each of the customers, find the expiry date of the product he/she will buy.
Constraints
- All values in input are integers.
- 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} are distinct.
- 1 \leq a_i \leq 2
Input
Input is given from Standard Input in the following format:
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
Output
Print M lines. The i-th line should contain the expiry date of the product he/she will buy.
Sample Input 1
2 3 1 200 1000 5 20 30 40 50 2 5 1 1 1 2 2
Sample Output 1
20 30 40 200 1000
- The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 20, respectively. Among them, 20 is greater, so the first customer will buy that product.
- The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 30, respectively. Among them, 30 is greater, so the second customer will buy that product.
- The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 40, respectively. Among them, 40 is greater, so the third customer will buy that product.
- The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 50, respectively, and the expiry dates of the second frontmost products in Section 1 and 2 are now 200 and 2, respectively. Among these values, 200 is the greatest, so the fourth customer will buy that product.
- The expiry dates of the frontmost products in Section 1 and 2 are now 1 and 50, respectively, and the expiry dates of the second frontmost products in Section 1 and 2 are now 1000 and 2, respectively. Among these values, 1000 is the greatest, so the fifth customer will buy that product.
Sample Input 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
Sample Output 2
100 88 72 65 93 77 68 63 50 90 64 91 49 46 44 96 37 31 62 20