fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e5 + 5;
  5. const int S = 320;
  6. //
  7. struct query
  8. {
  9.     int l, r, a, b, id;
  10.     //
  11.     bool operator < (const query &other)
  12.     {
  13.         if (l / S != other.l / S)
  14.             return l < other.l;
  15.         return l / S & 1 ? r < other.r : r > other.r;
  16.     }
  17. };
  18. //
  19. int n, q, A[mx];
  20. int cnt[mx];
  21. pair<int, int> block[S], ans[mx];
  22. query Q[mx];
  23. //
  24. void update (int pos, int val)
  25. {
  26.     if (pos == 0)
  27.         return;
  28.     //
  29.     int id = pos / S;
  30.     //
  31.     block[id].first += val;
  32.     if (cnt[pos] == 0)
  33.         ++block[id].second;
  34.     cnt[pos] += val;
  35.     if (cnt[pos] == 0)
  36.         --block[id].second;
  37. }
  38. void operator += (pair<int, int> &a, const pair<int, int> &b)
  39. {
  40.     a.first += b.first;
  41.     a.second += b.second;
  42. }
  43. pair<int, int> get (int a, int b)
  44. {
  45.     int block_a = a / S, block_b = b / S;
  46.     pair<int, int> res(0, 0);
  47.     //
  48.     if (block_a == block_b)
  49.     {
  50.         for (int i = a; i <= b; ++i)
  51.             res += make_pair(cnt[i], cnt[i] > 0);
  52.         return res;
  53.     }
  54.     ++block_a, ++b;
  55.     for (int i = block_a; i < block_b; ++i)
  56.         res += block[i];
  57.     for (int i = a; i < block_a * S; ++i)
  58.         res += make_pair(cnt[i], cnt[i] > 0);
  59.     for (int i = block_b * S; i < b; ++i)
  60.         res += make_pair(cnt[i], cnt[i] > 0);
  61.     return res;
  62. }
  63. void calc (void)
  64. {
  65.     int l = 0, r = 0;
  66.     //
  67.     for (int i = 1; i <= q; ++i)
  68.     {
  69.         while (l < Q[i].l)
  70.             update(A[l++], -1);
  71.         while (l > Q[i].l)
  72.             update(A[--l], 1);
  73.         while (r < Q[i].r)
  74.             update(A[++r], 1);
  75.         while (r > Q[i].r)
  76.             update(A[r--], -1);
  77.         ans[Q[i].id] = get(Q[i].a, Q[i].b);
  78.     }
  79. }
  80. //
  81. void process (void)
  82. {
  83.     cin >> n >> q;
  84.     for (int i = 1; i <= n; ++i)
  85.         cin >> A[i];
  86.     for (int i = 1; i <= q; ++i)
  87.         cin >> Q[i].l >> Q[i].r >> Q[i].a >> Q[i].b,
  88.         Q[i].id = i;
  89.  
  90.     sort(Q + 1, Q + q + 1);
  91.     calc();
  92.  
  93.     for (int i = 1; i <= q; ++i)
  94.         cout << ans[i].first << ' ' << ans[i].second << '\n';
  95. }
  96. //
  97. signed main (void)
  98. {
  99.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  100.     process();
  101. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xRCMlD
https://m...content-available-to-author-only...j.com/problem/504
language:
C++14 (gcc 8.3)
created:
7 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!