実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 274

問題概要

縦 $N$ マス、横 $N$ マスからなるマス目があり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼ぶ。マス目には既に $M$ 個のコマが置かれており、 $k$ 番目のコマはマス $(a_k, b_k)$ に置かれている。

これから、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置くことを考える。マス $(i, j)$ に置かれているコマは、次のどちらかの条件を満たすコマを取ることができる。

マス $(i+2, j+1)$ に置かれている。
マス $(i+1, j+2)$ に置かれている。
マス $(i-1, j+2)$ に置かれている。
マス $(i-2, j+1)$ に置かれている。
マス $(i-2, j-1)$ に置かれている。
マス $(i-1, j-2)$ に置かれている。
マス $(i+1, j-2)$ に置かれている。
マス $(i+2, j-1)$ に置かれている。

このとき、自分のコマを置くことができるマスがいくつあるか求めよ。

制約

入力はすべて整数。
$1\leq N\leq10^9$
$1\leq M\leq2\times10^5$

考察

B問題とほぼ同じ問題設定だが、 $N$ は最大 $10^9$ になるので、B問題の解法と同じ方針を取ると MLE や TLE となってしまう。

そこで、自分のコマを置くことができないマス (= 既に置かれているコマが取ることのできるマス) のみを記録しておき、その個数をマスの総数 $N^2$ から引くことを考える。

自分のコマが置けないマスは、setなどに格納しておくのがよいだろう。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    ll N, M;
    cin >> N >> M;

    set<pair<int, int>> attackable;
    rep(i, 0, M)
    {
        int a, b;
        cin >> a >> b;
        attackable.insert({a, b});

        rep(j, 0, 8)
        {
            int nx = a + dx[j];
            int ny = b + dy[j];

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= N)
            {
                attackable.insert({nx, ny});
            }
        }
    }

    ll ans = N * N - attackable.size();
    cout << ans << endl;
}