本問題では、\(N\) が最大で \(10^9\) と大きいため、マス目の状態を単純に二次元配列として管理することはできません。したがって、今までに置いたブロックの位置をより効率的な方法で管理し、新たに置きたいブロックが既に存在するブロックと重なるかどうかを高速に判定できる必要があります。

以下、マス \((r,c)\) を左上とする \(2\times 2\) の領域を占めるブロックのことを、ブロック \((r,c)\) と呼びます。

まず、ブロック同士の重なり判定に関して、以下の事実が成立します。

• ブロック \((r_1,c_1)\) とブロック \((r_2,c_2)\) は、\(|r_1-r_2|\leq1\) かつ \(|c_1-c_2|\leq1\) である場合に、またその場合に限り重なる。

特に、あるブロック \((r,c)\) が既に置かれている他のブロックと重なるかどうか判定したい場合、\(r-1\leq r' \leq r+1, c-1\leq c' \leq c+1\) を満たす \(9\) 通りの組 \((r',c')\) に対して、既に置かれているブロックの中にブロック \((r',c')\) があるかどうか確認すればよいです。

以上のことをふまえると、既に置いたブロックの位置を、何らかの「集合に対する要素の追加・存在判定を高速に行えるデータ構造」を用いて管理すればよいことがわかります。具体的には ハッシュセット や 平衡二分探索木 などのデータ構造が該当しますが、これらを自分で実装する必要は（ほとんどのプログラミング言語においては）なく、例えば C++ では std::set や std::unordered_set、Python では set が標準で組み込まれているため、それらを用いることで簡単に実装できます。

実装の詳細は下記の実装例を参考にしてください。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    set<pair<int, int>> st;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        int r, c;
        cin >> r >> c;
        bool ok = true;
        for (int x = r - 1; x <= r + 1; x++) {
            for (int y = c - 1; y <= c + 1; y++) {
                if (st.contains({x, y})) ok = false;
            }
        }
        if (ok) {
            st.insert({r, c});
            ++ans;
        }
    }
    cout << ans << endl;
}