← 返回题目列表

AtCoder · awc0036_a

A. 图书馆借阅管理

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

分数: 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