fork(2) download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <ctime>
  4. #include <cctype>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <cassert>
  8. #include <algorithm>
  9. using namespace std;
  10.  
  11. /* FOR READING */
  12. const int BUFFER_SIZE = 2000000;
  13. char buffer[BUFFER_SIZE];
  14. #define SKIP_WHITE_SPACES while(isspace(*buffer_pointer)) { ++buffer_pointer; }
  15. #define READ_INTEGER(x) x = 0; while (isdigit(*buffer_pointer)) { x = x * 10 + *buffer_pointer - '0'; ++buffer_pointer; }
  16.  
  17. /* FOR PROBLEM */
  18. const int MAXN = 100000;
  19. const int MAX_SQRT_N = 317;
  20. const int MAXA = 100000;
  21.  
  22. int a[MAXN];
  23.  
  24. int blockMode[MAX_SQRT_N] = {}; /*By default is 0, but fixed in initialize*/
  25. int blockCount[MAXA+1][MAX_SQRT_N] = {};
  26. int histogram[MAXA + 1] = {}; /* will be cleaned just relevant */
  27. int blockSize;
  28.  
  29. #define GET_BLOCK_INDEX(i) ((i) / blockSize)
  30. #define FIRST_INDEX_IN_BLOCK(i) ((i)*blockSize)
  31. #define LAST_INDEX_IN_BLOCK(i) (FIRST_INDEX_IN_BLOCK((i)+1)-1)
  32. #define COUNT_IN_BLOCKS(left, right, value) (blockCount[(value)][(right)] - blockCount[(value)][(left)-1])
  33.  
  34. int main()
  35. {
  36. 	/* READING */
  37. 	register char *buffer_pointer = buffer;
  38. 	fread(buffer, 1, BUFFER_SIZE, stdin);
  39.  
  40.  
  41. 	register int n, q;
  42. 	SKIP_WHITE_SPACES
  43. 	READ_INTEGER(n)
  44. 	SKIP_WHITE_SPACES
  45. 	READ_INTEGER(q)
  46.  
  47. 	/* INITIALIZATION */
  48. 	blockSize = (int)sqrt(1.0L*n);
  49.  
  50. 	for (register int i = 0; i < n; ++i)
  51. 	{
  52. 		/* READING */
  53. 		SKIP_WHITE_SPACES
  54. 		READ_INTEGER(a[i])
  55.  
  56. 		/* INITIALIZATION */
  57. 		int j = GET_BLOCK_INDEX(i);
  58. 		if (++blockCount[a[i]][j] > blockCount[blockMode[i]][j])
  59. 		{
  60. 			blockMode[i] = a[i];
  61. 		}
  62. 	}
  63.  
  64. 	while (q--)
  65. 	{
  66. 		/* READING */
  67. 		register int left, right;
  68. 		SKIP_WHITE_SPACES
  69. 		READ_INTEGER(left)
  70. 		SKIP_WHITE_SPACES
  71. 		READ_INTEGER(right)
  72.  
  73. 		/* COUNTING */
  74. 		register int i;
  75. 		register int modeCount = 0;
  76. 		if (right - left + 1 <= blockSize)
  77. 		{
  78. 			for (i = left; i <= right; ++i)
  79. 			{
  80. 				if (++histogram[a[i]] > modeCount)
  81. 				{
  82. 					modeCount = histogram[a[i]];
  83. 				}
  84. 			}
  85.  
  86. 			// cleaning
  87. 			for (i = left; i <= right; ++i)
  88. 			{
  89. 				histogram[a[i]] = 0;
  90. 			}
  91. 		}
  92. 		else
  93. 		{
  94. 			const int leftBlock = GET_BLOCK_INDEX(left), rightBlock = GET_BLOCK_INDEX(right);
  95. 			const int lastInLeftBlockIndex = LAST_INDEX_IN_BLOCK(leftBlock), firstInRightBlockIndex = FIRST_INDEX_IN_BLOCK(rightBlock);
  96.  
  97. 			for (i = left; i <= lastInLeftBlockIndex; ++i)
  98. 			{
  99. 				int currentCount = ++histogram[a[i]] + COUNT_IN_BLOCKS(leftBlock + 1, rightBlock - 1, a[i]);
  100. 				if (currentCount > modeCount)
  101. 				{
  102. 					modeCount = currentCount;
  103. 				}
  104.  
  105. 			}
  106. 			for (i = firstInRightBlockIndex; i <= right; ++i)
  107. 			{
  108. 				int currentCount = ++histogram[a[i]] + COUNT_IN_BLOCKS(leftBlock + 1, rightBlock - 1, a[i]);
  109. 				if (currentCount > modeCount)
  110. 				{
  111. 					modeCount = currentCount;
  112. 				}
  113. 			}
  114. 			for (i = leftBlock + 1; i <= rightBlock - 1; ++i)
  115. 			{
  116. 				int currentCount = histogram[blockMode[i]] + COUNT_IN_BLOCKS(leftBlock + 1, rightBlock - 1, blockMode[i]);
  117. 				if (currentCount > modeCount)
  118. 				{
  119. 					modeCount = currentCount;
  120. 				}
  121. 			}
  122.  
  123. 			// cleaning
  124. 			for (i = left; i <= lastInLeftBlockIndex; ++i)
  125. 			{
  126. 				histogram[a[i]] = 0;
  127. 			}
  128. 			for (i = firstInRightBlockIndex; i <= right; ++i)
  129. 			{
  130. 				histogram[a[i]] = 0;
  131. 			}
  132. 		}
  133.  
  134. 		printf("%d\n", modeCount);
  135. 	}
  136.  
  137. 	return 0;
  138. }
  139.  
Success #stdin #stdout 0s 130048KB
comments (?)
stdin
copy 
5 3
1 2 1 3 3
0 2
1 2
0 4
stdout
copy 
2
1
2
https://ideone.com/2tEMmD
language:
C++14 (gcc 8.3)
created:
8 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!