fork(4) download
copy 
  1. /*
  2.     AUTHOR:         BHUVNESH JAIN
  3.     INSTITUITION:   BITS PILANI, PILANI
  4. */
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define fastio          std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  10. #define PAUSE_EXE       assert(false)
  11. #define MAX             30002
  12. #define MAX2            200002
  13. #define SIZE            1000002
  14. #define MOD             1000000007LL
  15. #define REP(i,n)        for(__typeof(n) i=0; i<n; ++i)
  16. #define CREP(i,n)       for(__typeof(n) i=n-1; i>=0; --i)
  17. #define MYREP(i,a,b)    for(__typeof(a) i=a; i<=b; ++i)
  18. #define MYCREP(i,a,b)   for(__typeof(a) i=b; i>=a; --i)
  19. #define sz(a)           int((a).size())
  20. #define pb              push_back
  21. #define mp              make_pair
  22. #define fi              first
  23. #define sec             second
  24. #define all(c)          (c).begin(),(c).end()
  25. #define allr(c)         (c).rbegin(),(c).rend()
  26. #define loop(c,i)       for(typeof(c.begin()) i = c.begin(); i != c.end(); i++)
  27. #define loopr(c,i)      for(typeof(c.end()) i = c.end(); i != c.begin(); )
  28.  
  29. int bucket_size, num[MAX], freq[SIZE];
  30.  
  31. int ans[MAX2];
  32.  
  33. struct query
  34. {
  35.     int ind, l, r;
  36. }q[MAX2];
  37.  
  38. bool cmp(query a, query b)
  39. {
  40.     int ax = a.l/bucket_size;
  41.     int bx = b.l/bucket_size;
  42.     if (ax != bx)
  43.         return ax < bx;
  44.     return a.r < b.r;
  45. }
  46.  
  47. int main()
  48. {
  49.     #ifndef ONLINE_JUDGE
  50.         freopen("inp.txt", "r", stdin);
  51.     #endif
  52.     int n, m;
  53.     scanf("%d", &n);
  54.     MYREP(i, 1, n)
  55.         scanf("%d", &num[i]);
  56.     scanf("%d", &m);
  57.     REP(i, m)
  58.     {
  59.         // inPos(q[i].l) , inPos(q[i].r);
  60.         scanf("%d %d", &q[i].l, &q[i].r);
  61.         q[i].ind = i;
  62.     }
  63.     bucket_size = ceil(sqrt(n));
  64.     sort(q, q+m, cmp);
  65.     int start, end;
  66.     int sum;
  67.     start = end = 0;
  68.     sum = 0;
  69.     REP(i, m)
  70.     {
  71.         while (start < q[i].l)
  72.         {
  73.             --freq[num[start]];
  74.             if (freq[num[start]] == 0)
  75.                 sum--;
  76.             ++start;
  77.         }
  78.         while (end > q[i].r)
  79.         {
  80.             --freq[num[end]];
  81.             if (freq[num[end]] == 0)
  82.                 sum--;
  83.             --end;
  84.         }
  85.  
  86.         while (start > q[i].l)
  87.         {
  88.             --start;
  89.             ++freq[num[start]];
  90.             if (freq[num[start]] == 1)
  91.                 sum++;
  92.         }
  93.         while (end < q[i].r)
  94.         {
  95.             ++end;
  96.             ++freq[num[end]];
  97.             if (freq[num[end]] == 1)
  98.                 sum++;
  99.         }
  100.  
  101.         ans[q[i].ind] = sum;
  102.     }
  103.     REP(i, m)
  104.         printf("%d\n", ans[i]);
  105.     return 0;
  106. }
Success #stdin #stdout 0s 10568KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/91Uwc4
language:
C++ (gcc 8.3)
created:
8 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!