# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

No gossip. In this problem I will just say what to do. Initially, you will be given a bracket sequence of length N. Then there will be some queries. In each query you will be given two integers l, r (1 ≤ l ≤ r ≤ N). You will have to find the maximum length of balanced bracket substring that starts from index l and ends not after index r. Here substring means a continious sub-part of a string.

In the first line there will be an integer **N** (1 ≤ N ≤ 5×10^{5}). Then there will be a string of length N containing only characters ‘(’ or ‘)’. In next line there will be an integer **Q** (1 ≤ Q ≤ 10^{6}) indicating the number of queries. Then each of the **Q** lines will contain two integers **l** and **r** (1 ≤ l ≤ r ≤ N) as described in statement.

For each query print the maximum length of continuous bracket sequence that is balanced and starts from index l and ends not after index r.

Input | Output |
---|---|

10 ()(())())( 5 1 9 1 1 1 2 9 10 2 5 | 8 0 2 0 0 |

You can learn more about balanced bracket sequence from here.

30% Solution Ratio

EgorKulikovEarliest,

Tashdid_trdbFastest, 0.2s

Tashdid_trdbLightest, 26 MB

Riaz_BSMRSTUShortest, 839B

Login to submit

At first, replace the given bracket sequence by an integer array a. In this array, a[i]=(count of...

Criterion 2020 Round 1 Ended |