In our problem, \(N\) is as large as \(10^9\), so the state of the cells cannot be simply managed in a two-dimensional array. Instead, we need to manage the positions of the blocks in a more efficient way, and determine fast if the new block would overlap with existing blocks.

From now on, let “block \((r,c)\)” refer to a block that occupies the \(2\times 2\) region, with cell \((r,c)\) being the top-left cell.

First, we have the following fact regarding overlaps of blocks:

• Blocks \((r_1,c_1)\) and \((r_2,c_2)\) overlap if and only if \(|r_1-r_2|\leq1\) and \(|c_1-c_2|\leq1\).

In particular, to determine if a block \((r,c)\) would block any existing block, it is sufficient to determine, for each of the four pairs \((r',c')\) with \(r-1\leq r' \leq r+1\) and \(c-1\leq c' \leq c+1\), if block \((r', c')\) is contained in the existing blocks.

Based on this fact, we now see that it is sufficient to manage the positions of existing blocks in some data structure supporting insertion and existence-check of elements in a set. Specific examples of such data structures include hash set and balanced binary search tree. In fact, (in most programming languages) you do not need to manually implement it; for example, C++ has std::set and std::unordered_set, and Python has set as a standard library, both facilitating implementations.

For more details on implementations, refer to the following sample code.

Sample code (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;
}