fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long int
  6. #define NN 300005
  7. #define pb push_back
  8. #define mp make_pair
  9. #define INF (((ll)1000000000) * ((ll)1000000000))
  10. #define inf 0x7fffffff
  11. #define inff 100000
  12. #define ff first
  13. #define ss second
  14. #define MOD 1000000007
  15. #define fast cin.sync_with_stdio(0);cin.tie(0)
  16. #define rep(i,N) for(int i=0;i<N;i++)
  17. #define frep(i,a,b) for(int i=a;i<=b;i++)
  18. #define pii pair<int,int>
  19. #define fill(A,v) memset(A,v,sizeof(A))
  20. #define setbits(x) __builtin_popcount(x)
  21. #define print(A,j,k) for(int ii=j;ii<=k;ii++)cout<<A[ii]<<" ";cout<<"\n"
  22. #define all(x) (x).begin(), (x).end()
  23. #define gcd __gcd
  24. #define SQRT 350
  25.  
  26. set<pii > S;
  27. set<pii >::iterator it;
  28. int dot[NN];
  29.  
  30. int solve(int len) {
  31. 	int ans=0;
  32. 	while(len>1) {
  33. 		ans+=len/2;
  34. 		if(len%2==0)
  35. 			len/=2;
  36. 		else
  37. 			len=len/2+1;
  38. 	}
  39. 	return ans;
  40. }
  41.  
  42. int main(int argc, char const *argv[])
  43. {
  44. 	fast;
  45.  
  46. 	int n,q;
  47. 	cin>>n>>q;
  48.  
  49. 	string s;
  50. 	cin>>s;
  51.  
  52. 	S.clear();
  53. 	int ans=0;
  54. 	for(int i=0;i<s.size();) {
  55. 		if(s[i]=='.') {
  56. 			dot[i+1]=1;
  57. 			i++;
  58. 			int start=i-1,end=start;
  59. 			while(s[i]=='.' && i<s.size()) {
  60. 				dot[i+1]=1;
  61. 				end=i;
  62. 				i++;
  63. 			}
  64. 			ans+=solve(end-start+1);
  65. 			//cout<<"insering "<<start+1<<" "<<end+1<<"\n";
  66. 			S.insert(mp(start+1,end+1));
  67. 		}
  68. 		else
  69. 			i++;
  70. 	}
  71.  
  72. 	//cout<<"current "<<ans<<"\n";
  73.  
  74. 	int p;
  75. 	string c;
  76. 	while(q--)  {
  77. 		cin>>p>>c;
  78. 		if(dot[p] && c==".") {
  79. 		}
  80. 		else if(!dot[p] && c!=".") {
  81. 		}
  82. 		//dot replaced by letter
  83. 		else if(dot[p] && c!=".") {
  84. 			dot[p]=false;
  85. 			it=S.upper_bound(mp(p,-inf));
  86. 			if(it==S.end())
  87. 				it--;
  88. 			while(it->ff > p )
  89. 				it--;
  90. 			int l=it->ff,r=it->ss;
  91. 			ans-=solve(r-l+1);
  92. 			S.erase(it);
  93. 			if(l==r);
  94. 			else if(p==l) {
  95. 				S.insert(mp(p+1,r));
  96. 				ans+=solve(r-p);
  97. 			}
  98. 			else if(p==r){
  99. 				S.insert(mp(l,r-1));
  100. 				ans+=solve(r-l);
  101. 			}
  102. 			else {
  103. 				S.insert(mp(l,p-1));
  104. 				ans+=solve(p-l);
  105. 				S.insert(mp(p+1,r));
  106. 				ans+=solve(r-p);
  107. 			}
  108. 		}
  109.  
  110. 		//letter replaced by dot
  111. 		else if(!dot[p] && c==".") {
  112. 			//cout<<"here\n";
  113. 			dot[p]=true;
  114. 			int l=-1,r=-1;
  115. 			it=S.upper_bound(mp(p-1,-inf));
  116. 			while(it->ff>=p && it!=S.begin())
  117. 				it--;
  118. 			if(it->ss==p-1) {
  119. 				//cout<<"jere\n";
  120. 				l=it->ff;
  121. 				r=p-1;
  122. 				ans-=solve(r-l+1);
  123. 				S.erase(it);
  124. 			}
  125. 			r++;
  126. 			it=S.upper_bound(mp(p+1,-inf));
  127. 			if(it==S.end()) ;
  128. 			else if(it->ff==p+1){
  129. 				r=it->ss;
  130. 				ans-=solve(it->ss-it->ff+1);
  131. 				S.erase(it);
  132. 			}
  133.  
  134. 			if(l!=-1 && r!=-1) {
  135. 				S.insert(mp(l,r));
  136. 				ans+=solve(r-l+1);
  137. 			}
  138. 		}
  139. 		cout<<ans<<"\n";
  140. 	}
  141.  
  142.  
  143.  
  144. 	return 0;
  145. }
Success #stdin #stdout 0s 3996KB
comments (?)
stdin
copy 
1 5
.
1 .
1 w
1 w
1 .
1 .
stdout
copy 
0
0
0
0
0
https://ideone.com/G1AApF
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!