C - Flip Grid
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
H 行 W 列からなるマス目があり、各マスの色は白または黒です。
i 行目 j 列目にあるマスを、マス (i,j) と呼ぶことにします。
黒いマスが N 個あり、i 番目の黒いマスは マス(x_i, y_i) です。
また、 黒くない残りの HW-N 個のマスの色は白です。
あなたはマス目に対して以下の操作を行うことができます。
- 正整数の組 (a,b) (1 \leq a \leq H, 1 \leq b \leq W) を選び、 1 \leq i \leq a かつ 1 \leq j \leq b を満たす全てのマス (i,j) の色を反転させる (白ならば黒に、黒ならば白に色を変える)。
HW 個全てのマスを白色にするために必要な操作回数の最小値を求めてください。
制約
- 1 \leq H,W \leq 2 \times 10^5
- 1 \leq N \leq \mathrm{min}(2 \times 10^5, H \times W)
- 1 \leq x_i \leq H
- 1 \leq y_i \leq W
- (x_i, y_i) \neq (x_j, y_j) (i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W N x_1 y_1 \vdots x_N y_N
出力
答えを整数で出力せよ。
入力例 1
2 2 2 1 2 2 1
出力例 1
2
はじめ、マス (1,2) とマス (2,1) のみが黒いマス、それ以外が白いマスです。
まず、 (a,b) = (2,1) として操作をすることで、マス (1,1) が白から黒に変わり、マス (2,1) が黒から白に変わります。
次に、 (a,b) = (1,2) として操作をすることで、マス (1,1) とマス (1,2) が黒から白に変わります。
このように、2 回の操作で 4 マス全てを白色にすることができました。
入力例 2
2 4 3 1 2 1 3 2 3
出力例 2
4