fork(4) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. #define REP(i,n) for(int i=0;i<(n);i++)
  6. #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
  7. #define FORD(i,a,b) for(int i=(a);i>=(b);i--)
  8.  
  9. int nextint()
  10. {
  11. 	int t;
  12. 	scanf("%d",&t);
  13. 	return t;
  14. }
  15.  
  16. struct info
  17. {
  18. 	int lv,rv;
  19. 	int lc,rc;
  20. 	int res;
  21. };
  22.  
  23. info merge(info l, info r)
  24. {
  25. 	if(l.res==0) return r;
  26. 	if(r.res==0) return l;
  27. 	info res;
  28. 	res.res=max(l.res,r.res);
  29. 	if(l.rv==r.lv)
  30. 		res.res=max(res.res,l.rc+r.lc);
  31. 	res.lv=l.lv;
  32. 	if(l.lv==r.lv)
  33. 		res.lc=l.lc+r.lc;
  34. 	else
  35. 		res.lc=l.lc;
  36. 	res.rv=r.rv;
  37. 	if(l.rv==r.rv)
  38. 		res.rc=l.rc+r.rc;
  39. 	else
  40. 		res.rc=r.rc;
  41. 	return res;
  42. }
  43.  
  44. vector<info> tree;
  45.  
  46. int ds;
  47.  
  48. int getds(int n)
  49. {
  50. 	n--;
  51. 	n|=n>>1;
  52. 	n|=n>>2;
  53. 	n|=n>>4;
  54. 	n|=n>>8;
  55. 	n|=n>>16;
  56. 	return n+1;
  57. }
  58.  
  59. int get(int l,int r)
  60. {
  61. 	info resl, resr;
  62. 	resl.lc=0; resl.rc=0; resl.res=0;
  63. 	resr.lc=0; resr.rc=0; resr.res=0;
  64. 	l+=ds;
  65. 	r+=ds;
  66. 	while(l<=r)
  67. 	{
  68. 		if(l&1) resl=merge(resl,tree[l++]);
  69. 		if(~r&1) resr=merge(tree[r--],resr);
  70. 		l>>=1;
  71. 		r>>=1;
  72. 	}
  73. 	return merge(resl,resr).res;
  74. }
  75.  
  76. int main()
  77. {
  78. 	while(1)
  79. 	{
  80. 		int n;
  81. 		int m;
  82. 		scanf("%d",&n);
  83. 		if(n==0) break;
  84. 		scanf("%d",&m);
  85. 		ds=getds(n);
  86. 		tree.resize(2*ds);
  87. 		REP(i,n)
  88. 		{
  89. 			int v;
  90. 			scanf("%d",&v);
  91. 			tree[i+ds].lv=tree[i+ds].rv=v;
  92. 			tree[i+ds].lc=tree[i+ds].rc=tree[i+ds].res=1;
  93. 		}
  94. 		FORD(i,ds-1,1)
  95. 			tree[i]=merge(tree[2*i],tree[2*i+1]);
  96. 		while(m--)
  97. 		{
  98. 			int l,r;
  99. 			scanf("%d%d",&l,&r);
  100. 			printf("%d\n",get(l-1,r-1));
  101. 		}
  102. 	}
  103. }
Success #stdin #stdout 0.02s 2864KB
comments (?)
stdin
copy 
16 1
1 1 1 1 2 2 2 3 3 2 2 2 4 4 4 4
1 16
0
stdout
copy 
4
https://ideone.com/rFqyj
language:
C++ (gcc 8.3)
created:
12 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!