Matched Brackets 2

Zonal Computing Olympiad 2012, 26 Nov 2011
We consider sequences of opening and closing brackets with two types of brackets, () and []. A bracket sequence is wellbracketed if we can pair up each opening bracket with a matching closing bracket in the usual sense. For instance, the sequences (), [] ([]) and []([]) are wellbracketed, while (, ()], (], )( and [(]) are not wellbracketed. In the last case, each opening bracket has a matching closing bracket and vice versa, but the intervals spanned by the different types of brackets intersect each other instead of being contained one within the other.
The alternating depth of a wellbracketed sequence tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets. For instance, the alternating depth of (), [] and ()[][] is 1, the alternating depth of [()] and ()([]) is 2, the alternating depth of ([()]) and [()][(([]))] is 3, and so on.
Given a wellbracketed sequence, we are interested in computing three quantities.
 The alternating depth of the sequence.
 The maximum number of symbols between any pair of matched brackets of the type ( and ), including both the outer brackets.
 The maximum number of symbols between any pair of matched brackets of the type [ and ], including both the outer brackets.
For instance, the alternating depth of (([]))[()] is 2, the maximum number of symbols between a matched pair () is 6 and the maximum number of symbols between a matched pair [] is 8.
Input format
The input consists of two lines. The first line is a single integer N, the length of the bracket sequence. Positions in the sequence are numbered 1,2,…,N. The second line is a sequence of N spaceseparated integers that encode the bracket expression as follows: 1 denotes an opening bracket (, 2 denotes a closing bracket ), 3 denotes an opening bracket [ and 4 denotes a closing bracket ]. Nothing other than 1, 2, 3 or 4 appears in the second line of input and the corresponding expression is guaranteed to be wellbracketed.
Output format
Your program should print 3 spaceseparated integers in a line, denoting the three quantities asked for in the following order: alternating depth, length of the maximum sequence between matching () brackets and length of the maximum sequence between matching [] brackets.
Testdata
You may assume that 2 ≤ N ≤ 10^{5}. In 30% of the test cases, 2 ≤ N ≤ 10^{3}.
 Subtask 1 (30 marks)
 Subtask 2 (70 marks)
Sample Input
14 1 1 3 4 2 2 3 3 3 1 2 4 4 4
Sample Output
2 6 8
Author:  admin3 
Date Added:  2112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions