F - Rook on Grid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。

グリッド上には M 個の障害物があり、i 番目の障害物はマス (X_i,Y_i) に置かれています。

マス (1,1) に飛車の駒が置いてあります。飛車の駒は、今いる位置から右または下方向に伸びる直線上にあり、障害物を飛び越えずに到達できるマスに 1 手で移動することができます。

2 手以内の移動で飛車の駒が到達できるマスの数を求めてください。

制約

  • 1\leq H,W \leq 2\times 10^5
  • 0\leq M \leq 2\times 10^5
  • 1\leq X_i \leq H
  • 1\leq Y_i \leq W
  • (X_i,Y_i) \neq (1,1)
  • (X_i,Y_i) は相異なる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

H W M
X_1 Y_1
\vdots
X_M Y_M

出力

2 手以内の移動で飛車の駒が到達できるマスの数を出力せよ。

入力例 1

4 3 2
2 2
3 3

出力例 1

10

障害物のない全てのマスに 2 手以内で移動できます。

入力例 2

5 4 4
3 2
3 4
4 2
5 2

出力例 2

14

障害物のないマスのうち、(4,4),(5,4) 以外の全てのマスに 2 手以内で移動できます。

入力例 3

200000 200000 0

出力例 3

40000000000

Score : 600 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let Square (i,j) be the square at the i-th row and j-th column.

There are M obstacles on this grid. The i-th obstacle is at Square (X_i, Y_i).

We have a rook, the chess piece, on Square (1, 1). In one move, it can move to the right or downward through any number of squares without obstacles.

Find the number of squares the rook can reach in two moves or less.

Constraints

  • 1\leq H,W \leq 2\times 10^5
  • 0\leq M \leq 2\times 10^5
  • 1\leq X_i \leq H
  • 1\leq Y_i \leq W
  • (X_i,Y_i) \neq (1,1)
  • (X_i,Y_i) are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W M
X_1 Y_1
\vdots
X_M Y_M

Output

Print the number of squares the rook can reach in two moves or less.

Sample Input 1

4 3 2
2 2
3 3

Sample Output 1

10

Every square without an obstacle can be reached in two moves or less.

Sample Input 2

5 4 4
3 2
3 4
4 2
5 2

Sample Output 2

14

Every square without an obstacle except (4,4) and (5,4) can be reached in two moves or less.

Sample Input 3

200000 200000 0

Sample Output 3

40000000000