fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Tree 
  5. {
  6. 	vector<int> tree, arr, lazy;
  7. 	int n;
  8.  
  9. 	void build(int node, int start, int end)
  10. 	{
  11. 		if (start == end)
  12. 			tree[node] = arr[start];
  13. 		else 
  14. 		{
  15. 			int mid = (start+end)/2;
  16. 			build(node*2, start, mid);
  17. 			build(node*2+1, mid+1, end);
  18.  
  19. 			tree[node] = tree[node*2] + tree[node*2+1];
  20. 		}
  21. 	}
  22.  
  23. 	int reduce(int mode, int start, int end, int val)
  24. 	{
  25. 		if (mode == 1)
  26. 			return end-start+1;
  27. 		else if (mode == 2)
  28. 			return 0;
  29. 		else if (mode == 3)
  30. 			return end-start+1-val;
  31. 		else
  32. 			return val;
  33. 	}
  34.  
  35. 	void lazy_prog(int node, int start, int end)
  36. 	{
  37. 		if (lazy[node] != 0)
  38. 		{
  39. 			//cout << "Pushing node " << node << '\n';
  40. 			tree[node] = reduce(lazy[node], start, end, tree[node]);
  41.  
  42. 			if (start != end)
  43. 			{
  44. 				lazy[node*2] = lazy[node];
  45. 				lazy[node*2+1] = lazy[node];
  46. 			}
  47.  
  48. 			lazy[node] = 0;
  49. 		}
  50. 	}
  51.  
  52. 	int query(int node, int start, int end, int i, int j)
  53. 	{
  54. 		lazy_prog(node, start, end);
  55.  
  56. 		if (i > end || j < start)
  57. 			return 0;		
  58.  
  59. 		if (start >= i && end <= j)
  60. 			return tree[node];
  61.  
  62.  
  63. 		int mid = (start+end)/2;
  64. 		int s1 = query(node*2, start, mid, i, j);
  65. 		int s2 = query(node*2+1, mid+1, end, i, j);
  66.  
  67. 		//cout << start << " - " << mid << ": " << s1 << " ";
  68. 		//cout << mid+1 << " - " << end << ": " << s2 << '\n';
  69. 		return s1 + s2;
  70. 	}
  71.  
  72. 	void update(int node, int start, int end, int i, int j, int mode)
  73. 	{
  74. 		lazy_prog(node, start, end);
  75. 		if (start > j || end < i)
  76. 			return;
  77.  
  78. 		if (start >= i && end <= j)
  79. 		{
  80. 			tree[node] = reduce(mode, start, end, tree[node]);
  81.  
  82. 			if (start != end)
  83. 			{
  84. 				lazy[node*2] = mode;
  85. 				lazy[node*2+1] = mode;
  86. 			}
  87.  
  88. 			return;
  89. 		}
  90.  
  91. 		int mid = (start+end)/2;
  92. 		update(node*2, start, mid, i, j, mode);
  93. 		update(node*2+1, mid+1, end, i, j, mode);
  94.  
  95. 		tree[node] = tree[node*2] + tree[node*2+1];
  96. 	}
  97.  
  98. 	Tree(vector<int> a)
  99. 	{
  100. 		arr = a;
  101. 		n = (int)a.size();
  102. 		tree.assign(4*n, 0);
  103. 		lazy.assign(4*n, 0);
  104. 		build(1, 0, n-1);
  105. 	}
  106. };
  107.  
  108. int main(int argc, char** argv) 
  109. {
  110. 	ios::sync_with_stdio(0);
  111. 	cin.tie(0);
  112. 	freopen(".in", "r", stdin);
  113. 	freopen(".out", "w", stdout);
  114.  
  115. 	int t;
  116. 	cin >> t;
  117.  
  118. 	for (int k = 0; k < t; k++)
  119. 	{
  120. 		string land = "";
  121.  
  122. 		int n;
  123. 		cin >> n;
  124. 		while (n--)
  125. 		{
  126. 			int T; cin >> T;
  127. 			string s; cin >> s;
  128. 			for (int i = 0; i < T; i++)
  129. 				land += s;
  130. 		}
  131.  
  132. 		vector<int> A((int)land.length());
  133.  
  134. 		for (int i = 0; i < (int)land.length(); i++)
  135. 			A[i] = (land[i] == '1' ? 1 : 0);
  136.  
  137. 		Tree segtree(A);
  138. 		//for (int i = 0; i < segtree.tree.size(); i++)
  139. 			//cout << i << ": " << segtree.tree[i] << '\n';
  140.  
  141. 		cout << "Case " << k+1 << ":\n";
  142. 		int q;
  143. 		cin >> q;
  144.  
  145. 		int Q = 1;
  146. 		for (int i = 0; i < q; i++)
  147. 		{
  148. 			char c; int a, b;
  149. 			cin >> c >> a >> b;
  150.  
  151. 			if (c != 'S')
  152. 			{
  153. 				int mode;
  154. 				if (c == 'F') mode = 1;
  155. 				else if (c == 'E') mode = 2;
  156. 				else mode = 3;
  157.  
  158. 				segtree.update(1, 0, A.size()-1, a, b, mode);
  159. 				//cout << mode << ' ' << segtree.query(1, 0, A.size()-1, a, b) << ' ' << segtree.query(1, 0, A.size()-1, b+1, A.size()-1) << '\n';
  160. 			}
  161. 			else
  162. 				cout << "Q" << Q++ << ": " << segtree.query(1, 0, A.size()-1, a, b) << '\n';
  163. 		}
  164. 	}
  165.  
  166. 	return 0;
  167. }
  168.  
  169.  
Runtime error #stdin #stdout #stderr 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/neazgA
language:
C++14 (gcc 8.3)
created:
4 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!