問題一覧 > 通常問題

No.1997 X Lighting

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 68
作問者 : MasKoaTS / テスター : 👑 potato167 Shirotsume
お気に入りにしたユーザー ProblemId : 7752 / 自分の提出
問題文最終更新日: 2022-05-13 20:47:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 350 (順位表) の他の問題:

Problem Statement

There is a grid with $N$ rows and $N$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left $(1 \leq i,j \leq N)$ is denoted by $(i, j)$.
Each cell contains a button and a light bulb, $1$ of each, and initially all light bulbs are off.

When the button in cell $(x, y)$ $(1 \leq x, y \leq N)$ is pressed, both of the following $2$ events occur.
(For a concrete example, see Sample 1 below.)

  • For every integer $k$ satisfying $\max(1 - x, 1 - y) \leq k \leq \min(N - x, N - y)$,
    if the light bulb in cell $(x + k, y + k)$ is off, it turns on.

  • For every integer $k$ satisfying $\max(1 - x, y - N) \leq k \leq \min(N - x, y - 1)$,
    if the light bulb in cell $(x + k, y - k)$ is off, it turns on.

When all the buttons in the $M$ cells $(X_{i}, Y_{i})$ $(1 \leq i \leq M)$ of this grid have been pressed,
how many light bulbs are on in the entire grid?

Constraints

  • $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)$

  • All inputs are integers.

Input

The input is given in the following format.

$N$ $M$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
   $\vdots$
$X_{M}$ $Y_{M}$
  • Line $1$ contains $N$ and $M$ in this order, separated by a single-byte space.

  • Line $(1 + i)$ $(1 \leq i \leq M)$ contains $X_{i}$ and $Y_{i}$ in this order, separated by a single-byte space.

Output

Output the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
10 2
3 4
8 5
Output
26

figure_01

Initially, the light bulbs in all cells are off.


figure_02

When the button in cell $(3, 4)$ is pressed, a total of $14$ light bulbs in the following cells (duplicates are not counted separately) turn on.

  • Event $1$ : $(1, 2), (2, 3), \dots, (9, 10)$

  • Event $2$ : $(1, 6), (2, 5), \dots, (6, 1)$


figure_03

Next, when the button in cell $(8, 5)$ is pressed, $12$ more light bulbs turn on in the same way.
Light bulbs that are already on stay on.

Therefore, in the end, a total of $26$ light bulbs are on.

Sample 2
Input
9 5
6 9
9 1
5 4
6 8
9 5
Output
44
Sample 3
Input
1000000000000 10
670838682 757586454
516823812 721590390
527726910 84114941
128888077 947055903
881666783 350676972
66848510 5572812
563194058 298525843
624810394 65280819
947209466 485726453
563921088 359201010
Output
10005931298786

The answer may not fit in a 32-bit integer type.

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