fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define filenamej "BRCKTS"
  3. #define N 1000001
  4. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  5. #define endl "\n"
  6. using namespace std;
  7.  
  8. int nn, n, m, u, v, t;
  9. char a[N];
  10. char ch;
  11. struct lalala { int l = 0; int r = 0; int wopen = 0; int wclose = 0; } node[4 * N];
  12. int leaf[N];
  13.  
  14. inline void combine(int i)
  15. {
  16.     int dec = min(node[i * 2].wopen, node[i * 2 + 1].wclose);
  17.     node[i].wopen = node[i * 2].wopen - dec + node[i * 2 + 1].wopen;
  18.     node[i].wclose = node[i * 2 + 1].wclose - dec + node[i * 2].wclose;
  19. }
  20.  
  21. void initLR(int i, int x, int y)
  22. {
  23. //    cout << i << ": " << x << " " << y << endl;
  24.     node[i].l = x;
  25.     node[i].r = y;
  26.     if (x == y)
  27.     {
  28.         leaf[x] = i;
  29.         return;
  30.     }
  31.     int mi = (x + y) / 2;
  32.     initLR(i * 2, x, mi);
  33.     initLR(i * 2 + 1, mi + 1, y);
  34. }
  35.  
  36. void build(int i)
  37. {
  38.     if (node[i].l == node[i].r)
  39.     {
  40.         int vtr = node[i].l;
  41.         if (a[vtr] == '(') node[i].wopen = 1;
  42.         else node[i].wclose = 1;
  43.         return;
  44.     }
  45.     build(i * 2);
  46.     build(i * 2 + 1);
  47.     combine(i);
  48. }
  49.  
  50. void update(int i)
  51. {
  52.     a[i] = ch;
  53.     int j = leaf[i];
  54.     if (ch == '(')
  55.     {
  56.         node[j].wopen = 1;
  57.         node[j].wclose = 0;
  58.     }
  59.     else
  60.     {
  61.         node[j].wclose = 1;
  62.         node[j].wopen = 0;
  63.     }
  64.     j /= 2;
  65.     for(; j > 0; j /= 2) combine(j);
  66. }
  67.  
  68. lalala query(int i)
  69. {
  70.     if (node[i].r < u || node[i].l > v) return node[0]; // default
  71.     if (node[i].r <= v && node[i].l >= u) return node[i];
  72.     lalala q1 = query(i * 2);
  73.     lalala q2 = query(i * 2 + 1);
  74.     int dec = min(q1.wopen, q2.wclose);
  75.     lalala res;
  76.     res.wopen = q1.wopen - dec + q2.wopen;
  77.     res.wclose = q2.wclose - dec + q1.wclose;
  78.     return res;
  79. }
  80.  
  81. int main()
  82. {
  83. 	#ifdef filename
  84. 		freopen(filename".inp", "r", stdin);
  85. 		freopen(filename".out", "w", stdout);
  86. 	#endif // filename
  87.  
  88.     int tes = 0;
  89.     while (true)
  90.     {
  91.         tes++;
  92.         n = -1;
  93.         cin >> n;
  94.         if (n == -1) return 0;
  95.         cout << "Test " << tes << ":\n";
  96.         initLR(1, 1, n);
  97.         u = 1;
  98.         v = n;
  99.         FOR(i, 1, n) cin >> a[i];
  100.         build(1);
  101.         cin >> m;
  102.         FOR(i, 1, m)
  103.         {
  104.             cin >> t;
  105.             if (t == 0)
  106.             {
  107.                 lalala ans = query(1);
  108.                 if (ans.wopen == 0 && ans.wclose == 0) cout << "YES\n";
  109.                 else cout << "NO\n";
  110.             }
  111.             else
  112.             {
  113.                 ch = (a[t] == '(') ? ')' : '(';
  114.                 update(t);
  115.             }
  116.         }
  117.     }
  118.  
  119. 	return 0;
  120. }
  121.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin
copy 
2
))
2
1
0
stdout
copy 
Test 1:
YES
https://ideone.com/kaxXjH
language:
C++14 (gcc 8.3)
created:
4 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!