分数: 266 分
问题陈述
高桥管理 N libraries in the city.图书馆 i (1 \leq i \leq N) has M_i genres, and each genre is numbered from 1 to M_i.
流派书籍的初始数量 j (1 \leq j \leq M_i) of library i is S_{i,j}。 It is possible for a genre to have an initial book count of 0.
One day, Aoki organized the lending records and found that there are Q 未处理的借出请求按顺序记录。 Takahashi will process these requests sequentially from the 1-st to the Q-th. The initial book counts represent the number of books at the time before processing these lending requests.
的 k第 次借出请求 (1 \leq k \leq Q) 是“借用 1 类型之书 d_k from library v_k."每个贷款请求的处理方式如下:
- If the current number of books of genre d_k in library v_k is 1 以上,贷款 成功, and the number of books of that genre decreases by 1.
- If the current number of books of genre d_k in library v_k is 0,贷款 fails, and the number of books does not change.
After processing all lending requests from the 1-st to the Q-th in order, output the remaining number of books for each genre in each library, and the number of requests that failed.
约束
- 1 \leq N \leq 1000
- 1 \leq M_i \leq 1000
- \sum_{i=1}^{N} M_i \leq 10^5
- 0 \leq S_{i,j} \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq v_k \leq N
- 1 \leq d_k \leq M_{v_k}
- 所有输入值均为整数。
输入
N
M_1 S_{1,1} S_{1,2} \ldots S_{1,M_1}
M_2 S_{2,1} S_{2,2} \ldots S_{2,M_2}
\vdots
M_N S_{N,1} S_{N,2} \ldots S_{N,M_N}
Q
v_1 d_1
v_2 d_2
\vdots
v_Q d_Q
- 第一行包含一个整数 N representing the number of libraries.
- 以下内容中 N lines, the i- 第行 (1 \leq i \leq N) 包含流派数量 M_i in library i 和初始图书计数 S_{i,1}, S_{i,2}, \ldots, S_{i,M_i} for each genre, given in this order separated by spaces.
- 下一行包含一个整数 Q representing the number of lending requests.
- 以下内容中 Q lines, the k- 第行 (1 \leq k \leq Q) 包含图书馆编号 v_k and the genre number d_k for the k-th lending request, separated by a space.
输出
输出 N + 1 行。
- 关于 i- 第行 (1 \leq i \leq N),输出图书馆每种类型的剩余图书数量 i after processing all lending requests, as M_i 按类型排列的整数 1 to genre M_i,用空格分隔。
- 关于 (N + 1)-th line, output the number of failed lending requests as a single integer.
示例输入 1
2 2 3 1 1 0 4 1 1 1 2 1 2 2 1
示例输出 1
2 0 0 2
示例输入 2
3 3 5 0 2 2 1 1 2 3 0 8 1 2 1 1 2 1 2 2 3 2 1 3 1 3 3 1
示例输出 2
4 0 0 0 0 2 0 2
示例输入 3
4 3 1000000000 0 5 4 2 3 1 0 1 100 2 10 20 12 1 1 1 2 1 2 1 3 2 4 2 4 3 1 3 1 4 1 4 2 4 2 2 3
示例输出 3
999999999 0 4 2 3 0 0 98 9 18 4