102711: [AtCoder]ABC271 B - Maintain Multiple Sequences
Description
Score : $200$ points
Problem Statement
There are $N$ sequences of integers.
The $i$-th $(1 \leq i \leq N)$ sequence has $L_i$ terms; the $j$-th $(1 \leq j \leq L_i)$ term of the $i$-th sequence is $a_{i, j}$.
You are given $Q$ queries. For the $k$-th $(1 \leq k \leq Q)$ query, given integers $s_k$ and $t_k$, find the $t_k$-th term of the $s_k$-th sequence.
Constraints
- $1 \leq N, Q \leq 2 \times 10^5$
- $L_i \geq 1 \, (1 \leq i \leq N)$
- $\sum_{i=1}^N L_i \leq 2 \times 10^5$
- $1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)$
- $1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $Q$
$L_1$ $a_{1, 1}$ $\ldots$ $a_{1, L_1}$
$\vdots$
$L_N$ $a_{N, 1}$ $\ldots$ $a_{N, L_N}$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$
Output
Print $Q$ lines. The $k$-th $(1 \leq k \leq Q)$ line should contain the answer to the $k$-th query.
Sample Input 1
2 2 3 1 4 7 2 5 9 1 3 2 1
Sample Output 1
7 5
The $1$-st sequence is $(1, 4, 7)$ and the $2$-nd is $(5, 9)$.
The answer to each query is as follows:
- The $3$-rd term of the $1$-st sequence is $7$.
- The $1$-st term of the $2$-nd sequence is $5$.
Sample Input 2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
Sample Output 2
128 1 26535 901
Input
题意翻译
有 $N$ 个数列，第 $i$ 个数列有 $L_i$ 个整数。 有 $Q$ 组询问，每组询问给定两个整数 $s_i$ 和 $t_i$，输出第 $s_i$ 个数列的第 $t_i$ 个元素。Output
问题描述
有N个整数序列。
第i个(1≤i≤N)序列有Li项；第i个序列的第j个(1≤j≤Li)项是ai, j。
给你Q个查询。对于第k个(1≤k≤Q)查询，给定整数sk和tk，找出第sk个序列的第tk项。
约束条件
- 1≤N，Q≤2×105
- Li≥1(1≤i≤N)
- ∑i=1NLi≤2×105
- 1≤ai, j≤109(1≤i≤N, 1≤j≤Li)
- 1≤sk≤N，1≤tk≤Lsk(1≤k≤Q)
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $Q$
$L_1$ $a_{1, 1}$ $\ldots$ $a_{1, L_1}$
$\vdots$
$L_N$ $a_{N, 1}$ $\ldots$ $a_{N, L_N}$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$
输出
打印Q行。第k个(1≤k≤Q)行应包含第k个查询的答案。
样例输入1
2 2 3 1 4 7 2 5 9 1 3 2 1
样例输出1
7 5
第1个序列是(1, 4, 7)，第2个是(5, 9)。
每个查询的答案如下：
- 第1个序列的第3项是7。
- 第2个序列的第1项是5。
样例输入2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
样例输出2
128 1 26535 901