fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  3. #define pb push_back
  4. #define ll long long 
  5. using namespace std;
  6.  
  7. struct query
  8. {
  9. 	/*L denotes the left bound of query*/
  10. 	/*R denotes the right bound of the query*/
  11. 	/*i denotes the index */
  12. 	int L, R, i;
  13.  
  14. };
  15. int freq[1000005]; /* array for storing the frequency of elements*/ 
  16.  
  17. int A[30005]; /*Given array*/
  18. int BLK; /*size of bloks*/
  19. int cnt; /*stores the number of distinct elements in the range [currL: currR]
  20.  
  21. /*function for adding xth element into existing segment*/
  22. void add(int x)
  23. {
  24. 	freq[ A[x] ]++;
  25. 	if(freq[ A[x] ] == 1)
  26. 	cnt++;
  27. }
  28.  
  29. /*function for removing xth element from existing range*/ 
  30. void remove(int x)
  31. {
  32. 	freq[ A[x] ]--;
  33. 	if(freq[ A[x] ] == 0)
  34. 	cnt--;
  35. }
  36.  
  37. /*a comparator function to sort the queries*/
  38. bool comp(query q1,query q2)
  39. {
  40. 	int BLK1 = q1.L/BLK;
  41. 	int BLK2 = q2.L/BLK;
  42.  
  43. 	if(BLK1 != BLK2) /* if they lie in the same block*/
  44. 	return q1.L < q2.L;
  45. 	return q1.R < q2.R; 
  46. }
  47. void I_m_Beast()
  48. {
  49. 	int n,q,l,r;
  50. 	cin >> n;
  51. 	for(int i = 0; i < n; i++)
  52. 		cin >> A[i];
  53. 	BLK = sqrt(n);
  54.  
  55. 	cin >> q;
  56. 	vector< query > v; /*for storing the queries*/
  57. 	query q1;
  58. 	for(int i = 0; i < q; i++)
  59. 	{
  60. 		cin >> l >> r;
  61. 		l--;
  62. 		r--;
  63.  
  64. 		q1.L = l;
  65. 		q1.R = r;
  66. 		q1.i = i;
  67. 		v.pb(q1);
  68. 	}
  69. 	sort(v.begin(), v.end(), comp);
  70. 	int currL = 0,currR = -1;
  71. 	memset(freq, 0, sizeof(freq));
  72. 	int ans[q];/*array for storing answer of queries*/
  73. 	int L,R;
  74. 	for(int i = 0; i < v.size(); i++)
  75. 	{
  76. 		q1 = v[i];
  77. 		L = q1.L;
  78. 		R = q1.R;
  79. 		while(currR < R)
  80. 		{
  81. 			currR++;
  82. 			add(currR); 	
  83. 		}
  84. 		while(currR > R)
  85. 		{
  86. 			remove(currR); 	
  87. 			currR--;
  88. 		}
  89. 		while(currL < L)
  90. 		{
  91. 			remove(currL);
  92. 			currL++;
  93. 		}
  94. 		while(currL > L)
  95. 		{
  96. 			currL--;
  97. 			add(currL);
  98. 		}
  99. 		ans[q1.i] = cnt;
  100. 	}
  101. 	for(int i = 0; i < q; i++)
  102. 	 cout << ans[i] << endl;
  103. }
  104. int main()
  105. {
  106. 	fastio;
  107. 	int t;
  108. //	cin>>t;
  109. 	t = 1;
  110. 	while(t--)
  111. 	{
  112. 		I_m_Beast();
  113. 	}
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 7448KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/IIw3WP
problem DQUERY, based on SPOJ submission 26152863 (CPP14), 2020-06-16 12:20:24
language:
C++14 (gcc 8.3)
created:
4 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!