fork download
  1. /*
  2. *************************************************************************
  3. * $ Author : honeyslawyer $
  4. * $ Name : shashank gupta $
  5. *************************************************************************
  6. *
  7. * Copyright 2013 @ honeyslawyer and shashank gupta
  8. *
  9. ************************************************************************/
  10. #include<cstdio>
  11. #include<iostream>
  12. #include<cmath>
  13. //#include<conio.h>
  14. #include<cstring>
  15. #include<ctype.h>
  16. #include<algorithm>
  17. #include<vector>
  18. #include<stdlib.h>
  19. #include<map>
  20. #include<queue>
  21. #include<stack>
  22. #include<set>
  23. #include<string>
  24. #include<climits>
  25.  
  26. #define mod 1000000007
  27. #define ll long long
  28.  
  29. using namespace std;
  30. ll gcd(ll a,ll b) {if(b==0) return a; return gcd(b,a%b);}
  31.  
  32. ll power(ll b,ll exp,ll m)
  33. {ll ans=1;
  34. b%=m;
  35. while(exp)
  36. {if(exp&1)
  37. ans=(ans*b)%m;
  38. exp>>=1;
  39. b=(b*b)%m;
  40. }
  41. return ans;
  42. }
  43. int n;
  44. struct node
  45. {
  46. int sum,mini;
  47. node split(node& l, node& r){}
  48. node merge(node& l, node& r)
  49. {
  50. sum=l.sum+r.sum;
  51. mini=min(l.mini,l.sum+r.mini);
  52. }
  53. };
  54. int MAX=1000020;
  55. struct node tree[1000020];
  56. node createleaf(int val)//the leaf nodes, which represent a single element of the array, will be created in this manner
  57. {
  58. node n;
  59. n.sum=n.mini=val;
  60. return n;
  61. }
  62. //range_query and update function remain same as that for last problem
  63. node range_query(int root, int left_most_leaf, int right_most_leaf, int u, int v)
  64. {
  65. //query the interval [u,v), ie, {x:u<=x<v}
  66. //the interval [left_most_leaf,right_most_leaf) is
  67. //the set of all leaves descending from "root"
  68. if(u<=left_most_leaf && right_most_leaf<=v)
  69. return tree[root];
  70. int mid = (left_most_leaf+right_most_leaf)/2,
  71. left_child = root*2,
  72. right_child = left_child+1;
  73. tree[root].split(tree[left_child], tree[right_child]);
  74. node l=createleaf(+30000+1), r=createleaf(30000+1);
  75. //identity is an element such that merge(x,identity) = merge(identity,x) = x for all x
  76. if(u < mid) l = range_query(left_child, left_most_leaf, mid, u, v);
  77. if(v > mid) r = range_query(right_child, mid, right_most_leaf, u, v);
  78. tree[root].merge(tree[left_child],tree[right_child]);
  79. node n;
  80. n.merge(l,r);
  81. return n;
  82. }
  83. void mergeup(int postn)
  84. {
  85. postn >>=1;
  86. while(postn>0)
  87. {
  88. tree[postn].merge(tree[postn*2],tree[postn*2+1]);
  89. postn >>=1;
  90. }
  91. }
  92. void update(int pos)
  93. {
  94. pos+=(1<<n);
  95. tree[pos].sum*=-1;
  96. tree[pos].mini*=-1;
  97. mergeup(pos);
  98. }
  99. int a[100000];
  100. int m;
  101. int create()
  102. {
  103. scanf("%d",&m);
  104. n=(int)log2(double(2*m-1));
  105. string s;
  106. cin>>s;
  107. //cout<<s;
  108. for(int i=0;i<m;i++)
  109. {
  110. if(s[i]=='(')
  111. a[i]=1;
  112. else
  113. a[i]=-1;
  114. }
  115. for(int i=0;i<MAX;i++)
  116. tree[i].mini=tree[i].sum=INT_MAX;
  117.  
  118. for(int i=0; i<(1<<n); i++)
  119. {
  120. //printf("%d %d\n",tree[i].mini,tree[i].sum);
  121. tree[i+(1<<n)] = createleaf(a[i]);
  122. }
  123.  
  124. // update all internal nodes in bottom up fashion
  125. for(int i=(1<<n)-1; i; i--)
  126. tree[i].merge(tree[i*2], tree[i*2+1]);
  127. }
  128.  
  129. int main()
  130. {
  131. //create();
  132. int t=10;
  133. for(int i=1;i<=10;i++)
  134. {
  135. create();
  136. int k;
  137. scanf("%d",&k);
  138. printf("Test %d:\n",i);
  139. while(k--)
  140. {
  141. int p;
  142. scanf("%d",&p);
  143. if(p>0)
  144. {
  145. //new
  146. update(p-1);
  147.  
  148. }
  149. else
  150. {
  151. struct node z=range_query(1,1<<n,1<<(n+1),0,300000+100);
  152. if(z.sum==0&&z.mini==0)
  153. printf("YES\n");
  154. else
  155. printf("NO\n");
  156. }
  157. }
  158. }
  159.  
  160. //getch();
  161. return 0;
  162. /*checklist
  163. 1)getch() and conio.h removed.*/
  164. }
Success #stdin #stdout 0.03s 11680KB
stdin
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
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
stdout
Test 1:
YES
NO
Test 2:
YES
NO
Test 3:
YES
NO
Test 4:
YES
NO
Test 5:
YES
NO
Test 6:
YES
NO
Test 7:
YES
NO
Test 8:
YES
NO
Test 9:
YES
NO
Test 10:
YES
NO