Emacs++

2016의 Distributed Code Jam에서, 괄호 밀도가 더 높은 것을 선호하는 Lisp 팬들을 위해 Lisp++ 언어를 소개했다. 이 언어의 문법이 어떻게 작동하는지 다시 살펴보자.

Lisp++ 프로그램은 균형 잡힌 괄호로 이루어진 문자열이다. 더 형식적으로 말하면, Lisp++ 프로그램은 다음 중 하나로 구성된다. (이 명세에서 C는 어떤 프로그램 코드를 나타내며, 매번 같은 코드일 필요는 없다.)

• () 말 그대로 여는 괄호 하나와 닫는 괄호 하나뿐이다. 이 (가 이 )와 짝을 이루며, 그 반대도 마찬가지라고 한다.

• (C) 한 쌍의 둘러싸는 괄호 안에 있는 프로그램이다. 이 (가 이 )와 짝을 이루며, 그 반대도 마찬가지라고 한다.

• CC 두 프로그램을 (반드시 서로 같을 필요는 없이) 연달아 놓은 것이다.

올해는 Lisp++용 텍스트 뷰어인 Emacs++를 발표하게 되어 기쁘다. Emacs++는 길이가 K인 Lisp++ 프로그램을 커서를 움직일 수 있는 하나의 긴 줄로 표시한다. 커서는 문자 사이가 아니라 항상 프로그램의 K개 문자 중 하나 위에 위치하는 "블록 커서"이다.

언제든지 다음 세 가지 동작 중 하나를 수행하여 커서를 움직일 수 있다. (i는 커서의 현재 위치를 나타내며, 가장 왼쪽 위치를 1부터 세어 정한다.)

• 커서를 한 문자 왼쪽으로 이동한다. (단, 커서가 이미 가장 왼쪽 문자 위에 있으면 아무 일도 일어나지 않는다.) 이 동작에는 $L_{i}$초가 걸린다.

• 커서를 한 문자 오른쪽으로 이동한다. (단, 커서가 이미 가장 오른쪽 문자 위에 있으면 아무 일도 일어나지 않는다.) 이 동작에는 $R_{i}$초가 걸린다.

• i번째 문자인 괄호와 (위에서 설명한 대로) 짝을 이루는 괄호로 커서를 순간 이동한다. 이 동작에는 $P_{i}$초가 걸린다.

Emacs++는 숙련 사용자에게 간단할 것이라고 생각하지만, 얼마나 효율적인지는 여전히 파악해야 한다. 하나의 Lisp++ 프로그램과 그 프로그램에 관한 Q개의 질의 목록이 있으며, 각 질의는 시작 위치 $S_{j}$와 끝 위치 $E_{j}$로 구성된다. j번째 질의에 답하려면, 최적으로 결정할 때 커서를 위치 $S_{j}$에서 위치 $E_{j}$로 옮기는 데 걸리는 가능한 최소 시간 $N_{j}$(초)을 구해야 한다.

그러한 모든 $N_{j}$ 값의 합을 출력하라.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 최대 9개의 테스트 케이스에 대해 K = $10^{5}$이고 Q = $10^{5}$이다. 그 밖의 모든 경우에는 2 ≤ K ≤ 1000이고 1 ≤ Q ≤ 1000이다. P의 길이 = K P는 위에서 설명한 균형 잡힌 괄호 문자열이다. 모든 j에 대해 1 ≤ $S_{j}$ ≤ K이다. 모든 j에 대해 1 ≤ $E_{j}$ ≤ K이다.

테스트 세트 1 (결과 공개)

모든 i에 대해 $L_{i}$ = 1이다. 모든 i에 대해 $R_{i}$ = 1이다. 모든 i에 대해 $P_{i}$ = 1이다.

테스트 세트 2 (결과 비공개)

모든 i에 대해 1 ≤ $L_{i}$ ≤ $10^{6}$이다. 모든 i에 대해 1 ≤ $R_{i}$ ≤ $10^{6}$이다. 모든 i에 대해 1 ≤ $P_{i}$ ≤ $10^{6}$이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 Lisp++ 프로그램의 길이인 정수 K와 질의 수인 정수 Q가 주어진다.

각 테스트 케이스의 둘째 줄에는 K개 문자로 이루어진 문자열 P가 주어진다. 각 문자는 ( 또는 )이며, P는 위에서 설명한 Lisp++ 프로그램(균형 잡힌 괄호 문자열)을 나타낸다.

각 테스트 케이스의 셋째 줄, 넷째 줄, 다섯째 줄에는 각각 K개의 정수가 주어진다. 이 줄들의 i번째 정수는 각각 위에서 설명한 값 $L_{i}$, $R_{i}$, $P_{i}$이다.

각 테스트 케이스의 여섯째 줄과 일곱째 줄에는 각각 Q개의 정수가 주어진다. 이 줄들의 j번째 정수는 각각 위에서 설명한 $S_{j}$와 $E_{j}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 (1부터 시작하는) 테스트 케이스 번호이고, y은 위에서 설명한 $N_{j}$ 값들의 합이다.

테스트 세트 1의 제한을 따르는 예제에서는 모든 시간 비용이 같다(이동당 1초). 각 질의의 최단 시간은 다음과 같다.

• 7에서 오른쪽으로 다섯 번 이동하여 12에 도달하며, 5초가 걸린다.

• 4에서 11로 순간 이동하며, 1초가 걸린다.

• 4에서 11로 순간 이동한 다음, 왼쪽으로 이동하여 10에 도달하며, 2초가 걸린다.

• 12에서 1로 순간 이동하며, 1초가 걸린다.

• 5에서 6로 오른쪽으로 이동하며, 1초가 걸린다.

따라서 질의 시간의 합은 5+1+2+1+1 = 10초이다.