fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 200005
  7. #define mins 1005
  8. #define eps 0.000000000001
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pll,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32.  
  33.  
  34. int tree[3*maxs],lazy[3*maxs],arr[maxs];
  35. string s;
  36.  
  37. void init(int node,int a,int b){
  38.     if(a>b){
  39.         return;
  40.     }
  41.     if(a==b){
  42.         tree[node]=arr[a];
  43.         return ;
  44.     }
  45.     init(node*2,a,(a+b)/2);
  46.     init(node*2+1,(a+b)/2+1,b);
  47.     tree[node]=min(tree[node*2],tree[node*2+1]);
  48. }
  49.  
  50. void update(int node,int a,int b,int i,int j,int val){
  51.     if(lazy[node]!=0){
  52.         tree[node]+=lazy[node];
  53.         if(a!=b){
  54.             lazy[node*2]+=lazy[node];
  55.             lazy[node*2+1]+=lazy[node];
  56.         }
  57.         lazy[node]=0;
  58.     }
  59.     if(a>b || b<i || a>j){
  60.         return ;
  61.     }
  62.     if(a>=i && b<=j){
  63.         tree[node]+=val;
  64.         if(a!=b){
  65.             lazy[node*2]+=val;
  66.             lazy[node*2+1]+=val;
  67.         }
  68.         return;
  69.     }
  70.     update(node*2,a,(a+b)/2,i,j,val);
  71.     update(node*2+1,(a+b)/2+1,b,i,j,val);
  72.     tree[node]=min(tree[node*2],tree[node*2+1]);
  73. }
  74.  
  75. int query(int node,int a,int b,int i,int j){
  76.     if(a>b || b<i || a>j){
  77.         return imax;
  78.     }
  79.     if(lazy[node]!=0){
  80.         tree[node]+=lazy[node];
  81.         if(a!=b){
  82.             lazy[node*2]+=lazy[node];
  83.             lazy[node*2+1]+=lazy[node];
  84.         }
  85.         lazy[node]=0;
  86.     }
  87.     if(a>=i && b<=j){
  88.         return tree[node];
  89.     }
  90.     int q1=query(node*2,a,(a+b)/2,i,j);
  91.     int q=query(node*2+1,(a+b)/2+1,b,i,j);
  92.     return min(q1,q);
  93. }
  94.  
  95. int main()
  96. {
  97. 	iosbase;
  98. 	int n,i,q,l,r,temp,j,k;
  99. 	cin>>s;
  100. 	n=s.size();
  101. 	for(i=0;i<n;i++){
  102. 		if(s[i]=='('){
  103. 			arr[i]=1;
  104. 		}
  105. 		else{
  106. 			arr[i]=-1;
  107. 		}
  108. 	}
  109. 	for(i=1;i<n;i++){
  110. 		arr[i]+=arr[i-1];
  111. 	}
  112. 	init(1,0,n-1);
  113. 	cin>>q;
  114. 	temp=query(1,0,n-1,0,n-1);
  115. 	for(i=0;i<q;i++){
  116. 		cin>>l>>r;
  117. 		if(s[l]==')' && s[r]=='('){
  118. 			update(1,0,n-1,l,r-1,2);
  119. 		}
  120. 		else if(s[l]=='(' && s[r]==')'){
  121. 			update(1,0,n-1,l,r-1,-2);
  122. 		}
  123. 		swap(s[l],s[r]);
  124. 		temp=query(1,0,n-1,0,n-1);
  125. 		if(temp<0){
  126. 			cout<<"No\n";
  127. 		}
  128. 		else{
  129. 			cout<<"Yes\n";
  130. 		}
  131. 	}
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 8928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3Os3Bo
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!