fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5. int anss = 0, ans[200005], a[30005], bs, frq[1000005];
  6. struct st
  7. {
  8.     int l, r, t;
  9. };
  10. bool cmp(const st &ss, const st &sk)
  11. {
  12.     int x_block = ss.l, y_block = sk.l;
  13.     if (x_block == y_block)
  14.     {   
  15.         if (x_block & 1)
  16.             return ss.r > sk.r;
  17.  
  18.         return ss.r < sk.r;
  19.     }
  20.     else
  21.         return x_block < y_block;
  22. }
  23. void add(int x)
  24. {
  25.     frq[a[x]]++;
  26.     if (frq[a[x]] == 1)
  27.         anss++;
  28. }
  29. void del(int x)
  30. {
  31.     frq[a[x]]--;
  32.     if (frq[a[x]] == 0)
  33.         anss--;
  34. }
  35.  
  36. int main()
  37. {
  38.     int i, n, ll, rr, j, k, l, q, lt = 1, rt = 0;
  39.     cin >> n;
  40.     bs = (int)sqrt(n);
  41.     for (i = 1; i <= n; i++)
  42.     {
  43.         cin >> a[i];
  44.     }
  45.     cin >> q;
  46.  
  47.     st b[200005];
  48.  
  49.     for (i = 0; i < q; i++)
  50.     {
  51.             cin >> b[i].l >> b[i].r;
  52.  
  53.             b[i].t = i;
  54.     }
  55.  
  56.     sort(b, b + q, cmp);
  57.     for (i = 0; i < q; i++)
  58.     {
  59.         ll = b[i].l, rr = b[i].r;
  60.  
  61.         while (rr > rt)
  62.         {
  63.             add(++rt);
  64.         }
  65.         while (ll < lt)
  66.         {
  67.             add(--lt);
  68.         }
  69.  
  70.         while (ll > lt)
  71.         {
  72.             del(lt++);
  73.         }
  74.         while (rr < rt)
  75.         {
  76.             del(rt--);
  77.         }
  78.  
  79.         ans[b[i].t] = anss;
  80.     }
  81.     for (i = 0; i < q; i++)
  82.         cout << ans[i] << "\n";
  83. }
Success #stdin #stdout 0s 4940KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IUbLVW
problem DQUERY, based on SPOJ submission 27531346 (CPP14), 2021-03-09 09:39:51
language:
C++14 (gcc 8.3)
created:
3 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!