[语言月赛202301] 避雷针

Luogu

IDLGB3701

Time1000ms

Memory512MB

DifficultyP1

2023O2优化数组语言月赛

$n$ 个避雷针从左至右排成一排，我们将它们从左至右依次标号为 $1 \sim n$。现在有 $m$ 道雷依次劈下。你得知了一串序列 $a _ 1, \cdots, a _ m$。对于第 $i$ 道雷，其劈中了 $a _ i - 2$（如果存在）、$a _ i - 1$（如果存在）、$a _ i$、$a _ i + 1$（如果存在）、$a _ i + 2$（如果存在）号避雷针。在 $m$ 道雷劈完后，你想要知道，被劈过**至少一次**的避雷针有几个。 ## Input 输入共两行。第一行为两个整数 $n, m$，代表避雷针数量和雷的数量。第二行为 $m$ 个整数 $a _ 1, \cdots, a _ m$，代表题面中的序列。 ## Output 输出共一行。输出一行一个整数，被劈过**至少一次**的避雷针的数量。 [samples] ## Note ### 样例 1 解释被劈中的避雷针是 $2, 3, 4, 5, 6$ 号，共 $5$ 个。 ### 样例 2 解释被劈中的避雷针是 $1, 2, 3, 4$ 号，共 $4$ 个。请注意 $a _ 1 - 2 = 0$ 号避雷针不存在，也不应被劈中。 ### 样例 3 解释被劈中的避雷针是 $1, 2, 3, 4, 5, 6, 7, 8, 9$ 号，共 $9$ 个。请注意尽管部分避雷针被劈了两次甚至三次，对这些避雷针我们仍然只计数一次。 ### 数据规模与约定 - 对于前 $10\%$ 的数据，保证 $n = 1$。 - 对于前 $30\%$ 的数据，保证 $m = 1$。 - 对于另外 $20\%$ 的数据，保证 $m \leq n - 2$ 且 $\forall i \in [1, m], a _ i = i$。 - 对于 $100\%$ 的数据，保证 $1 \leq n,m \leq 10 ^ 6$，$1 \leq a _ i \leq n$。

Samples

Input #1

17 1
4

Output #1

Input #2

10 1
2

Output #2

Input #3

9 3
3 7 7

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛202301] 避雷针",
    "description": {
      "content": "$n$ 个避雷针从左至右排成一排，我们将它们从左至右依次标号为 $1 \\sim  n$。 现在有 $m$ 道雷依次劈下。你得知了一串序列 $a _ 1, \\cdots, a _ m$。对于第 $i$ 道雷，其劈中了 $a _ i - 2$（如果存在）、$a _ i - 1$（如果存在）、$a _ i$、$a _ i + 1$（如果存在）、$a _ i + 2$（如果存在）号避雷针。 在 $m$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3701"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$n$ 个避雷针从左至右排成一排，我们将它们从左至右依次标号为 $1 \\sim  n$。\n\n现在有 $m$ 道雷依次劈下。你得知了一串序列 $a _ 1, \\cdots, a _ m$。对于第 $i$ 道雷，其劈中了 $a _ i - 2$（如果存在）、$a _ i - 1$（如果存在）、$a _ i$、$a _ i + 1$（如果存在）、$a _ i + 2$（如果存在）号避雷针。\n\n在 $m$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments