Status

User's AC Ratio

60.0% (6/10)

Submission's AC Ratio

8.4% (7/83)

Description

給你一個 $N\times M$ 的方格紙，
一開始方格紙上面有些格子是黑色，有些格子是白色。
接著會有 $Q$ 筆操作，每次操作將一個白色格子塗黑，
每一筆操作為相依的，
也就是說你塗完一個格子後下次操作也不會恢復原狀。
請問每次操作後會有多少白色格子的聯通塊，
以及最大塊白色聯通塊的大小為何？

如果兩個格子有一個共同邊且顏色相同，
則我們視這兩個格子為聯通，
如果找到一塊極大數量且聯通的格子，則稱為聯通塊。
如下圖有三個聯通塊。

Input Format

第一行有三個正整數 $N,M,Q$，代表方格紙的大小為 $N\times M$，並且有 $Q$ 筆詢問。
接下來 $N$ 行，每行有 $M$ 個數字 $a$，代表方格紙一開始的狀態，若 $a$ 為 $0$ 代表該格子為白色，若 $a$ 為 $1$ 則代表該格子為黑色。
接下來 $Q$ 行，每行有兩個正整數 $r,c$，代表要將格子 $(r,c)$ 塗成黑色。

$1\leq N,M\leq3000$
$Q\leq2\times10^5$
$a\in{0,1}$
$1\leq r\leq N$
$1\leq c\leq M$

Output Format

對於每一筆操作，請輸出兩個數字，分別代表白色格子的聯通塊數量及最大的白色聯通塊大小。

Sample Input 1

5 8 5
0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0
0 0 1 1 1 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 0
3 1
1 8
3 6
1 3
3 7

Sample Output 1

4 17
4 17
6 8
6 7
5 7

Sample Input 2

7 9 8
1 1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0 0
1 0 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1 0
1 0 0 0 1 1 1 1 0
0 0 1 1 1 0 0 1 1
0 1 1 1 1 0 0 0 1
7 7
1 5
2 5
6 2
3 6
3 7
4 4
1 7

Sample Output 2

4 26
4 25
4 24
5 21
5 20
6 10
7 9
7 8

Hints

此為 Sample Testcase 1 的圖形

Problem Source

Subtasks

No.	Testdata Range	Score
1	0~37	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	3000	196608	65536	1
1	3000	196608	65536	1
2	3000	196608	65536	1
3	3000	196608	65536	1
4	3000	196608	65536	1
5	3000	196608	65536	1
6	3000	196608	65536	1
7	3000	196608	65536	1
8	3000	196608	65536	1
9	3000	196608	65536	1
10	3000	196608	65536	1
11	3000	196608	65536	1
12	3000	196608	65536	1
13	3000	196608	65536	1
14	3000	196608	65536	1
15	3000	196608	65536	1
16	3000	196608	65536	1
17	3000	196608	65536	1
18	3000	196608	65536	1
19	3000	196608	65536	1
20	3000	196608	65536	1
21	3000	196608	65536	1
22	3000	196608	65536	1
23	3000	196608	65536	1
24	3000	196608	65536	1
25	3000	196608	65536	1
26	3000	196608	65536	1
27	3000	196608	65536	1
28	3000	196608	65536	1
29	3000	196608	65536	1
30	3000	196608	65536	1
31	3000	196608	65536	1
32	3000	196608	65536	1
33	3000	196608	65536	1
34	3000	196608	65536	1
35	3000	196608	65536	1
36	3000	196608	65536	1
37	3000	196608	65536	1

Submit