Informatica Online Judge

  괄호 순열 2 [0950 / 03B6]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 16   Total Tried : 20


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

경곽이는 길이가 n인 괄호 순열을 하나 만들었다.

영재는 경곽이에게 다음과 같은 질문을 했다.

"괄호 순열의 s번째 문자부터 e번째 문자까지 정상적으로 만들어지는 괄호가 몇 개가 있을까?"

이를 해결할 수 있는 프로그램을 작성하시오.

Input

첫 번째 줄에 길이가 n인 "(". ")"로 이루어진 문자열이 입력된다.
두 번째 줄에 영재의 질문의 수 m이 입력된다.
세 번째 줄부터 m줄에 걸쳐서 s_i, e_i가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 1,000,000
1 <= m <= 100,000
1 <= s_i <= e_i <= n ; 1 <= i <= n

Output

각 질문에 대해서 정상적으로 만들 수 있는 괄호를 구성하는 문자의 수를 출력한다.

IO Example

입력
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

출력
0
0
2
10
4
6
6

[설명]
())(())(())(
123456789012

라고 번호를 붙이면

1~1까지는 "(" 이므로 정상적인 괄호가 없다.
2~3은 "))" 이므로 역시 정상적인 괄호를 만들 수 없다.
1~2는 "()" 이므로 2문자를 이용하여 정상적인 괄호를 만들 수 있다.
1~12는 "())(())(())("이므로, ( ) ( ( ) ) ( ( ) )로 10개를 이용하여 만들 수 있다.
8~12는 "(())("이므로 ( ( ) )로 4개를 이용하여 만들 수 있다.
5~11은 "())(())"이므로 ( ) ( ( ) ) 로 6개를 이용하여 만들 수 있다.
2~10은 "))(())(()"이므로 ( ( ) ) ( ) 로 6개를 이용하여 만들 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]