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. 	void initialize(char val){
  20. 	    if(val=='('){
  21. 	        open=1;
  22. 	        close=0;
  23. 	    }
  24. 	    else{
  25. 	        open=0;
  26. 	        close=1;
  27. 	    }
  28. 	}
  29. 	void merge(node &A,node &B){
  30. 	    int mn=min(A.open,B.close);
  31. 	    open=A.open+B.open-mn;
  32. 	    close=B.close+A.close-mn;
  33. 	}
  34. }st[MAX];
  35. string arr;
  36. void init(int idx,int l,int r){
  37. 	if(l==r){
  38. 			st[idx].initialize(arr[l]);
  39. 		    return;
  40. 	}
  41. 	{
  42. 		int m=(l+r)/2;
  43. 		init(idx*2+1,l,m);
  44. 		init(idx*2+2,m+1,r);
  45. 		st[idx].merge(st[idx*2+1],st[idx*2+2]);
  46. 	}
  47. }
  48.  
  49. void update(int idx,int l,int r,int i,char val){
  50. 	if(l==r && l==i){
  51. 		st[idx].initialize(val);
  52. 		return;
  53. 	}
  54. 	else{
  55. 		int m=(l+r)/2;
  56. 		if(i<=m)
  57. 			update(idx*2+1,l,m,i,val);
  58. 		else if(i>m)
  59. 			update(idx*2+2,m+1,r,i,val);
  60. 		st[idx].merge(st[idx*2+1],st[idx*2+2]);
  61. 	}
  62. }
  63.  
  64. int main() {
  65.       ios_base::sync_with_stdio(false);
  66.       cin.tie(NULL);
  67. 	for(int t=0;t<10;t++){
  68. 		int n;
  69. 		cin>>n;
  70. 		arr.clear();
  71. 		memset(st,0,sizeof(st));
  72. 		cin>>arr;
  73. 	//	cout<<arr<<endl;
  74. 		init(0,0,n-1);				//Initialise tree
  75. 		int q;
  76. 		cin>>q;
  77. 		cout<<"Test "<<t+1<<':'<<endl;
  78. 		while(q--){
  79. 		   // cout<<"c"<<endl;
  80. 			int f;
  81. 			cin>>f;
  82. 			if(f==0){
  83. 				if(!st[0].open && !st[0].close)				//query node
  84. 					cout<<"YES"<<endl;
  85. 				else
  86. 					cout<<"NO"<<endl;
  87. 			}
  88. 			else{
  89. 				if(arr[f-1]=='(')
  90. 					update(0,0,n-1,f-1,')');					 //update node
  91. 				else
  92. 					update(0,0,n-1,f-1,'(');
  93. 			}
  94. 		}
  95. 	}
  96. 	//cout<<"Execution time : "<<tick();
  97.       return 0;
  98. }
  99.  
Time limit exceeded #stdin #stdout 5s 23880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test 1:
https://ideone.com/cm6j8F
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!