test/hackerrank/range-counting-query.Mo.test.cpp

• View this file on GitHub
• Last update: 2025-08-11 23:50:29+09:00
• Problem: https://www.hackerrank.com/contests/happy-query-contest/challenges/range-counting-query

Depends on

• Mo's Algorithm (src/Misc/Mo.hpp)

Code

// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/happy-query-contest/challenges/range-counting-query
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/Mo.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> A(N), cnt(N), sum(N + 2);
 for (int i= 0; i < N; i++) cin >> A[i], A[i]--;
 Mo mo;
 int Q;
 cin >> Q;
 vector<int> x(Q), y(Q), ans(Q);
 for (int q= 0; q < Q; q++) {
  int l, r;
  cin >> l >> r >> x[q] >> y[q];
  mo.query(--l, r);
 }
 auto add= [&](int k) { sum[++cnt[A[k]]]++; };
 auto erase= [&](int k) { sum[cnt[A[k]]--]--; };
 auto out= [&](int q) { ans[q]= sum[x[q]] - sum[y[q] + 1]; };
 mo.run(add, erase, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << '\n';
 return 0;
}

#line 1 "test/hackerrank/range-counting-query.Mo.test.cpp"
// competitive-verifier: PROBLEM https://www.hackerrank.com/contests/happy-query-contest/challenges/range-counting-query
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Misc/Mo.hpp"
#include <algorithm>
#include <numeric>
#include <cmath>
struct Mo {
 std::vector<int> L, R;
 Mo() {}
 void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
 template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
  int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(q));
  std::vector<int> ord(q);
  std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int a, int b) {
   int ablk= L[a] / bs, bblk= L[b] / bs;
   return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
  });
  int l= 0, r= 0;
  for (auto i: ord) {
   while (l > L[i]) add_left(--l);
   while (r < R[i]) add_right(r++);
   while (l < L[i]) erase_left(l++);
   while (r > R[i]) erase_right(--r);
   out(i);
  }
 }
 template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
};
#line 7 "test/hackerrank/range-counting-query.Mo.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> A(N), cnt(N), sum(N + 2);
 for (int i= 0; i < N; i++) cin >> A[i], A[i]--;
 Mo mo;
 int Q;
 cin >> Q;
 vector<int> x(Q), y(Q), ans(Q);
 for (int q= 0; q < Q; q++) {
  int l, r;
  cin >> l >> r >> x[q] >> y[q];
  mo.query(--l, r);
 }
 auto add= [&](int k) { sum[++cnt[A[k]]]++; };
 auto erase= [&](int k) { sum[cnt[A[k]]--]--; };
 auto out= [&](int q) { ans[q]= sum[x[q]] - sum[y[q] + 1]; };
 mo.run(add, erase, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	000	AC	5 ms	4 MB
g++-13	001	AC	114 ms	7 MB
g++-13	002	AC	114 ms	7 MB
g++-13	003	AC	114 ms	7 MB
g++-13	004	AC	117 ms	7 MB
g++-13	005	AC	117 ms	7 MB
g++-13	006	AC	117 ms	7 MB
g++-13	007	AC	95 ms	7 MB
g++-13	008	AC	96 ms	7 MB
g++-13	009	AC	70 ms	6 MB
g++-13	010	AC	52 ms	5 MB
g++-13	011	AC	50 ms	5 MB
g++-13	012	AC	62 ms	6 MB
g++-13	013	AC	53 ms	5 MB
g++-13	014	AC	47 ms	6 MB
g++-13	015	AC	57 ms	6 MB
g++-13	016	AC	90 ms	6 MB
g++-13	017	AC	79 ms	6 MB
g++-13	018	AC	66 ms	6 MB
g++-13	019	AC	54 ms	5 MB
g++-13	020	AC	69 ms	6 MB
g++-13	021	AC	48 ms	5 MB
g++-13	022	AC	93 ms	6 MB
g++-13	023	AC	98 ms	7 MB
g++-13	024	AC	97 ms	7 MB
g++-13	025	AC	108 ms	7 MB
g++-13	026	AC	109 ms	7 MB
g++-13	027	AC	109 ms	7 MB
clang++-18	000	AC	5 ms	4 MB
clang++-18	001	AC	120 ms	7 MB
clang++-18	002	AC	120 ms	7 MB
clang++-18	003	AC	119 ms	7 MB
clang++-18	004	AC	127 ms	7 MB
clang++-18	005	AC	127 ms	7 MB
clang++-18	006	AC	126 ms	7 MB
clang++-18	007	AC	97 ms	7 MB
clang++-18	008	AC	93 ms	7 MB
clang++-18	009	AC	73 ms	6 MB
clang++-18	010	AC	55 ms	5 MB
clang++-18	011	AC	53 ms	5 MB
clang++-18	012	AC	62 ms	6 MB
clang++-18	013	AC	56 ms	5 MB
clang++-18	014	AC	47 ms	6 MB
clang++-18	015	AC	58 ms	6 MB
clang++-18	016	AC	93 ms	6 MB
clang++-18	017	AC	85 ms	6 MB
clang++-18	018	AC	71 ms	6 MB
clang++-18	019	AC	58 ms	5 MB
clang++-18	020	AC	65 ms	6 MB
clang++-18	021	AC	46 ms	5 MB
clang++-18	022	AC	88 ms	7 MB
clang++-18	023	AC	93 ms	7 MB
clang++-18	024	AC	93 ms	7 MB
clang++-18	025	AC	102 ms	7 MB
clang++-18	026	AC	106 ms	7 MB
clang++-18	027	AC	103 ms	7 MB

Back to top page