fork(1) download
copy 
  1. /*
  2. *DIV 2 C.
  3. *LINK:
  4. *nilabja10201992
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define inf (1<<30)
  10. #define INF (int)1e9
  11. #define EPS 1e-9
  12. #define PI 3.1415926535897932384626433832795
  13. #define MOD 1000000007
  14. #define MAX 1000000
  15.  
  16. struct node{
  17. 	int open;
  18. 	int close;
  19.  
  20. 	void initialize(char val){
  21. 	    if(val=='('){
  22. 	        open=1;
  23. 	        close=0;
  24. 	    }
  25. 	    else{
  26. 	        open=0;
  27. 	        close=1;
  28. 	    }
  29. 	}
  30. 	void merge(node &A,node &B){
  31. 	    int mn=min(A.open,B.close);
  32. 	    open=A.open-mn+B.open;
  33. 	    close=B.close+A.close-mn;
  34. 	}
  35. }st[MAX];
  36. string arr;
  37. void init(int idx,int l,int r){
  38. 	if(l==r){
  39. 			st[idx].initialize(arr[l]);
  40. 		    return;
  41. 	}
  42. 	else {
  43. 		int m=(l+r)/2;
  44. 		init(idx*2+1,l,m);
  45. 		init(idx*2+2,m+1,r);
  46. 		st[idx].merge(st[idx*2+1],st[idx*2+2]);
  47. 	}
  48. }
  49.  
  50. void update(int idx,int l,int r,int i,char val){
  51. 	if(l==r && l==i){
  52. 		st[idx].initialize(val);
  53. 		return;
  54. 	}
  55. 	else{
  56. 		int m=(l+r)/2;
  57. 		if(i<=m)
  58. 			update(idx*2+1,l,m,i,val);
  59. 		if(i>m)
  60. 			update(idx*2+2,m+1,r,i,val);
  61. 		st[idx].merge(st[idx*2+1],st[idx*2+2]);
  62. 	}
  63. }
  64.  
  65. int main() {
  66.       ios_base::sync_with_stdio(false);
  67.       cin.tie(NULL);
  68. 	for(int t=0;t<10;t++){
  69. 		int n;
  70. 		cin>>n;
  71. 		arr.clear();
  72. 		memset(st,0,sizeof(st));
  73. 		cin>>arr;
  74. 	//	cout<<arr<<endl;
  75. 		init(0,0,n-1);				//Initialise tree
  76. 		int q;
  77. 		cin>>q;
  78. 		cout<<"Test "<<t+1<<':'<<endl;
  79. 		while(q--){
  80. 		   // cout<<"c"<<endl;
  81. 			int f;
  82. 			cin>>f;
  83. 			if(f==0){
  84. 				if(!st[0].open && !st[0].close)				//query node
  85. 					cout<<"YES"<<endl;
  86. 				else
  87. 					cout<<"NO"<<endl;
  88. 			}
  89. 			else{
  90. 				if(arr[f-1]=='(')
  91. 					arr[f-1]=')';
  92. 				else
  93. 					arr[f-1]='(';
  94. 				update(0,0,n-1,f-1,arr[f-1]);					 //update node
  95. 			}
  96. 		/*	for(int i=0;i<n<<1;i++)
  97. 				cout<<st[i].open<<" "<<st[i].close<<" "<<i<<endl;
  98. 			cout<<endl;*/
  99. 		}
  100. 	}
  101. 	//cout<<"Execution time : "<<tick();
  102.       return 0;
  103. }
  104.  
Success #stdin #stdout 0s 23056KB
comments (?)
stdin
copy 
6
()))()
7
4
6
6
5
0
3
0
stdout
copy 
Test 1:
NO
YES
https://ideone.com/4435ID
language:
C++14 (gcc 8.3)
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!