問題一覧 > 通常問題

No.1997 X Lighting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : MasKoaTSMasKoaTS / テスター : ShirotsumeShirotsume potato167potato167
0 ProblemId : 7752 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-13 20:47:31

問題文

$N$ 行 $N$ 列のマス目があり、上から $i$ 行目、左から $j$ 列目 $(1 \leq i,j \leq N)$ のマスは $(i, j)$ と表されます。
各マスにはボタンと電球が $1$ 個ずつ設置されており、最初すべての電球は消灯しています。

マス $(x, y)$ $(1 \leq x, y \leq N)$ にあるボタンを押すと、次の $2$ つの事象がともに起こります。
(具体例は、下のサンプル1を参照してください)

  • $\max(1 - x, 1 - y) \leq k \leq \min(N - x, N - y)$ を満たす任意の整数 $k$ について、
    マス $(x + k, y + k)$ にある電球が消灯しているならば、これが点灯する。

  • $\max(1 - x, y - N) \leq k \leq \min(N - x, y - 1)$ を満たす任意の整数 $k$ について、
    マス $(x + k, y - k)$ にある電球が消灯しているならば、これが点灯する。

このマス目の中の $M$ 個のマス $(X_{i}, Y_{i})$ $(1 \leq i \leq M)$ にあるボタンをすべて押したとき、
点灯している電球はマス目全体でいくつありますか?

制約

  • $1 \leq N \leq 10^{12}$

  • $1 \leq M \leq \min( N^{2}, 10^{5} )$

  • $1 \leq X_{i}, Y_{i} \leq N$ $(1 \leq i \leq M)$

  • $(X_{i}, Y_{i} ) \neq (X_{j}, Y_{j} )$ $(1 \leq i < j \leq M)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
   $\vdots$
$X_{M}$ $Y_{M}$
  • $1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる

  • $(1 + i)$ $(1 \leq i \leq M)$ 行目には $X_{i}$ と $Y_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
10 2
3 4
8 5
出力
26

figure_01

最初、すべてのマスにある電球は消灯しています。


figure_02

マス $(3, 4)$ にあるボタンを押すと、次のマス(重複しているものは区別しない)にある合計 $14$ 個の電球が点灯します。

  • $1$ つ目の事象 : $(1, 2), (2, 3), \dots, (9, 10)$

  • $2$ つ目の事象 : $(1, 6), (2, 5), \dots, (6, 1)$


figure_03

続いてマス $(8, 5)$ にあるボタンを押すと、先と同様にして新たに $12$ 個の電球が点灯します。
既に点灯している電球はそのまま点灯し続けます。

よって、最終的に全部で $26$ 個の電球が点灯していることになります。

サンプル2
入力
9 5
6 9
9 1
5 4
6 8
9 5
出力
44
サンプル3
入力
1000000000000 10
670838682 757586454
516823812 721590390
527726910 84114941
128888077 947055903
881666783 350676972
66848510 5572812
563194058 298525843
624810394 65280819
947209466 485726453
563921088 359201010
出力
10005931298786

答えは32bit整数型に収まらない可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。