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. 	bool 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_start >= start && query_end <= end)
  111. 	{
  112. 		return tree[tree_index];
  113.  
  114. 	}
  115. 	ll mid = start + end;
  116. 	mid >>= 1;
  117.  
  118.  
  119. 	b = query(tree,2*tree_index,start,mid,query_start,query_end);
  120.  
  121. 	c = query(tree,2*tree_index+1,mid+1,end,query_start,query_end);
  122.  
  123. 	// yeah i know its wrong 
  124. 	// but can't figure it out what to do :(
  125. 	// .....
  126.  
  127.  
  128. }
  129. int main()
  130. {
  131. 	ll n,i,j,x,y,q,k,val;
  132. 	cin>>n>>q>>k;
  133.  
  134. 	ll a[2*n] = {0};
  135. 	for(i = 0;i<n;i++)
  136. 		cin>>a[i],
  137. 		a[n+i] = a[i];
  138. 	node tree[8*n+4];
  139. 	build(tree,a,1,0,2*n-1);
  140. 	//for(i = 1;i<=26;i++)
  141. 	//cout<<i<<"\t"<<tree[i].ans<<"\t"<<tree[i].pre<<"\t"<<tree[i].suff<<"\t"<<tree[i].has_0<<endl;
  142. 	j = 0;
  143.  
  144.  
  145.  
  146. 	// just for testing purpose
  147. 	/*while(1)
  148. 	{
  149. 		//cin>>j;
  150. 		//cout<<j<<" ";
  151.  
  152. 		node node1 = query(tree,1,0,n-1, j,j+n-1);
  153.  
  154. 		cout<<j<<" "<<j+n-1<<" "<<node1.ans<<" "<<node1.pre<<" "<<node1.suff<<endl;
  155. 		j++;
  156. 	}*/
  157.  
  158.  
  159. 	/*string que = "";
  160. 	cin>>que;
  161. 	i = 0;
  162. 	j = 0;
  163. 	while(i<que.length())
  164. 	{
  165.  
  166. 		if(que[i] == '!')
  167. 		{
  168. 			j++;
  169. 			if(j == n)
  170. 				j = 0;
  171.  
  172. 		}
  173.  
  174. 		//cout<<x<<" "<<y<<"\t";
  175. 		else
  176. 		{
  177. 			//cout<<j<<" "<<j+n-1<<"\t";
  178. 			val = query(tree,1,0,2*n-1, j,j+n-1).ans;
  179. 			cout<<val<<endl;
  180. 			//cout<<min(k,val)<<endl;
  181. 		}
  182.  
  183. 		i++;
  184. 	}*/
  185.  
  186.  
  187.  
  188. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
5 5 3
1 1 0 1 1
stdout
copy 
Standard output is empty
https://ideone.com/vG4Xo3
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!