fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define all(x) (x).begin(), (x).end()
  5.  
  6. #ifdef KAZAR
  7.   #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  8. #else
  9.   #define eprintf(...) 0
  10. #endif
  11.  
  12. using namespace std;
  13.  
  14. template<class T> inline void umax(T &a,T b){if(a < b) a = b;}
  15. template<class T> inline void umin(T &a,T b){if(a > b) a = b;}
  16. template<class T> inline T abs(T a){return a > 0 ? a : -a;}
  17.  
  18. typedef long long ll;
  19. typedef pair<int, int> ii;
  20. typedef vector<int> vi;
  21.  
  22. const int inf = 1e9 + 143;
  23. const ll longinf = 1e18 + 143;
  24.  
  25. inline int read(){int x;scanf(" %d",&x);return x;}
  26.  
  27. const int N = 1e6 + 100;
  28.  
  29. int c[N], a[N];
  30. int l[N], r[N], ord[N];
  31. int ans[N];
  32.  
  33. int main(){
  34.  
  35. #ifdef KAZAR
  36.   freopen("f.input","r",stdin);
  37.   freopen("f.output","w",stdout);
  38.   freopen("error","w",stderr);
  39. #endif
  40.  
  41.   int n = read();
  42.   for (int i = 0; i < n; i++) {
  43.     a[i] = read();
  44.   }
  45.  
  46.   int len = 1;
  47.   while (len * len < n)
  48.     ++len;
  49.  
  50.   int q = read();
  51.   for (int i = 0; i < q; i++) {
  52.     l[i] = read() - 1;
  53.     r[i] = read() - 1;
  54.     ord[i] = i;
  55.   }
  56.  
  57.   sort(ord, ord + q, [&](int a,int b){
  58.     if (l[a] / len == l[b] / len)
  59.         return r[a] < r[b];
  60.     return l[a] / len < l[b] / len;
  61.   });
  62.  
  63.   int cur = 0;
  64.   auto add = [&cur](int id) {
  65.     if (c[a[id]] == 0)
  66.       ++cur;
  67.     c[a[id]]++;
  68.   };
  69.  
  70.   auto del = [&cur](int id) {
  71.     if (c[a[id]] == 1)
  72.       --cur;
  73.     c[a[id]]--;
  74.   };
  75.  
  76.   int L = 0, R = 0;
  77.   add(0);
  78.   for (int _i = 0; _i < q; _i++) {
  79.     int i = ord[_i];
  80.     while (R > r[i]) del(R--);
  81.     while (R < r[i]) add(++R);
  82.     while (L < l[i]) del(L++);
  83.     while (L > l[i]) add(--L);
  84.     ans[i] = cur;
  85.   }
  86.  
  87.   for (int i = 0; i < q; i++) {
  88.     printf("%d\n", ans[i]);
  89.   }
  90.  
  91.   return 0;
  92. }
  93.  
Runtime error #stdin #stdout 0.94s 26904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rL4acM
language:
C++14 (gcc 8.3)
created:
9 years 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!