23711번 - Ivan Smirnov 다국어

https://stackoverflow.com/questions/45658828/number-of-ways-to-merge-2-parenthesis-sequences. Now you can solve a strictly harder problem in about $10^{18}$ years. This almost fits in the time limit. All you have to do is some minor optimizations.

Two sequences of parentheses $s$ and $t$ mergeable if they can be interleaved to form a balanced parentheses sequence. Formally, if $s$ has length $n$ and $t$ has length $m$ they are mergeable if and only if there exists a balanced parentheses sequence $p$ of length $n + m$, and two disjoint sequences of indices $a$ and $b$ of length $n$ and $m$ respectively, such that:

1. $0 \leq a_1 < a_2 < \ldots < a_n < n + m$
2. $0 \leq b_1 < b_2 < \ldots < b_m < n + m$
3. For all $i$ $p_{a_i} = s_i$
4. For all $i$ $p_{b_i} = t_i$

The RLE (Run Length Encoding) of some string is a list of pairs $(c_i, a_i)$ where $c_i$ is a character and $a_i$ is a positive integer and $\forall_i c_i \neq c_{i+1}$, the length of the encoding (i.e. number of pairs in the list) is called the run length of the string. The original string of RLE $[(c_1, a_1), (c_2, a_2), \ldots, (c_n, a_n)]$ consists of $a_1$ repetitions of character $c_1$, followed by $a_2$ repetitions of character $c_2$, and so on, and ends with $a_n$ repetitions of character $c_n$. It can be shown that RLE is unique.

You are given an RLE of a parentheses sequence $s$ and RLEs of $m$ other parentheses sequences candidates $t_i$.

For each $i$ find out if $t_i$ and $s$ are mergeable.

The input starts with a description of the sequence $s$. The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$), the run length of $s$.

$n$ lines follow. $i$-th of them describes a single pair in the RLE of $s$ and contains a character $c_i$ and an integer $a_i$ separated by a single space ($c_i \in \{ (, ) \}, c_i \neq c_{i+1}, 1 \leq a_i \leq 10^{12}$).

The next line contains a single integer $m$ ($1 \leq n \leq 3 \cdot 10^5$), the number of sequences $t$ to check.

The remaining lines describe those sequences one by one, using the same format as the description of $s$. If this isn't clear you should take a look at the samples.

It is guaranteed that the sum of run lengths of those $m$ sequences doesn't exceed $3 \cdot 10^5$. 

Print $m$ lines.

The $i$-th of those lines should contain 1 if $t_i$ and $s$ are mergeable and 0 if they are not.