fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <ctime>
  7. #include <cmath>
  8. #include <cassert>
  9. #include <cctype>
  10. #include <climits>
  11. #include <vector>
  12. #include <bitset>
  13. #include <set>
  14. #include <queue>
  15. #include <stack>
  16. #include <map>
  17. #include <deque>
  18. #include <string>
  19. #include <list>
  20. #include <iterator>
  21. #include <sstream>
  22. #include <complex>
  23. #include <fstream>
  24. #include <functional>
  25. #include <numeric>
  26. #include <utility>
  27. #include <algorithm>
  28. #include <assert.h>
  29.  
  30. using namespace std;
  31.  
  32. #define endl '\n'
  33. #define MOD 1000000007ULL
  34. #define INF 1000000000
  35. #define eps 1e-8
  36. #define ll long long
  37. #define F first
  38. #define S second
  39. #define pb push_back
  40. #define mp make_pair
  41. #define debug(X) cerr << " --> " << #X << " = " << X << endl
  42. #define sd(x) scanf("%d",&(x))
  43. #define slld(x) scanf("%lld",&(x))
  44. #define pd(x) printf("%d\n",(x))
  45. #define plld(x) printf("%lld\n",(x))
  46. #define gcd __gcd
  47. #define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
  48.  
  49. typedef vector< vector<int> > vvi;
  50. typedef vector< vector<ll> > vvl;
  51. typedef pair<int, int> pii;
  52. typedef pair<long long, long long> pll;
  53. typedef vector<int> vi;
  54. typedef vector<ll> vll;
  55.  
  56. int st[400005];
  57. int lazy[400005];
  58. int a[100005];
  59.  
  60. void construct(int node, int i, int j)
  61. {
  62. 	if(i == j)
  63. 	{
  64. 		st[node] = a[i];
  65. 		lazy[node] = -1;
  66. 		return;
  67. 	}
  68. 	int mid = (i+j)/2;
  69. 	construct(node*2, i, mid);
  70. 	construct(node*2+1,mid+1,j);
  71. 	st[node] = st[node*2]+st[node*2+1];
  72. 	lazy[node] = -1;
  73. 	return;
  74. }
  75.  
  76. void push(int node, int i, int j)
  77. {
  78. 	if(lazy[node] != -1)
  79. 	{
  80. 		st[node] = (j-i+1)*lazy[node];
  81. 		if(i != j)
  82. 		{
  83. 			lazy[node*2] = lazy[node];
  84. 			lazy[node*2+1] = lazy[node];
  85. 		}
  86. 		lazy[node] = -1;
  87. 	}
  88. }
  89.  
  90. void update(int node, int i, int j, int x, int y, int v)
  91. {
  92. 	if(i > j) return;
  93. 	push(node, i, j);
  94. 	if(j < x || i > y) return;
  95. 	if(i >= x && j <= y)
  96. 	{
  97. 		st[node] = (j-i+1)*v;
  98. 		if(i != j)
  99. 		{
  100. 			lazy[node*2] = v;
  101. 			lazy[node*2+1] = v;
  102. 		}
  103. 		return;
  104. 	}
  105. 	int mid = (i+j)/2;
  106. 	update(node*2, i, mid, x, y, v);
  107. 	update(node*2+1, mid+1, j, x, y, v);
  108. 	st[node]=st[node*2]+st[node*2+1];
  109. 	return;
  110. }
  111.  
  112. int query(int node, int i, int j, int x, int y)
  113. {
  114. 	if(i > j) return 0;
  115. 	push(node, i, j);
  116. 	if(j < x || i > y) return 0;
  117. 	if(i >= x && j <= y)
  118. 		return st[node];
  119. 	int mid = (i+j)/2;
  120. 	return query(node*2, i, mid, x, y)+query(node*2+1, mid+1, j, x, y);
  121. }
  122.  
  123. int main()
  124. {
  125. 	csl;
  126.  
  127. 	int t;
  128. 	cin >> t;
  129. 	while(t--)
  130. 	{
  131. 		string s;
  132. 		cin >> s;
  133. 		for(int i = 0;i < s.size();i++)
  134. 		{
  135. 			if(s[i] == 'X')
  136. 				a[i+1] = 1;
  137. 			else a[i+1] = 0;
  138. 		}
  139. 		int n = s.size();
  140. 		construct(1, 1, n);
  141. 		int k;
  142. 		cin >> k;
  143. 		int aq,l,r;
  144. 		while(k--)
  145. 		{
  146. 			cin >> aq >> l >> r;
  147. 			if(aq == 1)
  148. 			{
  149. 				update(1, 1, n, l, r, 1);
  150. 			}
  151. 			else
  152. 			{
  153. 				update(1, 1, n, l, r, 0);
  154. 			}
  155. 		}
  156. 		for(int i = 1;i <= n;i++)
  157. 			a[i] = query(1, 1, n, i, i);
  158. 		int pre[n+1], suf[n+1];
  159. 		pre[0] = 0;
  160. 		pre[1] = a[1];
  161. 		suf[n] = a[n];
  162. 		for(int i = 2;i <= n;i++)
  163. 		{
  164. 			pre[i] = pre[i-1] + a[i];
  165. 			suf[n-i+1] = suf[n-i+2] + a[n-i+1];
  166. 		}
  167. 		int ans = min(pre[n], n-pre[n]);
  168. 		for(int i = 1;i < n;i++)
  169. 		{
  170. 			ans = min(ans, i-pre[i]+suf[i+1]);
  171. 		}
  172. 		cout << ans << endl;
  173. 	}
  174.  
  175. 	return 0;
  176. }
Success #stdin #stdout 0s 6976KB
comments (?)
stdin
copy 
1
XOXO
2
2 1 2
1 3 4
stdout
copy 
2
https://ideone.com/vPrXix
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!