fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define inf 1e18
  4. #define iosbase ios_base::sync_with_stdio(false);
  5. #define mp make_pair
  6. #define pb push_back
  7. #define MOD 1000000007
  8. #define sc(n) scanf("%lld" , &n);
  9. #define Max 500005
  10. using namespace std;
  11.  
  12. ll arr[Max];
  13. ll lazy[Max];
  14. int tree[4*Max];
  15.  
  16. void build_tree(int node, int a, int b) {
  17.     if(a > b) return;
  18.  
  19.   	if(a == b) {
  20.     		tree[node] = arr[a];
  21. 		return;
  22. 	}
  23.  
  24. 	build_tree(node*2, a, (a+b)/2);
  25. 	build_tree(node*2+1, 1+(a+b)/2, b);
  26.  
  27. 	tree[node] = min(tree[node*2], tree[node*2+1]);
  28. }
  29.  
  30.  
  31. void update_tree(int node, int a, int b, int i, int j, int value) {
  32.  
  33. 	if(lazy[node] != 0) {
  34.    		tree[node] += lazy[node];
  35.  
  36. 		if(a != b) {
  37. 			lazy[node*2] += lazy[node];
  38.     			lazy[node*2+1] += lazy[node];
  39. 		}
  40.  
  41.    		lazy[node] = 0; // Reset it
  42.   	}
  43.  
  44. 	if(a > b || a > j || b < i)
  45. 		return;
  46.  
  47.   	if(a >= i && b <= j) {
  48.     		tree[node] += value;
  49.  
  50. 		if(a != b) {
  51. 			lazy[node*2] += value;
  52. 			lazy[node*2+1] += value;
  53. 		}
  54.  
  55.     		return;
  56. 	}
  57.  
  58. 	update_tree(node*2, a, (a+b)/2, i, j, value);
  59. 	update_tree(1+node*2, 1+(a+b)/2, b, i, j, value);
  60.  
  61. 	tree[node] = min(tree[node*2], tree[node*2+1]);
  62. }
  63.  
  64. int query_tree(int node, int a, int b, int i, int j) {
  65.  
  66. 	if(a > b || a > j || b < i) return inf;
  67.  
  68. 	if(lazy[node] != 0) {
  69. 		tree[node] += lazy[node];
  70.  
  71. 		if(a != b) {
  72. 			lazy[node*2] += lazy[node];
  73. 			lazy[node*2+1] += lazy[node];
  74. 		}
  75.  
  76. 		lazy[node] = 0;
  77. 	}
  78.  
  79. 	if(a >= i && b <= j)
  80. 		return tree[node];
  81.  
  82. 	int q1 = query_tree(node*2, a, (a+b)/2, i, j);
  83. 	int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j);
  84.  
  85. 	int res = min(q1, q2);
  86.  
  87. 	return res;
  88. }
  89.  
  90. int main()
  91. {
  92. 	iosbase
  93. 	string s="";
  94. 	cin>>s;
  95. 	ll size = s.size();
  96. 	ll open =0 , close = 0;
  97.  
  98. 	for(int i=0 ; i<s.size() ; i++){
  99. 		if(s[i]=='(')open++;
  100. 		else close++;
  101.  
  102. 		arr[i] = open - close;
  103. 	}
  104.  
  105.     build_tree(1,0,size-1);
  106.  
  107. 	ll q;
  108. 	cin>>q;
  109.  
  110.  
  111. 	while(q--)
  112. 	{
  113. 		ll a ,b;
  114. 		cin>>a>>b;
  115.  
  116. 		if(s[a]==s[b]){
  117. 			if(query_tree(1,0,size-1,size-1,size-1)==0 && query_tree(1,0,size-1,0,size-1)>=0){
  118. 			cout<<"Yes\n";
  119. 			}
  120. 			else{
  121. 			cout<<"No\n";
  122. 			}
  123. 			continue;
  124.  
  125.  
  126. 		}
  127. 		else if(s[a]=='(' && s[b]==')'){
  128. 			update_tree(1,0,size-1, a, b-1 , -2);
  129. 		}
  130. 		else{
  131. 			update_tree(1,0,size-1, a, b-1 , +2);
  132. 		}
  133.  
  134. 		if(query_tree(1,0,size-1,a,b-1)>=0 && query_tree(1,0,size-1,size-1,size-1)==0 && query_tree(1,0,size-1,0,size-1)>=0){
  135.  
  136.  
  137. 			cout<<"Yes\n";
  138. 		}
  139. 		else{
  140.  
  141. 			cout<<"No\n";
  142. 		}
  143. 		swap(s[a],s[b]);
  144.  
  145. 	}
  146.  
  147. 	return 0;
  148. }
Runtime error #stdin #stdout 0s 19040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C5qaQ6
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!