/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N を正の整数とします。 行と列にそれぞれ 0 から 2N までの番号が付いた (2N+1)\times (2N+1) のマス目があり、行 i かつ列 j に属するマスを (i,j) で表します。
白のポーンが 1 つあり、最初 (0,N) に置かれています。 黒のポーンは M 個あり、i 個目の黒のポーンは (X_i, Y_i) に置かれています。
白のポーンが (i,j) にあるとき、あなたは以下のいずれかの操作で白のポーンを動かすことができます。
- 0\leq i\leq 2N-1, 0 \leq j\leq 2N を満たし、(i+1,j) に黒のポーンが無いならば、白のポーンを (i+1,j) に動かす。
- 0\leq i\leq 2N-1, 0 \leq j\leq 2N-1 を満たし、(i+1,j+1) に黒のポーンが有るならば、白のポーンを (i+1,j+1) に動かす。
- 0\leq i\leq 2N-1, 1 \leq j\leq 2N を満たし、(i+1,j-1) に黒のポーンが有るならば、白のポーンを (i+1,j-1) に動かす。
黒のポーンは動かすことができません。
この操作を繰り返した結果、(2N,Y) に白のポーンが置かれている状態にできるような Y の値としてあり得るものの個数を求めてください。
制約
- 1 \leq N \leq 10^9
- 0 \leq M \leq 2\times 10^5
- 1 \leq X_i \leq 2N
- 0 \leq Y_i \leq 2N
- (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 Y_1 : X_M Y_M
出力
答えを出力せよ。
入力例 1
2 4 1 1 1 2 2 0 4 2
出力例 1
3
(4,0), (4,1), (4,2) の 3 つへはそれぞれ次のように動かせます:
- (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)
- (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)
- (0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)
一方、 (4,3) と (4,4) へは動かすことができません。 よって、 3 を出力します。
入力例 2
1 1 1 1
出力例 2
0
白のポーンを (0,1) から動かすことはできません。
Score : 500 points
Problem Statement
Let N be a positive integer. We have a (2N+1)\times (2N+1) grid where rows are numbered 0 through 2N and columns are also numbered 0 through 2N. Let (i,j) denote the square at Row i and Column j.
We have one white pawn, which is initially at (0, N). Also, we have M black pawns, the i-th of which is at (X_i, Y_i).
When the white pawn is at (i, j), you can do one of the following operations to move it:
- If 0\leq i\leq 2N-1, 0 \leq j\leq 2N hold and (i+1,j) does not contain a black pawn, move the white pawn to (i+1, j).
- If 0\leq i\leq 2N-1, 0 \leq j\leq 2N-1 hold and (i+1,j+1) does contain a black pawn, move the white pawn to (i+1,j+1).
- If 0\leq i\leq 2N-1, 1 \leq j\leq 2N hold and (i+1,j-1) does contain a black pawn, move the white pawn to (i+1,j-1).
You cannot move the black pawns.
Find the number of integers Y such that it is possible to have the white pawn at (2N, Y) by repeating these operations.
Constraints
- 1 \leq N \leq 10^9
- 0 \leq M \leq 2\times 10^5
- 1 \leq X_i \leq 2N
- 0 \leq Y_i \leq 2N
- (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M X_1 Y_1 : X_M Y_M
Output
Print the answer.
Sample Input 1
2 4 1 1 1 2 2 0 4 2
Sample Output 1
3
We can move the white pawn to (4,0), (4,1), and (4,2), as follows:
- (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)
- (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)
- (0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)
On the other hand, we cannot move it to (4,3) or (4,4). Thus, we should print 3.
Sample Input 2
1 1 1 1
Sample Output 2
0
We cannot move the white pawn from (0,1).