CCO '23 P6 - Triangle Collection

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 4.0s
Memory limit: 1G

Author:
Problem types
Canadian Computing Olympiad: 2023 Day 2, Problem 3

Alice has a collection of sticks. Initially, she has c_{\ell} sticks of length \ell for each \ell = 1, \ldots, N.

Alice would like to use her sticks to make some isosceles triangles. An isosceles triangle is made of two sticks of the same length, say \ell, and a third stick with a length between 1 and 2\ell - 1 inclusive. Note that the triangles must strictly obey the triangle inequality, and equilateral triangles are okay. Each stick may be used in at most one triangle. Alice would like to know the maximum number of isosceles triangles she can make with her sticks.

There are Q events that change the collection of sticks she has. The i-th event consists of two integers \ell_{i} and d_i, representing that the number of sticks of length \ell_{i} changes by d_{i}. Note that d_i may be positive, negative, or even 0, but Alice will never have a negative number or more than 10^9 sticks of each length.

Your task is to determine the maximum number of isosceles triangles Alice can make after each event if she uses her sticks optimally.

Input Specification

The first line of input contains two space-separated integers N and Q.

The second line of input contains N space-separated integers c_1, c_2,\ldots, c_N (0 \le c_i \le 10^9), representing Alice's initial collection.

The next Q lines of input each contain two space-separated integers \ell_i and d_i (1 \le \ell_i \le N, -10^9 \le d_i \le 10^9), representing an event.

Initially and after each event, the number of sticks of length \ell is between 0 and 10^9 for all \ell = 1,\ldots, N.

Marks AwardedBounds on N,QAdditional Constraints
5 marks1 \le N,Q \le 2\,000There are at most 2\,000 sticks in
total initially and after each event
5 marks1 \le N,Q \le 2\,000No additional constraints.
5 marks1 \le N,Q \le 200\,000The number of sticks of each length is either
0, 1, or 2 initially and after each event.
5 marks1 \le N,Q \le 200\,000For each event, |d_i|=1
5 marks1 \le N,Q \le 200\,000No additional constraints.

Output Specification

Output Q lines each containing a single integer, the answer after each event.

Sample Input

4 3
3 1 4 1
3 -3
1 6
2 1

Output for Sample Input

1
3
4

Explanation of Output for Sample Input

After the first event, Alice can make a single triangle with sticks of lengths (1, 1, 1).

After the second event, Alice can make 3 triangles with sticks of lengths (1, 1, 1).

After the third event, Alice can make 3 triangles with sticks of lengths (1, 1, 1) and a triangle with sticks of lengths (2, 2, 3).


Comments

There are no comments at the moment.