Candy Brackets¶
Estimated time limit: 1 second. Memory limit: 128 MB.
The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.
Story¶
A candy workshop strings together candies and bracket-shaped candy shells, adding new treats at either end. Alongside sweet favorites are unusual mustard and bitter-melon flavors: some add sweetness points, while others subtract them. The bracket-shaped shells have sweetness values of their own.
Customers may choose a contiguous segment only if its brackets match completely. After each addition, the workshop wants to find the sweetest eligible segment. Choosing nothing is allowed if none of the treats appeal.
Formal Problem Statement¶
Each element has type \(0\) (an opening bracket), \(1\) (a closing bracket), or \(2\) (a candy), and an integer sweetness value that may be negative, zero, or positive. A string's sweetness is the sum of all element values, including bracket values.
Matching strings are exactly those generated by these rules: the empty string matches; a single candy matches; enclosing a matching string in an opening and a closing bracket gives a matching string; concatenating two matching strings gives a matching string. Sweetness values do not affect matching.
Start with a string of length \(N\) and perform \(M\) operations. Each operation adds one element to the left or right end of the current string, and changes persist. A substring is a contiguous segment in the original order: negative elements in its interior cannot be skipped. The empty string and the entire string are allowed. Find the maximum sweetness of a matching substring initially and after each operation. The empty string has sweetness \(0\) , so the answer is never negative.
Input Format¶
The first line contains integers \(N,M\) .
The second line contains the \(N\) initial types, and the third contains their \(N\) sweetness values, in order. If \(N=0\) , both lines are empty.
Each of the next \(M\) lines contains integers \(position,type,value\) . Position \(0\) means the left end and position \(1\) the right end; \(type\) is the element type and \(value\) its sweetness, possibly with a minus sign.
Output Format¶
Print \(M+1\) lines. The first is the initial answer, followed by the answer after each operation in order.
Samples¶
Sample 1¶
Input¶
2 2
2 2
-10 100
0 2 20
1 2 -200
Output¶
100
110
110
Sample 2¶
Input¶
1 4
2
10
0 0 -8
1 1 -9
0 2 7
1 2 20
Output¶
10
10
10
10
20
Sample 3¶
Input¶
0 4
1 1 4000000000
0 0 4000000000
0 2 0
1 2 3
Output¶
0
0
8000000000
8000000000
8000000003
Sample 4¶
Input¶
3 0
0 2 1
-3 -2 -4
Output¶
0
Sample Explanation¶
In the first sample, initially choose only the candy worth \(100\) . After adding \(20\) at the left, the whole string is worth \(20-10+100=110\) . The final candy worth \(-200\) can be excluded, leaving the answer at \(110\) .
In the second sample, the candy is worth \(10\) . After adding both brackets, the whole matching string is worth \(-8+10-9=-7\) , but its inner candy can still be chosen for \(10\) . Adding \(7\) at the left does not allow choosing both candies while skipping the opening bracket between them. Finally, adding \(20\) at the right gives answer \(20\) , obtained either by that candy alone or by the entire string.
The third sample starts empty. A lone closing bracket does not match. Adding an opening bracket includes the values of both brackets, giving \(8000000000\) .
In the fourth sample, all values are negative, so choose the empty string for \(0\) .
Constraints and Guarantees¶
This problem was strengthened by Codex (GPT-6): every element, including brackets, may have sweetness \(-4\times10^9\le value\le4\times10^9\) , and the data include insertions at both ends with mixed positive and negative values.
For all inputs, \(0\le N,M\le10^6\) , \(position\in\{0,1\}\) , and \(type\in\{0,1,2\}\) . Initial types and values have the same bounds. Zero sweetness, an empty initial string, and zero operations are allowed. Answers require signed 64-bit integers.
| Score share | Additional conditions |
|---|---|
| 20% | \(N+M\le100\) |
| 20% | All element values are nonnegative |
| 20% | Every element has type \(2\) |
| 40% | None |