#2142. Triangle Collection

    ID: 2142 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1267来源:qoj.ac数据:公开样例堆

Triangle Collection

Triangle Collection

题目描述

2023 Canadian Computing Olympiad Day 2, Problem 3 Triangle Collection Time Limit: 4 seconds Problem Description Alice has a collection of sticks. Initially, she has cℓsticks of length ℓfor each ℓ= 1, . . . , 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 ℓ, and a third stick with a length between 1 and 2ℓ−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 ℓi and di, representing that the number of sticks of length ℓi changes by di. Note that di may be positive, negative, or even 0, but Alice will never have a negative number or more than 109 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 c1, c2, . . . , cN (0 ≤ci ≤109), representing Alice’s initial collection. The next Q lines of input each contain two space-separated integers ℓi and di (1 ≤ℓi ≤ N, −109 ≤di ≤109), representing an event. Initially and after each event, the number of sticks of length ℓis between 0 and 109 for all ℓ= 1, . . . , N. Marks Awarded Bounds on N, Q Additional Constraints 1 ≤N, Q ≤2 000 5 marks There are at most 2 000 sticks in total initially and after each event. 1 ≤N, Q ≤2 000 5 marks No additional constraints. 1 ≤N, Q ≤200 000 5 marks The number of sticks of each length is either 0, 1, or 2 initially and after each event. 1 ≤N, Q ≤200 000 For each event, |di| = 1. 5 marks 1 ≤N, Q ≤200 000 5 marks No 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).

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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