/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
はじめ、全てのマスには壁が 1 個ずつ立てられています。
以下で説明されるクエリを Q 個与えられる順に処理した後に、残っている壁の個数を求めてください。
q 番目のクエリでは整数 R_q, C_q が与えられます。
あなたは (R_q, C_q) に爆弾を置いて壁を爆破します。その結果、以下の処理が行われます。
- (R_q, C_q) に壁が存在する場合は、その壁を破壊して処理を終了する。
- (R_q, C_q) に壁が存在しない場合は、(R_q, C_q) から上下左右に見て最初に現れる壁を破壊する。厳密に述べると、以下の 4 個の処理が同時に行われる。
- (i, C_q) に壁が存在して (k, C_q) (i \lt k \lt R_q) に壁が存在しないような i \lt R_q が存在する時、(i, C_q) に存在する壁を破壊する。
- (i, C_q) に壁が存在して (k, C_q) (R_q \lt k \lt i) に壁が存在しないような i \gt R_q が存在する時、(i, C_q) に存在する壁を破壊する。
- (R_q, j) に壁が存在して (R_q, k) (j \lt k \lt C_q) に壁が存在しないような j \lt C_q が存在する時、(R_q, j) に存在する壁を破壊する。
- (R_q, j) に壁が存在して (R_q, k) (C_q \lt k \lt j) に壁が存在しないような j \gt C_q が存在する時、(R_q, j) に存在する壁を破壊する。
制約
- 1 \leq H, W
- H \times W \leq 4 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq R_q \leq H
- 1 \leq C_q \leq W
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
H W Q R_1 C_1 R_2 C_2 \vdots R_Q C_Q
出力
クエリを全て処理した後に、残っている壁の個数を出力せよ。
入力例 1
2 4 3 1 2 1 2 1 3
出力例 1
2
クエリを処理する手順を説明すると次のようになります。
- 1 番目のクエリでは (R_1, C_1) = (1, 2) である。 (1, 2) に壁は存在するので (1, 2) の壁が爆破される。
- 2 番目のクエリでは (R_2, C_2) = (1, 2) である。 (1, 2) に壁は存在しないので、(1, 2) から上下左右に見て最初に現れる壁である (2,2),(1,1),(1,3) が爆破される。
- 3 番目のクエリでは (R_2, C_2) = (1, 3) である。 (1, 3) に壁は存在しないので、(1, 3) から上下左右に見て最初に現れる壁である (2,3),(1,4) が爆破される。
全てのクエリを処理した後に残っている壁は (2, 1), (2, 4) の 2 個です。
入力例 2
5 5 5 3 3 3 3 3 2 2 2 1 2
出力例 2
10
入力例 3
4 3 10 2 2 4 1 1 1 4 2 2 1 3 1 1 3 1 2 4 3 4 2
出力例 3
2
Score : 400 points
Problem Statement
There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Initially, there is one wall in each cell.
After processing Q queries explained below in the order they are given, find the number of remaining walls.
In the q-th query, you are given two integers R_q and C_q.
You place a bomb at (R_q, C_q) to destroy walls. As a result, the following process occurs.
- If there is a wall at (R_q, C_q), destroy that wall and end the process.
- If there is no wall at (R_q, C_q), destroy the first walls that appear when looking up, down, left, and right from (R_q, C_q). More precisely, the following four processes occur simultaneously:
- If there exists an i \lt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all i \lt k \lt R_q, destroy the wall at (i, C_q).
- If there exists an i \gt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all R_q \lt k \lt i, destroy the wall at (i, C_q).
- If there exists a j \lt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all j \lt k \lt C_q, destroy the wall at (R_q, j).
- If there exists a j \gt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all C_q \lt k \lt j, destroy the wall at (R_q, j).
Constraints
- 1 \leq H, W
- H \times W \leq 4 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq R_q \leq H
- 1 \leq C_q \leq W
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W Q R_1 C_1 R_2 C_2 \vdots R_Q C_Q
Output
Print the number of remaining walls after processing all queries.
Sample Input 1
2 4 3 1 2 1 2 1 3
Sample Output 1
2
The process of handling the queries can be explained as follows:
- In the 1st query, (R_1, C_1) = (1, 2). There is a wall at (1, 2), so the wall at (1, 2) is destroyed.
- In the 2nd query, (R_2, C_2) = (1, 2). There is no wall at (1, 2), so the walls at (2,2),(1,1),(1,3), which are the first walls that appear when looking up, down, left, and right from (1, 2), are destroyed.
- In the 3rd query, (R_3, C_3) = (1, 3). There is no wall at (1, 3), so the walls at (2,3),(1,4), which are the first walls that appear when looking up, down, left, and right from (1, 3), are destroyed.
After processing all queries, there are two remaining walls, at (2, 1) and (2, 4).
Sample Input 2
5 5 5 3 3 3 3 3 2 2 2 1 2
Sample Output 2
10
Sample Input 3
4 3 10 2 2 4 1 1 1 4 2 2 1 3 1 1 3 1 2 4 3 4 2
Sample Output 3
2