BRCKTS - Brackets

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

  • every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
  • for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets
On a bracket word one can do the following operations:
  • replacement -- changes the i-th bracket into the opposite one
  • check -- if the word is a correct bracket expression


Write a program which

  • reads (from standard input) the bracket word and the sequence of operations performed,
  • for every check operation determines if the current bracket word is a correct bracket expression,
  • writes out the outcome (to standard output).


Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. The first line of a test consists of a single number n (1<=n<=30000) denoting the length of the bracket word. The second line consists of n brackets, not separated by any spaces. The third line consists of a single number m -- the number of operations. Each of the following m lines carries a number k denoting the operation performed. k=0 denotes the check operation, k>0 denotes replacement of k-th bracket by the opposite.


For every test case your program should print a line:
Test i:
where i is replaced by the number of the test and in the following lines, for every check operation in the i-th test your program should print a line with the word YES, if the current bracket word is a correct bracket expression, and a line with a word NO otherwise. (There should be as many lines as check operations in the test.)


[and 9 test cases more]
Test 1:
[and 9 test cases more]

Warning: large Input/Output data, be careful with certain languages

hide comments
yasser1110: 2021-07-27 12:49:39

@abid1729 No. See

yasser1110: 2021-07-27 12:48:50

This was straightforward problem if you can figure out how to merge left and right halves of the string and figure out if its valid or not.
Unfortunately I took a lot of time and many attempts to solve this problem. Lot more than I would have wanted.

sicho_mohit: 2021-07-09 20:20:26

I have tried each and everything , still my code is giving TLE.
Can anyone please help me out.
Thanks in advance.

[NG]: Don't post / link to code in comments, use forum for review or debug.

Last edit: 2021-07-09 21:54:14
wheneveright: 2021-05-27 05:05:07

@lokesh_2052 I think you should find the min sum in the segment tree. For example ))(( is -1 -1 1 1, and it's sum-segment tree is based on -1 -2 -1 0, then find min in the segment tree.

enn, my English isn't well

lokesh_2052: 2021-02-14 16:30:58

I did this in 2.42s. I could not do myself . I find confusion ))(( is right or wrong . this is wrong!!!!!!
If ))(( is right then just '(' is +1 ans ')' -1 and segment tree and upadte query that's all
but ))(( is wrong. So what can I do. This is hard to think where I stuck.

sabal_nrl322: 2020-09-07 04:34:27

Just a simple Segment Tree construction....

yaseenmollik: 2020-08-03 04:58:03

Solved using segment tree. Nice problem!

coolboy7: 2020-07-27 13:24:34

can this question be solved using stack???

jopdhiwaala: 2020-06-11 15:54:47

@abid1729 no its not but when you change the characters at 3 and 4 it becomes correct ()()()

pallindromeguy: 2020-06-07 17:37:13

Use "puts" or "printf".
Using "cout" gave me 10 WA :o

Last edit: 2020-06-07 17:37:24

Added by:Adam Dzedzej
Time limit:11s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Internet Contest Pogromcy Algorytmow(Algorithm Tamers) 2003 Round IV