Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 271 B問題 Maintain Multiple Sequences

AtCoder ABC271 ABC B問題 200 pts

問題

提出解答

問題の概要

$N$ 項の整数列の列 $A=(A_1, \dots, A_N)$ がある. ここで, 第 $i$ 項目は長さ $L_i$ の整数列であり, $A_i=(a_{i,1}, \dots, a_{i, L_i})$ である.

次の $Q$ 個の質問に答えよ.

問 $q$ : $A$ の第 $s_q$ 項目の整数列の第 $t_q$ 項目は何か?

制約

$1 \leq N,Q \leq 2 \times 10^5$
$L_i \geq 1$
$\displaystyle \sum_{i=1}^N L_i \leq 2 \times 10^5$
$1 \leq a_{i,j} \leq 10^9$
$1 \leq s_q \leq N, 1 \leq t_q \leq L_{s_q}$

解法

入力で与えられる整数列を各項に持つ列をデータ構造として持てれば良い. これには例えば C++ ならば vector の vector, Python (Pypy) ならば list の list で実現できる.

なお, 大抵の言語では何かしらの工夫をしない限り, 出力すべきは ${\tt A[s-1] [t-1]}$ になることに注意.