DP. 大事な座標だけ見れば十分．差分を高速に計算する．
黒のポーンが置かれている行だけが重要． 黒のポーンが無い行は，真下に進むしかないので， 動けるマスに変化は無い．
黒のポーンがある行 \(x\) に対して，黒のポーンの \(y\) 座標を記録しておく． あとはルールに従って遷移する． 真下に移動，斜め下に移動(2つ)の合計3つの遷移があり得る． 遷移出来るかどうかは，黒のポーンの有無により決まる．
注意
遷移する際，黒のポーンを基準で考えたほうが速い． 黒のポーンの \(y\) 座標は全体で \(M\) 個なので少ない．
白のポーン基準で移動先を判定すると，現時点の白のポーンのあり得る \(y\) 座標が 多くなる場合がある． 白のポーンの \(y\) 座標は，最悪ケースで遷移毎に \(1,3,5,7, \cdots, M+1\) となる(\(M\)は偶数とした)．
また，遷移可能なマスと不可能なマスが同じマスである場合， 可能な方が優先されるので，バッファは 削除 -> 追加 の順．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
map<ll,set<ll>> mp;
rep(i,m){
ll x,y; cin >> x >> y;
mp[x].insert(y);
}
set<ll> st; // st : whilte pawn
st.insert(n);
for(auto [_,t]:mp){ // t : black pawn
set<ll> buf_i, buf_e;
for(auto y:t){
if(in(y,st)) buf_e.insert(y);
if(in(y+1,st)) buf_i.insert(y);
if(in(y-1,st)) buf_i.insert(y);
}
for(auto y:buf_e) st.erase(y);
for(auto y:buf_i) st.insert(y);
}
cout << st.size() << endl;
// TLE : white pawn 基準にすると，動けるマスが多かった場合に，遷移が大きくなるから．
// set<ll> st;
// st.insert(n);
// for(auto [_,t]:mp){ // t : black pawn
// set<ll> buf_i, buf_e;
// for(auto y:st){ // st : white pawn
// if(in(y,t)) buf_e.insert(y);
// if(in(y+1,t)) buf_i.insert(y+1);
// if(in(y-1,t)) buf_i.insert(y-1);
// }
// for(auto y:buf_e) st.erase(y);
// for(auto y:buf_i) st.insert(y);
// }
// cout << st.size() << endl;
return 0;
}
