fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int,int>
  3. using namespace std;
  4. struct data{
  5. 	pair<int ,int> lfeq,rfeq,totalfeq;
  6. };
  7. int n;
  8. data tree[2*100001];
  9.     pii maxx(pii a, pii b)
  10.     {
  11.         if(a.first >= b.first)
  12.             return a;
  13.         else
  14.             return b;
  15.     }
  16. data combine(data l, data r)
  17. {	data res;
  18. 		res.lfeq = l.totalfeq;
  19. 		res.rfeq = r.totalfeq;
  20. 	if(l.totalfeq.second == r.totalfeq.second)
  21. 	{
  22. 		res.totalfeq = make_pair(l.totalfeq.first + r.totalfeq.first,l.totalfeq.second);
  23. 	}
  24. 	else
  25. 	{
  26. 		if(l.rfeq.second == r.lfeq.second)
  27. 		{
  28. 			pair<int ,int > tp;
  29. 			if(l.totalfeq.second == l.rfeq.second)
  30. 			{
  31. 				tp.first = max(l.totalfeq.first+r.lfeq.first,r.totalfeq.first);
  32. 				tp.second  = (tp.first == r.totalfeq.first)?r.totalfeq.second:l.totalfeq.second;
  33. 			}
  34. 			else if(r.lfeq.second == r.totalfeq.second)
  35. 			{
  36. 				tp.first = max(l.rfeq.first+r.totalfeq.first,l.totalfeq.first);
  37. 				tp.second = (tp.first==l.totalfeq.first)?l.totalfeq.second:r.totalfeq.second;
  38. 			}
  39. 			res.totalfeq = tp;
  40. 		}
  41. 		else
  42. 		{
  43. 			res.totalfeq = maxx(l.totalfeq,r.totalfeq);
  44. 		}
  45. 	}
  46. 	return res;
  47. }
  48. data init(int feq,int num)
  49. {
  50. 	data res;
  51. 	res.lfeq.first = res.rfeq.first = res.totalfeq.first = feq;
  52. 	res.lfeq.second = res.rfeq.second = res.totalfeq.second = num;
  53. 	return res;
  54. }
  55. void build()
  56. {
  57. 	for(int i=n-1;i>0;i--)
  58. 	{
  59. 		tree[i] = combine(tree[i<<1],tree[i<<1|1]);
  60. 	}
  61. }
  62. data query(int l,int r)
  63. {
  64. 	data resl= init(0,-1000001),resr = init (0,-1000001) ;
  65. 	//int fl= 0;
  66. 	for(l+=n,r+=n;l<r;l>>=1,r>>=1)
  67. 	{	
  68. 		if(l&1) resl = combine(resl,tree[l++]);
  69. 		if(r&1) resr = combine(tree[--r],resr);
  70. 	}
  71. 	return combine(resl,resr);
  72. }
  73.  
  74. int main()
  75. {	 std::ios::sync_with_stdio(false);
  76. 	//int t=1;
  77. 	while(1)
  78. 	{	int ts,l,r;	
  79. 		scanf("%d", &n);
  80. 		if(n==0)
  81. 			break;
  82. 		scanf("%d",&ts);
  83. 		int a[n];
  84.  
  85. 		for (int i = 0; i < n; ++i){
  86. 			scanf("%d", &a[i]);
  87. 			tree[n+i] = init(1,a[i]);
  88. 		} 
  89. 		build();
  90.  
  91. 		while(ts--)
  92. 		{
  93. 			scanf("%d%d",&l,&r);
  94. 			printf("%d \n",query(l-1,r).totalfeq.first);
  95. 		}
  96. 		//scanf("%d",&t);
  97. 	}
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1 
4 
3
https://ideone.com/uhftBt
language:
C++14 (gcc 8.3)
created:
8 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!