fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <set>
  5. #include <utility>
  6. #include <array>
  7. #include <string.h>
  8. #include <math.h>
  9. template<typename T>
  10. void fast_scan(T &number) {
  11. 	number = 0;
  12. 	bool negative = false;
  13. 	register int  c = getchar();
  14. 	if (c == '-') {
  15. 		negative = true;
  16. 		c = getchar();
  17. 	}
  18. 	for (; c > 47 && c < 58; c = getchar()) {
  19. 		number = 10 * number + (c - 48);
  20. 	}
  21. 	if (negative) number *= -1;
  22. }
  23. template<typename T1>
  24. struct pair {
  25. 	T1 first,second;
  26. 	static T1 compare;
  27. 	pair() {
  28.  
  29. 	}
  30. 	pair(T1 x, T1 y) : first(x),second(y){	
  31. 	}
  32. 	void operator()(T1 x, T1 y) {
  33. 		first = x;
  34. 		second = y;
  35. 	}
  36. 	bool operator<(const pair<T1> other) const {
  37. 		if ((first/compare) == (other.first/compare)) return second < other.second;
  38. 		return (first / compare) < (other.first / compare);
  39. 	}
  40. };
  41. template<typename T2>
  42. T2 pair<T2>::compare = 1;
  43. int main() {
  44. 	size_t n; fast_scan(n);
  45. 	pair<size_t>::compare = size_t(sqrt(n));
  46. 	struct pair<size_t> pair1;
  47. 	std::vector<int>v(n);
  48. 	for (size_t i = 0; i < n; i++) {
  49. 		fast_scan(v[i]);
  50. 	}
  51. 	std::set< std::pair< struct pair<size_t>, size_t> > set;
  52. 	size_t q; fast_scan(q);
  53. 	std::vector<long long int>v1(q);
  54. 	size_t i = 0;
  55. 	while (q) {
  56. 		size_t l, r; fast_scan(l); fast_scan(r); --l; --r;
  57. 		pair1(l, r);
  58. 		set.insert(std::make_pair(pair1,i));
  59. 		q--;
  60. 		i++;
  61. 	}
  62. 	int *a = new int[1000000];
  63. 	memset(a, 0,1000000);
  64. 	auto it = set.begin();
  65. 	size_t l = ((*it).first).first; size_t r = l; long long int count = 0;
  66. 	a[v[l]]++; count++;
  67. 	while (it!=set.end()) {
  68. 		while (l < ((*it).first).first) {
  69. 			l++;
  70. 			if (l < ((*it).first).first) {
  71. 				a[v[l]]--;
  72. 				if (a[v[l]] == 0) --count;
  73. 			}
  74. 		}
  75. 		while ((l > ((*it).first).first)) {
  76. 			l--;
  77. 			if ((l > ((*it).first).first)) {
  78. 				a[v[l]]++;
  79. 				if (a[v[l]] == 1) ++count;
  80. 			}
  81. 		}
  82. 		while (((*it).first).second > r) {
  83. 			r++;
  84. 			a[v[r]]++;
  85. 			if (a[v[r]] == 1) ++count;
  86. 		}
  87. 		while (((*it).first).second < r) {
  88. 			r--;
  89. 			a[v[r]]--;
  90. 			if (a[v[r]] == 0) --count;
  91. 		}
  92. 		v1[(*it).second] = count;
  93. 		it++;
  94. 	}
  95. 	for (auto i = v1.begin(); i != v1.end(); i++) std::cout << *i << '\n';
  96. }
  97.  
Runtime error #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EacVYA
problem DQUERY, based on SPOJ submission 23924292 (CPP14), 2019-06-15 22:33:29
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!