Funcia
Lv.1simulationstack

Score Sheet

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A score sheet starts empty and processes the commands ops in order:

CommandMeaning
an integer x (e.g. "5", "-2")write a new score x
"+"write the sum of the two most recent scores
"D"write double the most recent score
"C"erase the most recent score

Erased scores no longer count as recent. After each command, record the sum of the scores currently on the sheet, and return these sums in command order.

Examples

opsresult
["5", "2", "C", "D", "+"][5, 7, 5, 15, 30]
["5", "-2", "4", "C", "D", "9", "+", "+"][5, 3, 7, 3, -1, 8, 13, 27]
["1", "C"][1, 0]

Example 1 — the sheet goes [5], [5, 2], [5], [5, 10], [5, 10, 15].

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(ops: string[]) → long[]

Constraints

  • 1≤1 \le ops.length ≤200,000\le 200{,}000
  • Integer commands satisfy −30,000≤x≤30,000-30{,}000 \le x \le 30{,}000, without leading zeros or a + sign.
  • When "+" is given the sheet holds at least two scores; when "D" or "C" is given it holds at least one.
  • Every score written has absolute value at most 10910^9. The sums may exceed the 32-bit range.

Expected complexity

Time
O(N)
Space
O(N)

Examples

opsExpected
["5","2","C","D","+"][5,7,5,15,30]
["5","-2","4","C","D","9","+","+"][5,3,7,3,-1,8,13,27]
["1","C"][1,0]

Hint

Hint

Keep the scores on a stack and maintain a running total: add each new score and subtract each erased one. Use 64-bit integers for the total. Re-adding the whole sheet after every command is O(N2)O(N^2) and exceeds the time limit; each command can be handled in O(1)O(1).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251538 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.