[CCO 2023] Triangle Collection

Luogu

IDLGP10071

Time1000ms

Memory1024MB

DifficultyP6

2023CCO（加拿大）

Alice 有一些棍子。一开始，对于每个 $l=1, \ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。 Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $l_{i}$ 和 $d_{i}$，表示长度为 $l_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $l$ 的棍子。你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。 ## Input 第一行包含两个用空格分隔的整数 $N$ 和 $Q$。第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $l_{i}$ 和 $d_{i}$，表示一个事件。保证在每个事件之前和之后，对于每个 $l=1, \ldots, N$，长度为 $l$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。 ## Output 输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。 [samples] ## Note 在第一个事件之后，Alice 可以用长度为 $ (1,1,1)$ 的棍子做一个三角形。在第二个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形。在第三个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形，并用长度为 $(2,2,3)$ 的棍子做一个三角形。对于所有的数据，有 $1 \leq N, Q \leq 2\times 10^5$，$0 \leq c_{i} \leq 10^{9}$，$1 \leq l_{i} \leq N$，$-10^{9} \leq d_{i} \leq 10^{9}$。 |子任务编号| 分值| N, Q 的范围| 额外限制| | :-: | :-: |:-:|:-:| |1| 20| $1 \leq N, Q \leq 2000$| 在所有时刻，总共最多有 $2000$ 根棍子。| |2| 20| $1 \leq N, Q \leq 2000$|没有额外的限制| |3| 20| $1 \leq N, Q \leq 2\times 10^5$| 在所有时刻，每种长度的棍子的数量只会是 $1,2,3$ | |4| 20| $1 \leq N, Q \leq 2\times 10^5$| $d_{i}=1,-1$ | |5| 20| $1 \leq N, Q \leq 2\times 10^5$|没有额外的限制|

Samples

Input #1

Output #1

1
3
4

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2023] Triangle Collection",
    "description": {
      "content": "Alice 有一些棍子。一开始，对于每个 $l=1, \\ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。 Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10071"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice 有一些棍子。一开始，对于每个 $l=1, \\ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。\n\nAlice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments