/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 行 N 列のマス目があります。
最初、マス目の上には何も置かれていません。
その状態から始めて、高橋君がマス目に対して M 回の操作を順に行います。i 回目 (1\leq i\leq M) の操作は以下のとおりです。
- 上から R_i 行目のマスに置かれているコマをすべて取り除く。
- 次に、左から C_i 列目のマスに置かれているコマをすべて取り除く。
- 最後に、上から R_i 行目かつ左から C_i 列目のマスにコマを置く。
M 回の操作の後でマス目に置かれているコマの個数を出力してください。
制約
- 1 \leq N \leq 3\times 10^5
- 1 \leq M \leq 3\times 10^5
- 1 \leq R_i \leq N
- 1 \leq C_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M R_1 C_1 R_2 C_2 \vdots R_M C_M
出力
M 回の操作の後でマス目に置かれているコマの個数を出力せよ。
入力例 1
3 6 1 1 1 2 3 3 3 2 1 3 1 3
出力例 1
2
最初、3 行 3 列のマス目の上に何も置かれていないところから、それぞれの操作によって、次のようにコマが取り除かれ、置かれます。
以下では、上から i 行目かつ左から j 列目のマスをマス (i,j) で表します。
- 1 回目の操作では、マス (1,1) にコマが置かれます。
- 2 回目の操作では、マス (1,1) からコマが取り除かれ、マス (1,2) にコマが置かれます。
- 3 回目の操作では、マス (3,3) にコマが置かれます。
- 4 回目の操作では、マス (1,2) およびマス (3,3) からコマが取り除かれ、マス (3,2) にコマが置かれます。
- 5 回目の操作では、マス (1,3) にコマが置かれます。
- 6 回目の操作では、マス (1,3) からコマが取り除かれ、マス (1,3) に再度コマが置かれます。
最終状態において、マス (1,3) およびマス (3,2) に 1 つずつコマが置かれているため、2 を出力します。
入力例 2
2 3 1 2 2 1 1 1
出力例 2
1
Score : 400 points
Problem Statement
There is a grid with N rows and N columns.
Initially, nothing is placed on the grid.
Starting from this state, Takahashi performs M operations on the grid in order. The i-th operation (1\leq i\leq M) is as follows.
- Remove all pieces placed on the cells in the R_i-th row from the top.
- Next, remove all pieces placed on the cells in the C_i-th column from the left.
- Finally, place a piece on the cell at the R_i-th row from the top and the C_i-th column from the left.
Output the number of pieces placed on the grid after the M operations.
Constraints
- 1 \leq N \leq 3\times 10^5
- 1 \leq M \leq 3\times 10^5
- 1 \leq R_i \leq N
- 1 \leq C_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M R_1 C_1 R_2 C_2 \vdots R_M C_M
Output
Output the number of pieces placed on the grid after the M operations.
Sample Input 1
3 6 1 1 1 2 3 3 3 2 1 3 1 3
Sample Output 1
2
Initially, nothing is placed on the grid with three rows and three columns, and pieces are removed and placed by each operation as follows.
Below, the cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j).
- In the first operation, a piece is placed on cell (1,1).
- In the second operation, the piece is removed from cell (1,1), and a piece is placed on cell (1,2).
- In the third operation, a piece is placed on cell (3,3).
- In the fourth operation, the pieces are removed from cell (1,2) and cell (3,3), and a piece is placed on cell (3,2).
- In the fifth operation, a piece is placed on cell (1,3).
- In the sixth operation, the piece is removed from cell (1,3), and a piece is placed on cell (1,3) again.
In the final state, there is one piece each on cell (1,3) and cell (3,2), so output 2.
Sample Input 2
2 3 1 2 2 1 1 1
Sample Output 2
1