Envíos

4075 - Jules and Parentheses

Criado por Rubén Alcolea Núñez
Adicionado por ymondelo20 (2018-09-05)
Límiteis
Tempo Total: 10000 MS | Tempo Caso: 1000 MS |Memória: 512 MB | Saída límite (mb): 64 MB | Tamanho: 16 KB
Lenguagens activados
Disponivel em

Descripção

Jules is a Computer Science professor who teaches Formal Language Theory at the university. In the first class of the current semester, she defined the concept of balanced parentheses expressions. She explained to her students that a parentheses expression W is balanced if W is the empty string, if W = (W1) or W = W1W2 where W1 and W2 are both balanced expressions. For example, the expressions "(())", "()()", and "(()())" are balanced. However the expressions ")", "))((", and "(()(()" are not balanced.

Today Jules has a new challenge for the students. Given a sequence of 1 ≤ S ≤ 105 parentheses, the cost of changing an open parenthesis (openCost), the cost of changing a closing parenthesis (closeCost), and the number of parentheses that the students can change (K), they need to compute the minimum cost to balance a certain range of a sequence of parentheses. It may also be impossible to balance the range, in which case they should answer "Impossible". In this problem the students can perform two types of queries:
  1. change(pos): change the direction of parenthesis at position 1 ≤ pos ≤ S.
  2. cost(a, b): compute the minimum cost to balance the range [a, b] if it is possible 1 ≤ a ≤ b ≤ S.
Write a program for the students to perform 1 ≤ Q ≤ 2 × 105 queries of type 1 or 2.
Julia es profesora de Ciencias de la Computación y enseña Teoría de Lenguajes Formales en la universidad. En la primera clase del presente semestre, ella definió el concepto de expresiones de paréntesis balanceadas. Ella les explicó a los estudiantes que una expresión de paréntesis W es balanceada si la cadena es vacía, si W = (W1) o W = W1W2, donde W1 y W2 son ambas expresiones balanceadas. Por ejemplo, las expresiones "(())", "()()" y "(()())" son balanceadas. Sin embargo, las expresiones ")," "))((" y "(()(()" no son balanceadas.

Hoy Julia tiene un nuevo desafío para los estudiantes. Dada una secuencia de 1 ≤ S ≤ 100000 paréntesis, el costo de cambiar un paréntesis abierto (openCost), el costo de cambiar un paréntesis cerrado (closeCost), y el número de paréntesis que los estudiantes pueden cambiar (K), ellos necesitan calcular el costo mínimo para balancear un cierto rango de la secuencia de paréntesis si es posible o imprimir "Impossible" en caso contrario. En este problema los estudiantes pueden ejecutar dos tipos de consultas:
  1. change(pos): Cambia la dirección de un paréntesis en una posición 1 ≤ pos ≤ S.
  2. cost(a, b): Calcula el costo mínimo de balancear el rango [a, b] si es posible 1 ≤ a ≤ b ≤ S.
Escriba un programa para que los estudiantes ejecuten 1 ≤ Q ≤ 200000 consultas de tipo 1 o 2
Jules is a Computer Science professor who teaches Formal Language Theory at the university. In the first class of the current semester, she defined the concept of balanced parentheses expressions. She explained to her students that a parentheses expression W is balanced if W is the empty string, if W = (W1) or W = W1W2 where W1 and W2 are both balanced expressions. For example, the expressions "(())", "()()", and "(()())" are balanced. However the expressions ")", "))((", and "(()(()" are not balanced.

Today Jules has a new challenge for the students. Given a sequence of 1 ≤ S ≤ 105 parentheses, the cost of changing an open parenthesis (openCost), the cost of changing a closing parenthesis (closeCost), and the number of parentheses that the students can change (K), they need to compute the minimum cost to balance a certain range of a sequence of parentheses. It may also be impossible to balance the range, in which case they should answer "Impossible". In this problem the students can perform two types of queries:
  1. change(pos): change the direction of parenthesis at position 1 ≤ pos ≤ S.
  2. cost(a, b): compute the minimum cost to balance the range [a, b] if it is possible 1 ≤ a ≤ b ≤ S.
Write a program for the students to perform 1 ≤ Q ≤ 2 × 105 queries of type 1 or 2.

Especificação de entrada

The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.
La entrada contiene en la primera línea la secuencia inicial de paréntesis S, |S| ≤ 100000. La segunda línea contiene el número de consultas Q (1 ≤ Q ≤ 200000), el costo de cambiar un paréntesis abierto openCost (1 ≤ openCost ≤ 1000), el costo de cambiar un paréntesis cerrado closeCost (1 ≤ closeCost ≤ 1000) y el número de paréntesis K (1 ≤ K ≤ 10000) que los estudiantes pueden cambiar. Las siguientes Q líneas tienen la información de cada consulta, tal y como se explicó anteriormente.
The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.

Especificação de saída

For each query of type 2, print the minimum cost to balance the range [a, b] if it is possible. Otherwise print "Impossible" (without the quotes).
Para cada consulta de tipo 2, imprima el costo mínimo de balancear el rango [a, b] si es posible. En caso contrario, imprima la cadena "Impossible" (sin las comillas).
The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.

Exemplo de entrada

((()()()
9 3 2 3
1 2
2 1 8
1 5
1 8
2 2 7
2 5 6
1 7
1 8
2 1 7

Exemplo de saída

0
7
2
Impossible

Sugestões(s)