fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7. #define fc first
  8. #define sc second
  9. #define endl '\n'
  10. #define ll long long
  11. #define forn(i, n) for(int i = 0; i < (int) (n); i++)
  12. #define all(x) x.begin(), x.end()
  13. #define rall(x) x.rbegin(), x.rend()
  14.  
  15. const int MAXN = (int) 3e5 + 7, MAXK = (int) 1e6 + 7;
  16. const int MAXQ = (int) 2e5 + 7;
  17. int ans[MAXN], a[MAXN], cnt[MAXK];
  18. const int SZ = 555;
  19.  
  20. struct ev {
  21.     int i, l, r;
  22.     ev() {}
  23. };
  24.  
  25. ev q[MAXQ];
  26.  
  27. bool cmp(ev a, ev b) {
  28.     if (a.l / SZ != b.l / SZ) {
  29.         return a.l / SZ < b.l / SZ;
  30.     } else {
  31.         return a.r < b.r;
  32.     }
  33. }
  34.  
  35. int cur_ans = 0;
  36.  
  37. void add(int x) {
  38.     cnt[x]++;
  39.     if (cnt[x] == 1) {
  40.         cur_ans++;
  41.     }
  42. }
  43.  
  44. void rem(int x) {
  45.     cnt[x]--;
  46.     if (cnt[x] == 0) {
  47.         cur_ans--;
  48.     }
  49. }
  50.  
  51.  
  52. int main() {
  53.     int n, m, l, r, nl, nr;
  54.     scanf("%d", &n);
  55.     forn (i, n) {
  56.         scanf("%d", &a[i]);
  57.     }
  58.     scanf("%d", &m);
  59.     forn (i, m) {
  60.         scanf("%d%d", &q[i].l, &q[i].r);
  61.         q[i].i = i;
  62.     }
  63.     sort(q, q + m, cmp);
  64.     l = r = 0;
  65.     add(a[0]);
  66.     forn (i, m) {
  67.         nl = q[i].l, nr = q[i].r;
  68.         nl--, nr--;
  69.         while (nl < l) {
  70.             l--;
  71.             add(a[l]);
  72.         }
  73.         while (nr > r) {
  74.             r++;
  75.             add(a[r]);
  76.         }
  77.         while (nl > l) {
  78.             rem(a[l]);
  79.             l++;
  80.         }
  81.         while (nr < r) {
  82.             rem(a[r]);
  83.             r--;
  84.         }
  85.         ans[q[i].i] = cur_ans;
  86.     }
  87.     forn (i, m) {
  88.         printf("%d\n", ans[i]);
  89.     }
  90. }
  91.  
Time limit exceeded #stdin #stdout 5s 12064KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FZS3DQ
problem DQUERY, based on SPOJ submission 17220605 (C++14), 2016-07-03 20:36:41
language:
C++14 (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!