置くことができるマス全体は最大で \(10 ^ {18}-3\) 個などと非常に大きくなる可能性がありますが、置くことができないマスはたかだか \(9M\) 個なので、これをすべて管理することができます。 置くことができないマスをハッシュセットなどで管理し、重複を取り除いて個数を数えることで、この問題を解くことができます。 時間計算量は \(O(M)\) や \(O(M\log M)\) などになります。

実装例は以下のようになります。

#include <iostream>
#include <set>
#include <vector>

int main() {
    using namespace std;
    int N, M;
    cin >> N >> M;

    // 置くことができないマスの集合
    set<pair<int, int>> bad_cell;
    // コマの動く先
    vector<pair<int, int>> knight_move{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        bad_cell.emplace(x, y);
        for (const auto& [dx, dy] : knight_move)
            // 取れる先が存在するマスなら
            if (1 <= x + dx && x + dx <= N && 1 <= y + dy && y + dy <= N)
                bad_cell.emplace(x + dx, y + dy);
    }

    // マス全体から置けないマスを引いたものが答え
    cout << static_cast<long>(N) * N - size(bad_cell) << endl;

    return 0;
}