fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define mp make_pair
  5. #define pb push_back
  6. //#pragma comment (linker, "/STACK:256000000")
  7. #define fileio freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
  8. #define boost  ios_base::sync_with_stdio(false);
  9.  
  10. /* Aag ka dariya hai , doob ke jana hai :P */
  11. // vabs
  12.  
  13.  
  14. int seg[100003]={0} , arr[30003]={0} , lazy[100003]={0};
  15. char str[30003];
  16. void build(int node,int x,int y)
  17. {
  18. 	if(x>y)
  19. 		return ;
  20. 	if(x==y)
  21. 	{
  22. 		seg[node] = arr[x];
  23. 		lazy[node] = 0;
  24. 		return ;
  25. 	}
  26. 	build(node*2,x,(x+y)/2);
  27. 	build(node*2+1,(x+y)/2+1,y);
  28. 	seg[node] = min( seg[node*2] , seg[node*2+1] );
  29. 	lazy[node] = 0;
  30. }
  31. /*int query(int node,int x,int y,int i,int j)
  32. {
  33. 	//cout<<i<<"_"<<j<<endl;
  34. 	int p1=0,p2=0,q1=0,q2=0;
  35.  
  36. 	if(x>y||y<i||x>j)
  37. 		return -1;
  38. 	if(lazy[node]!=0)
  39. 	{
  40. 		long long int d = y-x+1;
  41. 		seg[node] += ((d*(d+1))/2) + (lazy[node]-1)*d;
  42. 		if(x!=y)
  43. 		{
  44. 			lazy[node*2] += lazy[node];
  45. 			lazy[node*2+1] += lazy[node] +  (y+x)/2 +1 -x;
  46. 		}
  47. 		lazy[node]=0;
  48. 	}
  49. 	if(x>=i&&y<=j)
  50. 	{
  51.  
  52. 		return seg[node];
  53. 	}
  54.  
  55. 	p1=query(node*2,x,(x+y)/2,i,j);
  56. 	p2=query(node*2+1,(x+y)/2+1,y,i,j);
  57. 	if(p1==-1)
  58. 		return p2;
  59. 	if(p2==-1)
  60. 		return p1;
  61. 	return (p1+p2);
  62. }*/
  63. void update(int node,int x,int y,int i,int j,int v)
  64. {
  65. 	//cout<<node<<"_"<<"_"<<x<<"_"<<y<<"_"<<endl;
  66. 	if(lazy[node]!=0)
  67. 	{
  68. 		seg[node] += lazy[node];
  69. 		if(x!=y)
  70. 		{
  71. 			lazy[node*2] += lazy[node];
  72. 			lazy[node*2+1] += lazy[node] ;
  73. 		}
  74. 		lazy[node]=0;
  75. 	}
  76.  
  77.  
  78. 	if(x>y||y<i||x>j)
  79. 		return ;
  80.  
  81. 	if(x>=i&&y<=j)
  82. 	{
  83. 		//cout<<seg[node]<<endl;	
  84. 		seg[node] += v;
  85. 		if(x!=y)
  86. 		{
  87. 			lazy[node*2] += v;
  88. 			lazy[node*2+1] += v;
  89. 		}
  90.  
  91. 		return ;
  92. 	}
  93. 	update(node*2,x,(x+y)/2,i,j,v);
  94. 	update(1+node*2,(x+y)/2+1,y,i,j,v);
  95.  
  96. 	seg[node]=min( seg[node*2] , seg[node*2+1] );
  97. 	//cout<<seg[node]<<endl;
  98. }
  99. int main()
  100. {
  101. 	int tc,i,x,y,j,k,v,n,sum,u;
  102.  
  103. 	for(u=1;u<=10;u++)
  104. 	{
  105. 		printf("Test %d:\n",u);
  106. 		memset(seg,-1,sizeof(seg));
  107. 		memset(lazy,0,sizeof(lazy));
  108. 		memset(arr,0,sizeof(arr));
  109.  
  110. 		scanf("%d%s%d",&n,str,&k);
  111.  
  112. 		for(i=0;i<n;i++)
  113. 		{
  114. 			arr[i+1] = arr[i] + (str[i] == ')'?-1:1);
  115. 		//	cout<<arr[i+1];
  116. 		}
  117.  
  118. 		build(1,1,n);
  119. 		sum = arr[n];
  120. 		for(i=0;i<k;i++)
  121. 		{
  122. 			cin>>x;
  123. 			//cout<<arr[n]<<endl;
  124. 			//scanf("%c%d%d",&ch,&x,&y);
  125. 			if(x == 0)
  126. 			{
  127. 				x = seg[1];
  128. 				if(x<0 || sum !=0)
  129. 					printf("NO\n");
  130. 				else
  131. 					printf("YES\n");
  132. 			}
  133. 			else
  134. 			{
  135. 				if(str[x-1] == ')')
  136. 				{
  137. 					v = 2;
  138. 					str[x-1] = '(';
  139. 				}
  140. 				else
  141. 				{
  142. 					v =-2;
  143. 					str[x-1] = ')';
  144. 				}
  145. 				sum+=v;
  146. 				update(1,1,n,x,n,v);
  147. 			}
  148.  
  149.  
  150. 			/*for(v=1;v<=10;v++)
  151. 				printf("%d_%d  ",max1[v],max2[v]);
  152. 			cout<<endl;*/
  153.  
  154.  
  155. 		}
  156. 	}
  157. 	return 0;
  158. }
  159.  
Success #stdin #stdout 0s 3616KB
comments (?)
stdin
copy 
4
()((
4
4
0
2
0
stdout
copy 
Test 1:
YES
NO
Test 2:
Test 3:
Test 4:
Test 5:
Test 6:
Test 7:
Test 8:
Test 9:
Test 10:
https://ideone.com/xYqwpY
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!