各行ごとに白のポーンがたどりつけるマス ( 列番号 ) の集合を持ちこれを更新していく事を考えます。
すなわち、 \(S_i=\{ j\in\mathbb{Z} \mid {}\)白のポーンが \((i,j)\) に到達可能 \(\}\ (0\leq i \leq 2N)\) として , \(i=0,1,\ldots 2N-1\) について順に\(S_{i+1}\) を \(S_i\) から求めていく事を考えます。
もちろんこれを愚直に求めようとするとタイムオーバーしてしまいます。

しかし実際には \(S_i\) と \(S_{i+1}\) の間における変化にのみ注目する事で大幅に計算量を改善する事が出来ます。 鍵となるのは次の単純な事実です。

• \((i+1 ,j)\) に黒のポーンが置かれていない時、 \((i,j)\) に白のポーンが到達可能なら \((i+1 ,j)\) に到達可能であり、 \((i,j)\) に白のポーンが到達可能でないならば \((i+1 ,j)\) にも到達可能でない。

まず、これより行 \(i\) に黒のポーンがあるマスが存在しないならば \(S_i=S_{i-1}\) となります。 さらに黒のポーンのある行についても \(S_{i-1}\) と \(S_i\) の間の変化は次の \(2\) つのどちらかしかありません。

• ( \(j-1 \in S_{i-1}\) または \(j+1 \in S_{i-1}\) ) かつ \(j \notin S_{i-1}\) のとき \(j \notin S_{i-1} \to j \in S_i\) となる。
• ( \(j-1 \notin S_{i-1}\) かつ \(j+1 \notin S_{i-1}\) ) かつ \(j \in S_{i-1}\) のとき \(j \in S_{i-1} \to j \notin S_i\) となる。

さらに、\(j<0\) または \(2N<j\) なる \(j\) は黒いポーンのあるマスの列番号として与えられることはないため、\(j\notin S_0\) と合わせて 任意の \(i\) について \(j\notin S_i\) であり、左右の境界について考える必要がない事も分かります。

これより、黒いポーンが置かれたマスにのみ注目すればよく、次のような方法で解くことができます。まず、 \((X_i, Y_i)\) を昇順にソートします。その後、 \(S=\{N\}\) から始めて、 ソートした後の列について前から順に、 \(X_i\) が等しい部分ごとに次のようなことを繰り返します。 \(X_l=X_{l+1}=\cdots =X_r\) であるとします。

• \(S\) に追加する要素の集合 \(A, S\) から削除する集合 \(B\) を最初空集合として用意する。 \(i=l,l+1, \ldots, r\) について順に次の操作を行う。

  • ( \(Y_i-1 \in S\) または \(Y_i+1 \in S\) ) かつ \(Y_i \notin S\) のとき、 \(A\) に \(Y_i\) を追加する。
  • ( \(Y_i-1 \notin S\) かつ \(Y_i+1 \notin S\) ) かつ \(Y_i \in S\) のとき、 \(B\) に \(Y_i\) を追加する。
  • そうでないとき何もしない。

• \(S\) から \(A\) の要素を追加し、\(B\) の要素を削除する。これを新しい \(S\) とする。

これを最後まで行った後の \(S\) が、白のポーンが \((2N,j)\) に到達可能であるような \(j\) の集合であり、これの要素数 \(\lvert S\rvert\) が求めたかったものです。

計算量は最初のソートに \(O(M\log M)\) 、その後の検索や追加・削除の操作も順序付き集合setなどで行えば一度につき \(O(\log M)\) であり全体で \(O(M\log M)\) となります。よって、この問題は\(O(M\log M)\)で解くことができ十分高速です。また、今までの事実により \((2N,j)\) に白のポーンが到達できるならば \(j=N\) または \(j\) 列には \(1\) つ以上黒いポーンが存在する必要があり、答えは \(M+1\) 以下となるので \(32\) bit 整数におさまります。

C++による実装例:

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n, m;
	vector<pair<int, int> > p;
	vector<int>a, b;
	set<int>s;
	int x, y;
	int l, r;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		p.push_back({ x,y });
	}
	sort(p.begin(), p.end());
	s.insert(n);
	l = 0;
	while (l < m) {
		a.clear();
		b.clear();
		r = l;
		while (r < m) {
			if (p[r].first == p[l].first)r++;
			else break;
		}
		for (int i = l; i < r; i++) {
			y = p[i].second;
			if (((s.find(y - 1) != s.end()) || (s.find(y + 1) != s.end())) && (s.find(y) == s.end()))a.push_back(y);
			if (((s.find(y - 1) == s.end()) && (s.find(y + 1) == s.end())) && (s.find(y) != s.end()))b.push_back(y);
		}
		for (int i = 0; i < a.size(); i++)s.insert(a[i]);
		for (int i = 0; i < b.size(); i++)s.erase(b[i]);
		l = r;
	}
	cout << s.size() << endl;
}