fork(1) download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <string.h>
  4. #include <math.h>
  5. template<typename T>
  6. void fast_scan(T &number) {
  7. 	number = 0;
  8. 	bool negative = false;
  9. 	register int  c = getchar();
  10. 	if (c == '-') {
  11. 		negative = true;
  12. 		c = getchar();
  13. 	}
  14. 	for (; c > 47 && c < 58; c = getchar()) {
  15. 		number = 10 * number + (c - 48);
  16. 	}
  17. 	if (negative) number *= -1;
  18. }
  19. template<typename T, typename T1, typename T2>
  20. class query {
  21. public:
  22. 	T first, second, third;
  23. 	static T comp;
  24. 	static T1 * index;
  25. public:
  26. 	query() {
  27.  
  28. 	}
  29. 	query(T x, T y,T z) : first(x), second(y),third(z) {
  30.  
  31.  
  32. 	}
  33. public:
  34. 	static T1* initialise(T2 num) {
  35. 		index = new T1[num];
  36. 		return index;
  37. 	}
  38. public:
  39. 	query& operator()(T x, T y, T z) {
  40. 		first = x;
  41. 		second = y;
  42. 		third = z;
  43. 		return *this;
  44. 	}
  45. 	bool operator<(const query & other) const {
  46. 		T comp1 = T (first /comp); T comp2 = T (other.first/comp);
  47. 		if (comp1 == comp2) return second < other.second;
  48. 		return comp1 < comp2;
  49. 	}
  50. };
  51. template<typename T, typename T1, typename T2>
  52. T query<T, T1, T2>::comp;
  53. template<typename T, typename T1, typename T2>
  54. T1 * query<T, T1, T2>::index = nullptr;
  55. int main() {
  56. 	size_t n; fast_scan(n);
  57. 	int* input = new int[n]; for (size_t i = 0; i < n; i++) fast_scan(input[i]); size_t q; fast_scan(q);
  58. 	query<size_t, long long int, size_t> que; que.comp = size_t(sqrt(n));
  59. 	long long int* count_arr = que.initialise(q);
  60. 	std::multiset< query<size_t, long long int, size_t> > set;
  61. 	for (size_t i = 0; i < q; i++) {
  62. 		size_t l, r; fast_scan(l); fast_scan(r); --l; --r;
  63. 		set.insert(que(l, r, i));
  64. 	}
  65. 	int * F = new int[1000001]; memset(F, 0, 1000001);
  66. 	auto i = set.begin();
  67. 	size_t l, r; l = r = (i->first);  F[input[l]]++; long long int count = 1;
  68. 	while (i != set.end()) {
  69. 		while (l < (i->first)) {
  70. 			if ((--F[input[l]]) == 0) --count;
  71. 			l++;
  72. 		}
  73. 		while (l > (i->first)) {
  74. 			--l;
  75. 			if ((++F[input[l]]) == 1) ++count;
  76. 		}
  77. 		while (r < (i->second)) {
  78. 			++r;
  79. 			if ((++F[input[r]]) == 1) ++count;
  80. 		}
  81. 		while (r > (i->second)) {
  82. 			if ((--F[input[l]]) == 0) --count;
  83. 			--r;
  84. 		}
  85. 		count_arr[i->third] = count;
  86. 		i++;
  87. 	}
  88. 	for (size_t j = 0; j < q; j++) std::cout << count_arr[j] << '\n';
  89. }
  90.  
Success #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NyhLqI
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!