置くことができるマスも置くことができないマスも非常に大きくなる場合があるため、それらを直接管理することは難しいです。
ここで、複数の異なる方向からコマが効いているマスについて考えます。 このようなマスの個数は \(O(M ^ 2)\) 個と評価できます。

よって、例えば、コマが効いている縦・横・斜めのマスの連なりごとに、これまでに見たマスを数えることでこの問題を解くことができます（同一の連なりを排除した上で、これまでに見たマスとして数えられるマスが全体で \(O(M ^ 2)\) 個となります）。

時間計算量は \(O(M ^ 2)\) や \(O(M ^ 2\log M)\) などとなります。

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

#include <iostream>
#include <set>

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

    // 横・縦・斜めの効き
    set<unsigned> horizontal, vertical, diagonal_slash, diagonal_backslash;
    for (unsigned i{}; i < Q; ++i){
        unsigned x, y;
        cin >> x >> y;
        horizontal.emplace(x);
        vertical.emplace(y);
        diagonal_slash.emplace(x + y);
        diagonal_backslash.emplace(x - y);
    }

    // 縦と横はすぐに計算できる
    unsigned long ans{(N - size(horizontal)) * (N - size(vertical))};

    // 斜め方向 1（x + y が一定）
    for (const auto d : diagonal_slash) {
        // すでに見たマスの x 座標
        set<unsigned> cross_x;
        for (const auto x : horizontal)
            // 交点が内側なら追加
            if (1 <= d - x && d - x <= N)
                cross_x.emplace(x);
        for (const auto y : vertical)
            // 交点が内側なら追加
            if (1 <= d - y && d - y <= N)
                cross_x.emplace(d - y);

        // マスの個数 2 min(d, N + 1) - d - 1 から、すでに見たマスの個数を除いたものが新しく見たマスの個数
        ans -= 2 * min(d, N + 1) - d - 1 - size(cross_x);
    }

    // 斜め方向 2（x - y が一定）
    for (const auto d : diagonal_backslash) {
        // すでに見たマスの x 座標
        set<unsigned> cross_x;
        for (const auto x : horizontal)
            // 交点が内側なら追加
            if (1 <= x - d && x - d <= N)
                cross_x.emplace(x);
        for (const auto y : vertical)
            // 交点が内側なら追加
            if (1 <= d + y && d + y <= N)
                cross_x.emplace(d + y);
        for (const auto e : diagonal_slash)
            // 交点が内側なら追加
            if ((d + e) % 2 == 0 && 1 <= (d + e) / 2 && (d + e) / 2 <= N && 1 <= (e - d) / 2 && (e - d) / 2 <= N)
                cross_x.emplace((d + e) / 2);
        
        // マスの個数 N - |d| から、すでに見たマスの個数を除いたものが新しく見たマスの個数
        ans -= N - min(d, -d) - size(cross_x);
    }

    cout << ans << endl;
    return 0;
}