Cancellation, undo, and combined tools
Use a reduced-prefix invariant, preserve action history, and combine a queue with a stack.
A cancellation can reveal the next one
To remove adjacent equal character pairs, keep the reduced prefix on a stack. If the next character equals the top, pop instead of pushing it. Otherwise push it. For abbaca, the states are a, ab, a, empty, c, ca.
The stack always holds a prefix with no adjacent equal pair. Only the boundary with the new character can need cancellation. This avoids restarting a full scan after each deletion. Every character is pushed at most once and popped at most once, so total processing is linear.
// Complete C++23 program. Input: one lowercase ASCII line.
#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
int main() {
std::string text;
std::getline(std::cin, text);
std::stack<char> kept;
for (char c : text) {
if (!kept.empty() && kept.top() == c) kept.pop();
else kept.push(c);
}
std::string answer;
while (!kept.empty()) {
answer.push_back(kept.top());
kept.pop();
}
std::reverse(answer.begin(), answer.end());
std::cout << (answer.empty() ? "EMPTY" : answer) << '\n';
}Undo reverses the latest uncancelled action
For additions and undo, keep the current total plus a stack of uncancelled amounts. Add pushes the amount and increases the total. Undo copies the top amount, subtracts it, and removes that action. An undo on empty history can do nothing when the contract says so.
Negative additions are still actions. Undoing an addition of −3 increases the total by three. A wide running total avoids overflow from many individually small amounts. Maintaining it is constant work per command; rescanning the entire history after each command can be quadratic.
Optional: reverse each group without reordering groups
A queue can hold waiting values while a temporary stack reverses one group. Move at most k front values into the stack, then drain it into the output. Continue until the queue is empty, including a shorter final group.
For 1 2 3 4 5 6 7 with k = 3, the result is 3 2 1 6 5 4 7. Require k ≥ 1 so the algorithm progresses. Each value makes a bounded number of queue/stack operations, giving O(n + 1) time, an O(n + 1) queue, and O(min(k, n) + 1) temporary stack.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
After adding 10, adding −3, then undoing once, what is the running total?
Turn the idea into code
Process commands on total = 0: 1 x adds and remembers x, 2 undoes the most recent uncancelled addition if any, and 3 prints the total. Only type 3 prints. Allow up to 200000 commands with |x| ≤ 10⁹.
Give me a hint
Store each addition in a stack and maintain a long long total. Undo changes the total before popping its amount.
Show the explained solution
The stack holds exactly the actions still contributing to the total. Each action is pushed once and removed at most once, so the whole program is O(q + 1) time with O(q + 1) worst-case storage.
// Complete C++23 program. Input: q, then commands 1 x, 2, or 3.
#include <iostream>
#include <stack>
int main() {
int q = 0;
std::cin >> q;
std::stack<long long> history;
long long total = 0;
while (q--) {
int type = 0;
std::cin >> type;
if (type == 1) {
long long amount = 0;
std::cin >> amount;
history.push(amount);
total += amount;
} else if (type == 2) {
if (!history.empty()) {
total -= history.top();
history.pop();
}
} else {
std::cout << total << '\n';
}
}
}Your notes
Mark complete when you can explain it yourself.