fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. class node
  5. {
  6. 	public : 
  7. 	ll pre,suff ,ans;
  8. 	ll has_0;
  9. 	node()
  10. 	{
  11. 		pre = suff = ans = has_0 = 0;
  12. 	}
  13. };
  14. void build(node *tree,ll *a,ll tree_index,ll start,ll end)
  15. {
  16. 	if(start>end)
  17. 	return;
  18. 	if(start == end)
  19. 	{
  20.  
  21. 		//a[start] == 1 ? tree[tree_index].has_0=0,pre=suff=ans=1 ? tree[tree_index].has_0=1,pre=suff=ans=0;
  22. 		if(a[start] == 1)
  23. 		{
  24. 			tree[tree_index].has_0 = 0;
  25. 			tree[tree_index].pre = 1;
  26. 			tree[tree_index].suff = 1;
  27. 			tree[tree_index].ans = 1;
  28. 		}
  29. 		else
  30. 		{
  31. 			tree[tree_index].has_0 = 1;
  32. 			tree[tree_index].pre = 0;
  33. 			tree[tree_index].suff = 0;
  34. 			tree[tree_index].ans = 0;
  35. 		}
  36. 		//cout<<tree_index<<" "<<start<<" "<<tree[tree_index].ans<<endl;
  37. 		return;	
  38. 	}
  39. 	ll mid = start + end;
  40. 	mid >>= 1;
  41.  
  42. 	build(tree,a,2*tree_index,start,mid);
  43. 	build(tree,a,2*tree_index+1,mid+1,end);
  44.  
  45. 	// for parent has_0
  46. 	if(tree[2*tree_index].has_0 == 1 || tree[2*tree_index + 1].has_0 == 1)
  47. 	tree[tree_index].has_0 = 1;
  48. 	else if(tree[2*tree_index].has_0 == 0 && tree[2*tree_index + 1].has_0 == 0)
  49. 	{
  50. 		// 1. Both do not contain 0
  51.  
  52. 		tree[tree_index].has_0 = 0;
  53. 		tree[tree_index].pre = tree[tree_index].suff = tree[tree_index].ans = end-start+1;
  54. 		return;
  55. 	}
  56.  
  57. 	// 2. if left child contains 0
  58. 	if(tree[2*tree_index].has_0 == 1 && tree[2*tree_index+1].has_0 == 0)
  59. 	{
  60. 		tree[tree_index].pre = tree[2*tree_index].pre;
  61. 		tree[tree_index].suff = tree[2*tree_index].suff + end - mid;
  62. 		tree[tree_index].ans = max(tree[tree_index].suff, max(tree[2*tree_index].ans , tree[2*tree_index+1].ans));	
  63. 		return;	
  64. 	}
  65.  
  66. 	// 3. if right child contains 0
  67. 	if(tree[2*tree_index].has_0 == 1 && tree[2*tree_index+1].has_0 == 0)
  68. 	{
  69. 		tree[tree_index].pre = tree[2*tree_index+1].pre + mid - start + 1;
  70. 		tree[tree_index].suff = tree[2*tree_index+1].suff;
  71. 		tree[tree_index].ans = max(tree[tree_index].pre, max(tree[2*tree_index].ans , tree[2*tree_index+1].ans));	
  72. 		return;	
  73. 	}
  74.  
  75. 	// 4. if both contains 0
  76. 	tree[tree_index].pre = tree[2*tree_index].pre;
  77. 	tree[tree_index].suff = tree[2*tree_index+1].suff;
  78. 	tree[tree_index].ans = max(tree[2*tree_index].suff+tree[2*tree_index+1].pre,max(tree[2*tree_index].ans,tree[2*tree_index+1].ans));
  79.  
  80. }
  81. //its returning the answer but have to return a node
  82. /*
  83. ll query(node *tree,ll tree_index,ll start,ll end,ll query_start,ll query_end)
  84. {
  85. 	// 1. No overlap
  86. 	if(start > query_end || end < query_start)
  87. 	return minv;
  88.  
  89. 	// 2. Complete overlap
  90. 	if(start >= query_start && end <= query_end)
  91. 	{
  92. 		return tree[tree_index].ans;
  93. 	}
  94. 	ll mid = start + end;
  95. 	mid >>= 1;
  96. 	ll leftans = query(tree,2*tree_index,start,mid, query_start,query_end);
  97. 	ll rightans = query(tree,2*tree_index + 1,mid+1,end, query_start,query_end);
  98.  
  99.  
  100. 	// merge answer :(
  101. 	ll mergeans = 1;    //???  
  102. 	//return max(merge_ans,max(leftans,rightans));
  103. 	return max(mergeans, max(leftans,rightans));
  104.  
  105. }*/
  106. node query(node *tree,ll tree_index,ll start,ll end,ll query_start,ll query_end)
  107. {
  108. 	node a,b,c;
  109.  
  110. 	if(query_end < start || end < query_start)
  111. 	{
  112. 		a.ans = a.pre = a.suff = 0;
  113. 		a.has_0 = 100;
  114. 		return a;
  115. 	}
  116.  
  117.  
  118. 	if(query_start <= start && query_end >= end)
  119. 	{
  120. 		return tree[tree_index];		
  121. 	}
  122.  
  123. 	ll mid = start + end;
  124. 	mid >>= 1;
  125.  
  126.  
  127. 	b = query(tree,2*tree_index,start,mid,query_start,query_end);
  128.  
  129. 	c = query(tree,2*tree_index+1,mid+1,end,query_start,query_end);
  130.  
  131. 	if(b.has_0 == 100)
  132. 	{
  133. 		//cout<<"left cut :)  ";
  134. 		return c;
  135. 	}
  136. 	if(c.has_0 == 100)
  137. 	{
  138. 		//cout<<"right cut :)  ";
  139. 		return b;
  140. 	}
  141.  
  142. 	// yeah i know its wrong 
  143. 	// but can't figure it out what to do :(
  144. 	// .....
  145.  
  146. 	// both don't contain 0
  147. 	if(b.has_0 == 0 && c.has_0 == 0)
  148. 	{
  149. 		a.has_0 = 0;
  150. 		a.pre = a.suff = a.ans = b.ans + c.ans;
  151. 		return a;
  152. 	}
  153.  
  154. 	// if left contains 0
  155. 	if(b.has_0 == 1 && c.has_0 == 0)
  156. 	{
  157. 		a.has_0 = 1;
  158. 		a.pre = b.pre;
  159. 		a.suff = b.suff + c.suff;
  160. 		a.ans = max(b.ans , max(c.ans , b.suff+c.pre));
  161. 		return a;
  162. 	}
  163.  
  164. 	// if right contains 0
  165. 	if(b.has_0 == 0 && c.has_0 == 1)
  166. 	{
  167. 		a.has_0 = 1;
  168. 		a.pre = b.pre + c.pre;
  169. 		a.suff = c.suff;
  170. 		a.ans = max(b.ans , max(c.ans , b.suff + c.pre));
  171. 		return a;
  172. 	}
  173.  
  174. 	// if both contains 0
  175. 	a.has_0 = 1;
  176. 	a.pre = b.pre;
  177. 	a.suff = c.suff;
  178. 	a.ans = max(b.ans , max(c.ans , b.suff + c.pre));
  179. 	return a;
  180. }
  181. int main()
  182. {
  183. 	ll n,i,j,x,y,q,k,val;
  184. 	cin>>n>>q>>k;
  185.  
  186. 	ll xr[n] = {0};
  187. 	for(i = 0;i<n;i++)
  188. 		cin>>xr[i];
  189. 	reverse(xr,xr+n);
  190. 	ll  a[2*n] = {0};
  191. 	for(i = 0;i<n;i++)
  192. 	{
  193. 		a[i] = a[i+n] = xr[i];
  194. 	}
  195. 	for(i = 0;i<n;i++)
  196. 	{
  197. 		a[i] = a[i+n] = xr[i];
  198. 		//cout<<xr[i]<<" ";
  199. 	}
  200. 	//for(i = 0;i<2*n;i++)
  201. 	//cout<<a[i]<<" ";
  202. 	node tree[8*n+4];
  203. 	build(tree,a,1,0,2*n-1);
  204. 	//for(i = 1;i<=26;i++)
  205. 	//cout<<i<<"\t"<<tree[i].ans<<"\t"<<tree[i].pre<<"\t"<<tree[i].suff<<"\t"<<tree[i].has_0<<endl;
  206. 	j = 2*n-1;
  207.  
  208.  
  209. 	/*while(1)
  210. 	{
  211. 		cin>>j>>val;
  212. 		//cout<<j<<" ";
  213.  
  214. 		node node1 = query(tree,1,0,2*n-1, j,val);
  215.  
  216. 		cout<<j<<" "<<val<<" "<<node1.ans<<" "<<node1.pre<<" "<<node1.suff<<endl;
  217. 		//j++;
  218. 	}*/
  219.  
  220.  
  221. 	string que = "";
  222. 	cin>>que;
  223. 	i = 0;
  224. 	j = 0;
  225. 	for(i = 0;i<que.length();i++)
  226. 	{
  227.  
  228. 		if(que[i] == '!')
  229. 		{
  230. 			j++;
  231. 			if(j == n)
  232. 				j = 0;
  233.  
  234. 		}
  235.  
  236. 		//cout<<x<<" "<<y<<"\t";
  237. 		else
  238. 		{
  239. 			val = query(tree,1,0,2*n-1, j,j+n-1).ans;
  240. 			cout<<min(val,k)<<endl;
  241. 		}
  242.  
  243.  
  244. 	}
  245.  
  246.  
  247.  
  248. }
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BtFs2r
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!