Forbidden Value
Contest: Educational Codeforces Round 99 (Rated for Div. 2)
Difficulty rating: 2900
Tags: data structures, dp

Polycarp is editing a complicated computer program. First, variable $$$x$$$ is declared and assigned to $$$0$$$. Then there are instructions of two types:

1. set $$$y$$$ $$$v$$$ — assign $$$x$$$ a value $$$y$$$ or spend $$$v$$$ burles to remove that instruction (thus, not reassign $$$x$$$);
2. if $$$y$$$ $$$\dots$$$ end block — execute instructions inside the if block if the value of $$$x$$$ is $$$y$$$ and ignore the block otherwise.

if blocks can contain set instructions and other if blocks inside them.

However, when the value of $$$x$$$ gets assigned to $$$s$$$, the computer breaks and immediately catches fire. Polycarp wants to prevent that from happening and spend as few burles as possible.

What is the minimum amount of burles he can spend on removing set instructions to never assign $$$x$$$ to $$$s$$$?

Input format:
The first line contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le s \le 2 \cdot 10^5$$$) — the number of lines in the program and the forbidden value of $$$x$$$.

The following $$$n$$$ lines describe the program. Each line is one of three types:

1. set $$$y$$$ $$$v$$$ $$$(0 \le y \le 2 \cdot 10^5, 1 \le v \le 10^9)$$$;
2. if $$$y$$$ $$$(0 \le y \le 2 \cdot 10^5)$$$;
3. end.

Each if instruction is matched by an end instruction. Each end instruction has an if instruction to match.

Output format:
Print a single integer — the minimum amount of burles Polycarp can spend on removing set instructions to never assign $$$x$$$ to $$$s$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 1
set 1 10
set 2 15
if 2
set 1 7
end

Example output:
17

Example input:
7 2
set 3 4
if 3
set 10 4
set 2 7
set 10 1
end
set 4 2

Example output:
4

Editorial:
Consider the following dynamic programming. $$$dp_{ij}$$$ — the minimum cost to make $$$x$$$ have value $$$j$$$ after the $$$i$$$-th line. The transitions here are pretty easy: on set you just consider two options of skipping or not skipping the instructions and on if you either go to the next line or to the end of the block depending on the value.
There are a lot of possible values, so that dp works in $$$O(n^2)$$$. First, let's notice that all the values that don't appear in the input won't matter, so you can keep only the existing values in the dp.
Next, let's consider the following modification to it. What happens when you enter an if block? It's actually the same dp but the only starting value is not $$$0$$$ with cost $$$0$$$ as in the beginning of the whole program but some value $$$y$$$ with some cost $$$c$$$. So let's calculate this dp separately from the outer one and just merge the values together. Notice that if some value doesn't appear inside the if block then its cost can not decrease exiting out of it. Thus, it's enough to calculate the inner dp only for values that appear inside the if block.
Okay, the transitions for if became easier. The set transitions are still slow, though. Examine the nature of them. All the values besides the $$$y$$$ written on the set instruction increase their cost by $$$v$$$. As for the $$$y$$$, its cost becomes equal to the cost of the cheapest value before the instruction.
Thus, let's maintain the dp in some data structure that allows to add the same integer to all elements and take the minimum of its elements. That can be done with a set and a single integer that stores the current shift that should be applied to all elements. Surely, you'll also need a map to retrieve the current cost of particular values.
The final part is fast merging of the if block dp and the outer one. It might not appear obvious but if you do that in a straightforward manner of adding all the costs from if one by one it can become $$$O(n^2)$$$ in total. So we can apply small-to-large and swap these dp's based on their sizes.
Overall complexity: $$$O(n \log^2 n)$$$.