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