fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty