Emacs++

2016년 Distributed Code Jam에서 괄호를 촘촘하게 쓰는 Lisp 애호가를 위해 Lisp++ 언어를 소개했습니다. 문법을 다시 정리하면 다음과 같습니다.

Lisp++ 프로그램은 짝이 맞는 괄호 문자열입니다. 정확히는 다음 중 하나입니다. 이 명세에서 $C$는 어떤 프로그램 코드든 뜻하며, 매번 같은 코드일 필요는 없습니다.

• () 여는 괄호 하나와 닫는 괄호 하나입니다. 이 (와 )는 서로 짝을 이룹니다.
• ($C$) 프로그램을 한 쌍의 괄호로 감싼 것입니다. 이 (와 )는 서로 짝을 이룹니다.
• $CC$ 두 프로그램을 이어 붙인 것입니다. 두 프로그램은 같지 않아도 됩니다.

올해는 Lisp++용 텍스트 뷰어인 Emacs++를 발표합니다. Emacs++는 길이 $K$인 Lisp++ 프로그램을 한 줄로 보여 주고, 사용자가 움직일 수 있는 커서를 함께 표시합니다. 커서는 블록 커서이며, 항상 $K$개 문자 중 하나의 위에 놓입니다. 두 문자 사이에 놓이지 않습니다.

언제든지 다음 세 동작 중 하나로 커서를 움직일 수 있습니다. $i$는 커서의 현재 위치이며, 가장 왼쪽 문자를 1번으로 셉니다.

• 커서를 한 칸 왼쪽으로 옮깁니다. 이미 가장 왼쪽 문자에 있으면 아무 일도 일어나지 않습니다. 소요 시간은 $L_i$초입니다.
• 커서를 한 칸 오른쪽으로 옮깁니다. 이미 가장 오른쪽 문자에 있으면 아무 일도 일어나지 않습니다. 소요 시간은 $R_i$초입니다.
• 커서를 $i$번째 문자와 짝을 이루는 괄호 위치로 순간 이동합니다. 소요 시간은 $P_i$초입니다.

Emacs++가 얼마나 효율적인지 알아볼 필요가 있습니다. 프로그램은 하나이고, 그 프로그램에 대한 $Q$개의 질의가 있습니다. 각 질의는 시작 위치 $S_j$와 끝 위치 $E_j$로 이루어집니다. $j$번째 질의마다, 최적의 선택을 했을 때 커서를 $S_j$에서 $E_j$로 옮기는 데 드는 가장 짧은 시간 $N_j$(초)를 구하십시오.

모든 $N_j$의 합을 출력하십시오.

첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다. 이어서 테스트 케이스가 나옵니다.

각 테스트 케이스의 첫 줄에는 Lisp++ 프로그램의 길이 $K$와 질의의 개수 $Q$가 정수로 주어집니다.

둘째 줄에는 길이 $K$의 문자열 $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 \le T \le 100$
• $K = 10^5$이고 $Q = 10^5$인 테스트 케이스는 최대 9개입니다.
• 그 밖의 모든 경우에는 $2 \le K \le 1000$이고 $1 \le Q \le 1000$입니다.
• $P$의 길이는 $K$이며, $P$는 위에서 설명한 짝이 맞는 괄호 문자열입니다.
• 모든 $j$에 대해 $1 \le S_j \le K$입니다.
• 모든 $j$에 대해 $1 \le E_j \le K$입니다.

테스트 세트 1의 제한을 따르는 예시에서는 모든 이동이 1초씩 걸립니다. 질의별 최단 시간은 다음과 같습니다.

1. 7에서 12까지 오른쪽으로 다섯 번 이동하며, 5초가 걸립니다.
2. 4에서 11로 순간 이동하며, 1초가 걸립니다.
3. 4에서 11로 순간 이동한 뒤 10까지 왼쪽으로 이동하며, 2초가 걸립니다.
4. 12에서 1로 순간 이동하며, 1초가 걸립니다.
5. 5에서 6으로 오른쪽으로 이동하며, 1초가 걸립니다.

질의 시간의 합은 5 + 1 + 2 + 1 + 1 = 10초입니다.