P10071 [CCO 2023] Triangle Collection

Alice has some sticks. Initially, for each $l = 1, \ldots, N$, she has $c_{l}$ sticks of length $l$. Alice wants to use her sticks to make some isosceles triangles. An isosceles triangle consists of two sticks of length $l$ and one stick whose length is between $1$ and $2 l - 1$. Note that the three stick lengths must strictly satisfy the triangle inequality, and equilateral triangles are also allowed. Each stick can be used in at most one triangle. Alice wants to know the maximum number of isosceles triangles she can make using her sticks. There are $Q$ events that change the number of sticks she has. The $i$-th event contains two integers $l_{i}$ and $d_{i}$, meaning that the number of sticks of length $l_{i}$ changes by $d_{i}$. Note that $d_{i}$ can be any integer, but Alice will never have a negative number of sticks of length $l$, nor more than $10^{9}$ sticks of length $l$. You need to compute, after each event, the maximum number of isosceles triangles Alice can make using her sticks.

The first line contains two integers $N$ and $Q$, separated by spaces. The second line contains $N$ integers $c_{1}, c_{2}, \ldots, c_{N}$, separated by spaces, representing the sticks Alice initially has. The next $Q$ lines each contain two integers $l_{i}$ and $d_{i}$, separated by spaces, representing an event. It is guaranteed that before and after each event, for every $l = 1, \ldots, N$, the number of sticks of length $l$ is between $0$ and $10^{9}$.

Output $Q$ lines. Each line contains one integer, the answer after the corresponding event.

After the first event, Alice can make one triangle using sticks of lengths $(1,1,1)$. After the second event, Alice can make three triangles using sticks of lengths $(1,1,1)$. After the third event, Alice can make three triangles using sticks of lengths $(1,1,1)$, and one triangle using sticks of lengths $(2,2,3)$. Constraints: for all testdata, $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}$. |Subtask ID|Points|Range of $N, Q$|Additional Constraints| | :-: | :-: | :-: | :-: | |1|20|$1 \leq N, Q \leq 2000$|At all times, there are at most $2000$ sticks in total.| |2|20|$1 \leq N, Q \leq 2000$|No additional constraints.| |3|20|$1 \leq N, Q \leq 2\times 10^5$|At all times, the number of sticks of each length will only be $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$|No additional constraints.| Translated by ChatGPT 5