fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<string.h>
  4. #include<math.h>
  5. #define M 100005
  6.  
  7.  
  8.  
  9. struct node
  10. {
  11. 	int  lf,rf,mf;
  12. }
  13. tree[50*M],tree1[50*M];
  14.  
  15.  
  16. int arr[M];
  17.  
  18. int max(int a,int b)
  19. {
  20. 	if(a>b)
  21. 	return a;
  22. 	else
  23. 	return b;
  24. }
  25.  
  26. int max2(int a,int b,int c)
  27. {
  28. 	if(a>=b&&a>=c)
  29. 	return a;
  30. 	else if(b>=a&&b>=c)
  31. 	return b;
  32. 	else
  33. 	return c;
  34. }
  35.  
  36.  
  37. int getmid(int a,int b)
  38. {
  39. 	return ((a+b)/2);
  40. }
  41.  
  42. void  buildtree(int node,int a,int b)
  43. {
  44. 	if(a>b)return;
  45. 	if(a==b)
  46.  	{tree[node].lf=tree[node].rf=tree[node].mf=1;return;}
  47.  
  48. 	int mid=getmid(a,b);
  49. 	buildtree(2*node,a,mid);
  50. 	buildtree(2*node+1,mid+1,b);
  51. 	if(arr[a]==arr[mid+1])
  52. 	tree[node].lf=tree[2*node].lf+tree[2*node+1].lf;
  53. 	else
  54. 	tree[node].lf=tree[2*node].lf;
  55. 	if(arr[mid]==arr[b])
  56. 	tree[node].rf=tree[2*node].rf+tree[2*node+1].rf;
  57. 	else
  58. 	tree[node].rf=tree[2*node+1].rf;
  59.  
  60. 	if(arr[mid]==arr[mid+1])
  61. 	tree[node].mf=max2(tree[2*node].mf,tree[2*node+1].mf,tree[2*node].rf+tree[2*node+1].lf);
  62. 	else
  63. 	tree[node].mf=max(tree[2*node].mf,tree[2*node+1].mf);
  64. 	return ;
  65. }
  66.  
  67.  
  68.  
  69.  
  70. int query(int node,int a,int b,int i,int j)
  71. {
  72. //	printf("node  %d   %d   %d\n",a,b,node);
  73. 	if(a>b||b<i||a>j){return -100009;}
  74. 	if(a>=i&&b<=j)
  75. 	{
  76. 	//	printf("the leaf node   %d\n",node);
  77.     tree1[node].lf=tree[node].lf;
  78.     tree1[node].rf=tree[node].rf;
  79.     tree1[node].mf=tree[node].mf;
  80.  
  81. 	return node;
  82. 	}
  83. 	int p,q,res;
  84. 	int mid=getmid(a,b);
  85.  
  86. 	p=query(2*node,a,mid,i,j);
  87. 	q=query(2*node+1,mid+1,b,i,j);
  88.  
  89. 	if(p==-100009&&q==-100009)return -100009;
  90. 	else if(p==-100009)
  91. 	{tree1[node].lf=tree1[q].lf;tree1[node].mf=tree1[q].mf;tree1[node].rf=tree1[q].rf;
  92. 	//printf("sonu  %d   %d     %d  %d\n",p,q,node,tree1[node].mf);
  93. 	return node;}
  94. 	else if(q==-100009)
  95.     {tree1[node].lf=tree1[p].lf;tree1[node].mf=tree1[p].mf;tree1[node].rf=tree1[p].rf;
  96. 	//printf("mk  %d    %d  %d   %d   %d\n",p,q,tree1[p].mf,node,tree1[node].mf);
  97. 	return node;}
  98. 	else
  99. 	{
  100. 	if(arr[a]==arr[mid+1])
  101. 	tree1[node].lf=tree1[2*node].lf+tree1[2*node+1].lf;
  102. 	else
  103. 	tree1[node].lf=tree1[2*node].lf;
  104. 	if(arr[mid]==arr[b])
  105. 	tree1[node].rf=tree1[2*node].rf+tree1[2*node+1].rf;
  106. 	else
  107. 	tree1[node].rf=tree1[2*node+1].rf;
  108.  
  109. 	if(arr[mid]==arr[mid+1])
  110. 	tree1[node].mf=max2(tree1[2*node].mf,tree1[2*node+1].mf,tree1[2*node].rf+tree1[2*node+1].lf);
  111. 	else
  112. 	tree1[node].mf=max(tree1[2*node].mf,tree1[2*node+1].mf);
  113.  
  114. 		return node;
  115. 	}
  116.  
  117. }
  118.  
  119.  
  120.  
  121. int main()
  122. {
  123. 	int t,a,b,c,i,j,k,l,q,n;
  124.  
  125. 	while(1)
  126. 	{
  127. 	scanf("%d",&n);
  128. 	if(n==0)break;
  129. 	scanf("%d",&q);
  130. 	for(i=1;i<=n;i++)
  131. 	scanf("%d",&arr[i]);
  132.  
  133. 	memset(tree,0,sizeof(tree));
  134. 	memset(tree1,0,sizeof(tree));
  135.  
  136. 	 buildtree(1,1,n);
  137. 	// for(i=1;i<=25;i++)printf("%d   %d    %d    %d\n",i,tree[i].lf,tree[i].rf,tree[i].mf);
  138.  //system("pause");
  139. //buildtree is fine :P
  140.      while(q--)
  141.      {
  142. 			scanf("%d%d",&a,&b);
  143.  
  144. 			printf("%d\n",tree1[query(1,1,n,a,b)].mf);
  145. 	}
  146.   }
  147. //	system("pause");
  148. }
Runtime error #stdin #stdout 0.11s 120896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/osSN1C
language:
C++ (gcc 8.3)
created:
10 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!