fork download
copy 
  1. #!/usr/bin/env python3
  2.  
  3.  
  4. def fillbrackets(start, end, array):
  5.     node = {}
  6.     if start == end:
  7.         node['close'] = 1 if array[start] == ')' else 0
  8.         node['open'] = 1 if array[start] == '(' else 0
  9.     else:
  10.         node['left'] = fillbrackets(start, (end+start)//2, array)
  11.         node['right'] = fillbrackets((end+start)//2 + 1, end, array)
  12.         matched = node['left']['open'] if node['left']['open'] < node['right']['close'] else node['right']['close']
  13.         node['open'] = node['left']['open'] + node['right']['open'] - matched
  14.         node['close'] = node['left']['close'] + node['right']['close'] - matched
  15.     return node
  16.  
  17.  
  18. def updatebrackets(index, start, end, segtr):
  19.     if start == end :
  20.         segtr['open'] ,segtr['close'] = segtr['close'] ,segtr['open'] 
  21.     else:
  22.         if index <= (start+end)//2 :
  23.             updatebrackets(index, start, (start + end)//2, segtr['left'])
  24.         else:
  25.             updatebrackets(index, (start + end)//2 + 1, end, segtr['right'])
  26.         matched = segtr['left']['open'] if segtr['left']['open'] < segtr['right']['close'] else segtr['right']['close']
  27.         segtr['open'] = segtr['left']['open'] + segtr['right']['open'] - matched
  28.         segtr['close'] = segtr['left']['close'] + segtr['right']['close'] - matched
  29.  
  30.  
  31.  
  32. def checkbrackets(segtr):
  33.     return 'YES' if segtr['open'] == 0 and segtr['close']==0 else 'NO'
  34.  
  35. for cases in range(10):
  36.     print('Test %d:' % int(cases + 1))
  37.     brlength = int(input())
  38.     brackets = input()
  39.     oplength = int(input())
  40.     segtree = fillbrackets(0, brlength-1, brackets)
  41.     #print(segtree)
  42.     for i in range(oplength):
  43.         operation = int(input())
  44.         if operation == 0:
  45.             print(checkbrackets(segtree))
  46.         else:
  47.             updatebrackets(operation-1, 0, brlength-1, segtree)
  48.             #print(segtree)
  49.  
Success #stdin #stdout 0.01s 9992KB
comments (?)
stdin
copy 
4
()((
4
4
0
2
0
4
()((
4
4
0
2
0
4
()((
4
4
0
2
0
4
()((
4
4
0
2
0
4
()((
4
4
0
2
0
16
((()()))()()((()
6
0
14
0
13
14
0
4
()(())
1
0
6
())(()
4
0
3
4
0
48
()()()((((()))(()()()))))((((()))((((((())()()))
3
0
40
0
12
(((())()()))
5
0
9
0
8
0
stdout
copy 
Test 1:
YES
NO
Test 2:
YES
NO
Test 3:
YES
NO
Test 4:
YES
NO
Test 5:
YES
NO
Test 6:
NO
YES
NO
Test 7:
NO
Test 8:
NO
YES
Test 9:
NO
NO
Test 10:
YES
NO
YES
https://ideone.com/P0JZpY
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!