fork download
copy 
  1. /////////////////////////////////////////////////////////////////////////
  2. // ------------------------------------------------------------------- //
  3. // | Author: Fananhkhoi | Luong Van Chanh High School for the gifted | //
  4. // ------------------------------------------------------------------- //
  5. /////////////////////////////////////////////////////////////////////////
  6.  
  7.  
  8.   /* -------------------[ TALK LESS & DO MORE ]------------------- */
  9.  
  10.  
  11. // #pragma GCC target("popcnt,lzcnt,bmi,bmi2,abm")
  12.  
  13. #include <bits/stdc++.h>
  14. #include<ext/pb_ds/assoc_container.hpp>
  15. #include<ext/pb_ds/tree_policy.hpp>
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18.  
  19. #define getBit(x, k) (((x) >> (k)) & 1)
  20. #define MASK(i) (1LL << (i))
  21. #define int long long
  22. //#define ll long long
  23. #define MOD 1000000007
  24. #define el "\n"
  25. #define vi vector<int>
  26. #define pii pair<int,int>
  27. #define vii vector<pii>
  28. #define FOU(i, l, r) for (int i = l; i <= r; i ++)
  29. #define FOD(i, r, l) for (int i = r; i >= l; i --)
  30. #define trav(a, x) for (auto &a : x )
  31. #define rep(i, a, b) for (int i = a; i < (b); i ++)
  32. //#define gcd __gcd
  33. #define fi first
  34. #define se second
  35. #define MP make_pair
  36. #define pb push_back
  37. #define pf push_front
  38. #define all(v) v.begin(), v.end()
  39. #define rev(v) reverse(all(v))
  40. #define srt(v) sort(all(v))
  41. #define grtsrt(v) sort(all(v), greater<int>())
  42. #define sz(x) (int) (x).size()
  43. #define maxHeap priority_queue<int>
  44. #define minHeap priority_queue<int, vi, greater<int>>
  45. #define Fix(a, b) cout << fixed << setprecision((b)) << (a)
  46.  
  47. int dx[] = {};
  48. int dy[] = {};
  49.  
  50. template<class _, class __>
  51.     bool minimize(_ &x, const __ y){
  52.         if(x > y){
  53.             x = y;
  54.             return true;
  55.         } else return false;
  56.     }
  57. template<class _, class __>
  58.     bool maximize(_ &x, const __ y){
  59.         if(x < y){
  60.             x = y;
  61.             return true;
  62.         } else return false;
  63.     }
  64.  
  65. inline int max(int a, int b){
  66.     return (a > b) ? a : b;
  67. }
  68.  
  69. inline int min(int a, int b){
  70.     return (a < b) ? a : b;
  71. }
  72.  
  73. inline int __lcm(int a, int b){
  74.     return a / __gcd(a, b) * b;
  75. }
  76.  
  77.  
  78. 	/* --------------------[ MAIN CODE ]--------------------- */
  79. const int MaxN = 1e6 + 50;
  80. const int oo = 2e18;
  81.  
  82. struct Querry{
  83.     int l, r, id;
  84.     bool operator < (const Querry &P){
  85.         return l < P.l;
  86.     }
  87. }q[MaxN];
  88.  
  89. int n, Q;
  90. int a[MaxN];
  91. int f[MaxN];
  92. int st[4 * MaxN];
  93. map<int,int> mp;
  94.  
  95. void update(int id, int l, int r, int pos, int val){
  96.     if (l > pos || r < pos){
  97.         return;
  98.     }
  99.     if (l == r){
  100.         st[id] = val;
  101.         return;
  102.     }
  103.     int mid = (l + r)/2;
  104.     update(2 * id, l, mid, pos, val);
  105.     update(2 * id + 1, mid + 1, r, pos, val);
  106.     st[id] = st[2 * id] + st[2 * id + 1];
  107. }
  108.  
  109. int get(int id, int l, int r, int u, int v){
  110.     if (u <= l && v >= r){
  111.         return st[id];
  112.     }
  113.     if (v < l || u > r || u > v){
  114.         return 0;
  115.     }
  116.     int mid = (l + r)/2;
  117.     return get(2 * id, l, mid, u, v) +
  118.            get(2 * id + 1, mid + 1, r, u, v);
  119. }
  120.  
  121. void prepare(){
  122.     for (pair<int,int> ii : mp){
  123.         update(1, 1, n, ii.se, 1);
  124.     }
  125. }
  126.  
  127. int ans[MaxN];
  128.  
  129. void inp(){
  130.     cin >> n;
  131.     for (int i = 1; i <= n; i ++){
  132.         cin >> a[i];
  133.     }
  134.     cin >> Q;
  135.     for (int i = 1; i <= Q; i ++){
  136.         cin >> q[i].l >> q[i].r;
  137.     }
  138.     for (int i = 1; i <= Q; i ++){
  139.         q[i].id = i;
  140.     }
  141. }
  142.  
  143. void sol(){
  144.     for (int i = n; i >= 1; i --){
  145.         if (mp.find(a[i]) != mp.end()){
  146.             f[i] = mp[a[i]];
  147.         }
  148.         else f[i] = -1;
  149.         mp[a[i]] = i;
  150.     }
  151.     prepare();
  152.     sort(q + 1, q + 1 + Q);
  153.  
  154.     int p = 1;
  155.     for (int i = 1; i <= Q; i ++){
  156.         while(p < q[i].l){
  157.             if (f[p] != - 1){
  158.                 update(1, 1, n, f[p], 1);
  159.                 update(1, 1, n, p, -1);
  160.             }
  161.             p ++;
  162.         }
  163.         ans[q[i].id] = get(1, 1, n, q[i].l, q[i].r);
  164.     }
  165.     for (int i = 1; i <= Q; i ++){
  166.         cout << ans[i] << el;
  167.     }
  168. }
  169.  
  170. int32_t main()
  171. {
  172.     ios_base::sync_with_stdio(false);
  173.     cin.tie(NULL);
  174.  
  175.     freopen("cau4.inp", "r", stdin);
  176.     freopen("cau4.out", "w", stdout);
  177.  
  178.     int t = 1;
  179.     bool multitest = 0;
  180.     if (multitest){
  181.         cin >> t;
  182.     }
  183.     while(t--){
  184.         inp();
  185.         sol();
  186.     }
  187.     return 0;
  188. }
  189.  
Success #stdin #stdout 0.01s 5912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rHh49L
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

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!