fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. using namespace std;
  5. char str[40010];
  6. struct node
  7. {
  8. 	int sum;
  9. 	int minsum;
  10. }tree[1000005];
  11. void build(int id,int l,int r)
  12. {
  13. 	if(r-l<2)
  14. 	{
  15. 		if(str[l] == '(')
  16. 		{
  17. 			tree[id].sum = 1;
  18. 			tree[id].minsum = 1;
  19. 		}
  20. 		else
  21. 		{
  22. 			tree[id].sum = -1;
  23. 			tree[id].minsum = -1;
  24. 		}
  25. 		return;
  26. 	}
  27. 	int mid = (r+l)/2;
  28. 	build(id*2,l,mid);
  29. 	build(id*2+1,mid,r);
  30. 	tree[id].sum = tree[id*2].sum + tree[id*2+1].sum;
  31. 	tree[id].minsum = min(tree[id*2].minsum,tree[id*2].minsum+tree[id*2+1].minsum);
  32. }
  33. void modify(int index,int id,int l,int r)
  34. {
  35. 	if(r-l<2)
  36. 	{
  37. 		tree[id].sum = tree[id].minsum = -tree[id].sum;
  38. 		return;
  39. 	}
  40. 	int mid = (r+l)/2;
  41. 	if(index<mid)
  42. 	modify(index,id*2,l,mid);
  43. 	else
  44. 	modify(index,id*2+1,mid,r);
  45. 	tree[id].sum = tree[id*2].sum + tree[id*2+1].sum;
  46. 	tree[id].minsum = min(tree[id*2].minsum,tree[id*2].minsum+tree[id*2+1].minsum);
  47. }
  48. int main()
  49. {
  50. 	int n,k;
  51. 	int val;
  52. 	int h = 1;
  53. 	for(int h=1;h<=10;h++)
  54. 	{
  55. 		scanf("%d",&n);
  56. 		scanf("%s",str);
  57. 		build(1,0,n);
  58. 		//cout<<"Test "<<h<<" :"<<endl;
  59. 		printf("Test %d:\n",h);
  60. 		//cin>>k;
  61. 		scanf("%d",&k);
  62. 		while(k--)
  63. 		{
  64. 			cin>>val;
  65. 			if(!val)
  66. 			{
  67. 				if(tree[1].sum == 0 && tree[1].minsum == 0)
  68. 				{
  69. 					//cout<<"YES"<<endl;
  70. 					printf("YES\n");
  71. 				}
  72. 				else
  73. 				{
  74. 					//cout<<"NO"<<endl;
  75. 					printf("NO\n");
  76. 				}
  77. 				//cout<<tree[1].sum<<"------------"<<tree[1].minsum<<endl;
  78. 			}
  79. 			else
  80. 			{
  81. 				modify(val-1,1,0,n);
  82. 			}
  83. 		}
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 10544KB
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
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
copy 
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
https://ideone.com/DkrwIg
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 years ago
visibility:
public

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!