fork download
copy 
  1. /* Priyansh Agarwal*/
  2. #include<bits/stdc++.h>
  3. #include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. #include<algorithm>
  6. #include<unordered_map>
  7. #include<vector>
  8. #include<unordered_set>
  9. #include<set>
  10. #include<map>
  11. #include<queue>
  12. #include<stack>
  13. #include<map>
  14. #include<chrono>
  15. using namespace std;
  16. using namespace __gnu_pbds;
  17. using namespace std::chrono;
  18. #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  19. #define MOD 1000000007
  20. #define MOD1 998244353
  21. #define nline "\n"
  22. #define pb push_back
  23. #define mp make_pair
  24. #define ff first
  25. #define ss second
  26. #define PI 3.141592653589793238462
  27. #define debug(x) cout << #x << " " << x <<endl;
  28. #define set_bits __builtin_popcount
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef long double lld;
  32. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds;
  33. /*---------------------------------------------------------------------------------------------------------------------------*/
  34. ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
  35. ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  36. void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size 3
  37. ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
  38. ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
  39. bool revsort(ll a, ll b) {return a > b;}
  40. void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
  41. ll combination(ll n, ll r, ll m, ll* fact) {ll val1 = fact[n]; ll val2 = mminvprime(fact[r], m); ll val3 = mminvprime(fact[n - r], m); return ((val1 * val2) % m * val3) % m;}
  42. void google(int t) {cout << "Case #" << t << ": ";}
  43. vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
  44. /*--------------------------------------------------------------------------------------------------------------------------*/
  45. int block_size;
  46. bool compare(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
  47. {
  48. 	int b1 = p1.ff.ff / block_size;
  49. 	int b2 = p2.ff.ff / block_size;
  50. 	if (b1 == b2)
  51. 		return b1 % 2 == 0 ? (p1.ff.ss < p2.ff.ss) : (p1.ff.ss > p2.ff.ss);
  52. 	return b1 < b2;
  53. }
  54. int main()
  55. {
  56. 	fastio();
  57. // #ifndef ONLINE_JUDGE
  58. // 	freopen("Input.txt", "r", stdin);
  59. // 	freopen("Output.txt", "w", stdout);
  60. // 	freopen("Error.txt", "w", stderr);
  61. // #endif
  62. 	auto start1 = high_resolution_clock::now();
  63. 	int n, q;
  64. 	cin >> n >> q;
  65. 	block_size = int(sqrt(n + 0.0) + 1);
  66. 	int arr[n];
  67. 	for (int i = 0; i < n; i++)
  68. 		cin >> arr[i];
  69. 	int start = 0;
  70. 	int end = -1;
  71. 	vector<pair<pair<int, int>, int>> ans(q);
  72. 	map<int, int> m1;
  73. 	for (int i = 0; i < q; i ++)
  74. 	{
  75. 		int a, b;
  76. 		cin >> a >> b;
  77. 		ans[i] = {{a, b}, i};
  78. 	}
  79. 	sort(ans.begin(), ans.end(), compare);
  80. 	int *ans1 = new int[q];
  81. 	int count = 0;
  82. 	for (auto i : ans)
  83. 	{
  84. 		pair<pair<int, int>, int> p1 = i;
  85. 		int right = p1.ff.ss - 1;
  86. 		int left = p1.ff.ff - 1;
  87. 		while (start < left)
  88. 		{
  89. 			int x = arr[start];
  90. 			m1[x]--;
  91. 			if (m1[x] == 0)
  92. 				count--;
  93. 			start++;
  94. 		}
  95. 		while (start > left)
  96. 		{
  97. 			start--;
  98. 			int x = arr[start];
  99. 			m1[x]++;
  100. 			if (m1[x] == 1)
  101. 				count++;
  102. 		}
  103. 		while (end < right)
  104. 		{
  105. 			end++;
  106. 			int x = arr[end];
  107. 			m1[x]++;
  108. 			if (m1[x] == 1)
  109. 				count++;
  110. 		}
  111. 		while (end > right)
  112. 		{
  113. 			int x = arr[end];
  114. 			m1[x]--;
  115. 			if (m1[x] == 0)
  116. 				count--;
  117. 			end--;
  118. 		}
  119. 		ans1[p1.ss] = count;
  120. 	}
  121. 	for (int i = 0; i < q; i++)
  122. 		cout << ans1[i] << "\n";
  123. 	auto stop1 = high_resolution_clock::now();
  124. 	auto duration = duration_cast<microseconds>(stop1 - start1);
  125. // #ifndef ONLINE_JUDGE
  126. // 	cerr << "Time: " << duration.count() / 1000.0 << endl;
  127. // #endif
  128. 	return 0;
  129. }
Runtime error #stdin #stdout 3.07s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hMUwEF
language:
C++14 (gcc 8.3)
created:
3 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!