시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 28 | 17 | 11 | 52.381% |
You are given a boolean expression, consisting of <<0
>>, <<1
>>, operations <<&
>> (boolean "AND"), <<|
>> (boolean "OR"), <<^
>> (<<XOR>>, boolean "exclusive OR"), and parentheses. A correct boolean expression can be defined recursively: an expression is correct, if it is either equal to one character <<0
>> or <<1
>>, or it is an application of some boolean operation to two correct boolean expressions. For simplicity, every application of a boolean operation is put into parentheses. The given expression does not contain spaces or any other characters except the ones described above. For instance, <<((0|1)|0)
>>, <<(0&1)
>> and <<0
>> are correct expressions, and <<0|1
>>, <<0|1&1
>> and <<(0)
>> are not.
Calculate the result of this expression. By the way, the expression is changing! You are also given $m$ queries to change a character at some position. Calculate the value of the given expression after each query.
First line contains string $S$, a correct boolean expression with at most $800\,000$ characters.
Next line contains a single integer $m$ ($1 \le m \le 400\,000$) --- number of queries. Then, $m$ lines follow. Each line contains an integer and a character $p_i$ $c_i$
, meaning that you should change a character at position $p_i$ to $c_i$. It's guaranteed that the expression remains correct after every query.
Output $m+1$ characters <<0
>> or <<1
>> on a single line. First character should be equal to the value of the original expression. Next $m$ characters should be equal to the value of the expression after each query.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $|S| \le 5$, $m \le 10$ |
2 | 10 | $|S| \le 200$, $m \le 200$ |
3 | 20 | $|S| \le 2\,000$, $m \le 2\,000$ |
4 | 25 | $|S| \le 200\,000$, $m \le 100\,000$ |
5 | 35 | $|S| \le 800\,000$, $m \le 400\,000$ |
((1&1)^(0|1)) 3 11 0 7 | 5 0
0110