fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cstring>
  8. #include <stack>
  9. #include <queue>
  10. #include <map>
  11. #include <string>
  12. #include <utility>
  13. #include <ctime>
  14. #include <algorithm>
  15. #include <iomanip>
  16. using namespace std;
  17. #define pb push_back
  18.  
  19. const int SIZE = 100005;
  20.  
  21. bool GirlFriends[SIZE], check_type_1[SIZE], check_type_2[SIZE];
  22. int final_type_1[SIZE], final_type_2[SIZE];
  23. vector<int> type_1[SIZE][2];
  24. vector<int> type_2[SIZE][2];
  25. priority_queue <int> q;
  26.  
  27. int main()
  28. {
  29. 	ios::sync_with_stdio(false);// to boost I/O
  30. 	cin.tie(0);
  31.  
  32. 	int t, len, k, type, l, r, ans;
  33. 	string s;
  34. 	cin >> t;
  35. 	while(t--)
  36. 	{
  37. 		cin >> s;
  38. 		len = s.size();
  39. 		for(int i = 1; i<=len; i++)
  40. 		{
  41. 			GirlFriends[i] = false;
  42. 			if(s[i-1]=='X')
  43. 				GirlFriends[i] = true;
  44. 		}
  45. 		cin >> k;
  46.  
  47. 		/* Store Queries and their Indices */
  48. 		for(int i = 1; i<=k; i++)
  49. 		{
  50. 			cin >> type >> l >> r;
  51. 			if(type==1)
  52. 			{	
  53. 				type_1[l][0].pb(i);
  54. 				type_1[r+1][1].pb(i);
  55. 			}	
  56. 			else if(type==2)
  57. 			{
  58. 				type_2[l][0].pb(i);
  59. 				type_2[r+1][1].pb(i);
  60. 			}
  61. 		}
  62.  
  63. 		/* End */
  64.  
  65. 		/* Initializations */
  66.  
  67. 		for(int i = 1; i<=(len+2); i++)
  68. 		{
  69. 			final_type_1[i] = 0;
  70. 			final_type_2[i] = 0;
  71. 		}
  72. 		for(int i = 1; i<=k; i++)	
  73. 		{
  74. 			check_type_1[i] = true;
  75. 			check_type_2[i] = true;
  76. 		}
  77.  
  78. 		/* End */
  79.  
  80. 		/* Update for Type-1 */
  81.  
  82. 		for(int i = 1; i<=len; i++)
  83. 		{
  84. 			for(int j = 0; j<type_1[i][1].size(); j++)
  85. 			{
  86. 				check_type_1[type_1[i][1][j]] = false;
  87. 			}
  88. 			for(int j = 0; j<type_1[i][0].size(); j++)
  89. 			{
  90. 				q.push(type_1[i][0][j]);
  91. 			}
  92. 			if(!q.empty())
  93. 			{
  94. 				while(!q.empty() && !check_type_1[q.top()])
  95. 				{
  96. 					q.pop();
  97. 				}
  98. 				if(!q.empty())
  99. 				{
  100. 					final_type_1[i] = q.top();
  101. 				}	
  102. 			}
  103. 		}
  104.  
  105. 		/* End */
  106.  
  107. 		while(!q.empty())
  108. 		{
  109. 			q.pop();
  110. 		}
  111.  
  112. 		/* Update for Type-2 */
  113.  
  114. 		for(int i = 1; i<=len; i++)
  115. 		{
  116. 			for(int j = 0; j<type_2[i][1].size(); j++)
  117. 			{
  118. 				check_type_2[type_2[i][1][j]] = false;
  119. 			}
  120. 			for(int j = 0; j<type_2[i][0].size(); j++)
  121. 			{
  122. 				q.push(type_2[i][0][j]);
  123. 			}
  124. 			if(!q.empty())
  125. 			{
  126. 				while(!q.empty() && !check_type_2[q.top()])
  127. 				{
  128. 					q.pop();
  129. 				}
  130. 				if(!q.empty())
  131. 				{
  132. 					final_type_2[i] = q.top();
  133. 				}	
  134. 			}
  135. 		}
  136.  
  137. 		/* End */
  138.  
  139. 		while(!q.empty())
  140. 		{
  141. 			q.pop();
  142. 		}
  143.  
  144. 		/* Final String After Updating */
  145.  
  146. 		for(int i = 1; i<=len; i++)
  147. 		{
  148. 			if(final_type_1[i]>final_type_2[i])
  149. 			{
  150. 				GirlFriends[i] = true;
  151. 			}
  152. 			else if(final_type_1[i]<final_type_2[i])
  153. 			{	
  154. 				GirlFriends[i] = false;
  155. 			}
  156. 		}
  157.  
  158. 		/* End */
  159.  
  160. 		/* Minimum number of Toggles */
  161.  
  162. 		int sum_X = 0, sum_O = 0;
  163. 		for(int i = 1; i<=len; i++)
  164. 		{
  165. 			if(GirlFriends[i])
  166. 				sum_X++;
  167. 		}
  168. 		int ans = sum_X;
  169. 		for(int i = 1; i<=len; i++)
  170. 		{
  171. 			if(!GirlFriends[i])	sum_O++;
  172. 			if(GirlFriends[i])	sum_X--;
  173. 			ans = min(ans, sum_X + sum_O);
  174. 		}
  175. 		cout << ans << "\n";
  176.  
  177. 		/* End */
  178.  
  179. 		/* Clearing all the vector arrays for next test case */
  180.  
  181. 		for(int i = 0; i<=len; i++)
  182. 		{
  183. 			type_1[i][0].clear();
  184. 			type_1[i][1].clear();
  185. 			type_2[i][0].clear();
  186. 			type_2[i][1].clear();
  187. 		}
  188. 		type_1[len+1][0].clear();
  189. 		type_1[len+1][1].clear();
  190. 		type_2[len+1][0].clear();
  191. 		type_2[len+1][1].clear();
  192.  
  193. 		/* End */
  194. 	}
  195. }
Success #stdin #stdout 0s 9224KB
comments (?)
stdin
copy 
1
XOXO
2
2 1 2
1 3 4
stdout
copy 
2
https://ideone.com/FmrZcl
language:
C++ (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!