test/yosupo/staticrmq.SparseTable.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• Sparse-Table (src/DataStructure/SparseTable.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/DataStructure/SparseTable.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<int> a(N);
 for (int i= 0; i < N; ++i) cin >> a[i];
 SparseTable st(a, [](int l, int r) { return min(l, r); });
 while (Q--) {
  int l, r;
  cin >> l >> r;
  cout << st.prod(l, r) << '\n';
 }
 return 0;
}

#line 1 "test/yosupo/staticrmq.SparseTable.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/DataStructure/SparseTable.hpp"
template <class T, class F> class SparseTable {
 std::vector<std::vector<T>> dat;
 F f;
public:
 SparseTable() {}
 SparseTable(const std::vector<T> &v, const F &f): f(f) {
  int n= v.size(), log= n > 1 ? 31 - __builtin_clz(n - 1) : 0;
  dat.resize(log + 1), dat[0].assign(v.begin(), v.end());
  for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
   for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= f(dat[i][j], dat[i][j + I]);
 }
 // [l, r)
 T prod(int l, int r) const {
  if (r == l + 1) return dat[0][l];
  int k= 31 - __builtin_clz(r - l - 1);
  return f(dat[k][l], dat[k][r - (1 << k)]);
 }
};
#line 7 "test/yosupo/staticrmq.SparseTable.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<int> a(N);
 for (int i= 0; i < N; ++i) cin >> a[i];
 SparseTable st(a, [](int l, int r) { return min(l, r); });
 while (Q--) {
  int l, r;
  cin >> l >> r;
  cout << st.prod(l, r) << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	max_random_00	AC	135 ms	40 MB
g++-13	max_random_01	AC	143 ms	40 MB
g++-13	max_random_02	AC	137 ms	40 MB
g++-13	max_random_03	AC	138 ms	40 MB
g++-13	max_random_04	AC	136 ms	40 MB
g++-13	random_00	AC	112 ms	32 MB
g++-13	random_01	AC	119 ms	37 MB
g++-13	random_02	AC	70 ms	7 MB
g++-13	random_03	AC	54 ms	35 MB
g++-13	random_04	AC	50 ms	23 MB
g++-13	small_00	AC	5 ms	4 MB
g++-13	small_01	AC	4 ms	4 MB
g++-13	small_02	AC	5 ms	4 MB
g++-13	small_03	AC	4 ms	4 MB
g++-13	small_04	AC	4 ms	4 MB
g++-13	small_05	AC	4 ms	4 MB
g++-13	small_06	AC	4 ms	4 MB
g++-13	small_07	AC	4 ms	4 MB
g++-13	small_08	AC	4 ms	4 MB
g++-13	small_09	AC	4 ms	4 MB
g++-13	small_values_00	AC	123 ms	40 MB
g++-13	small_width_query_00	AC	147 ms	40 MB
g++-13	small_width_query_01	AC	146 ms	40 MB
g++-13	small_width_query_02	AC	147 ms	40 MB
g++-13	small_width_query_03	AC	147 ms	40 MB
g++-13	small_width_query_04	AC	155 ms	40 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	max_random_00	AC	138 ms	40 MB
clang++-18	max_random_01	AC	142 ms	40 MB
clang++-18	max_random_02	AC	134 ms	40 MB
clang++-18	max_random_03	AC	133 ms	40 MB
clang++-18	max_random_04	AC	132 ms	40 MB
clang++-18	random_00	AC	108 ms	32 MB
clang++-18	random_01	AC	116 ms	38 MB
clang++-18	random_02	AC	73 ms	7 MB
clang++-18	random_03	AC	49 ms	35 MB
clang++-18	random_04	AC	48 ms	23 MB
clang++-18	small_00	AC	5 ms	4 MB
clang++-18	small_01	AC	4 ms	4 MB
clang++-18	small_02	AC	4 ms	4 MB
clang++-18	small_03	AC	4 ms	4 MB
clang++-18	small_04	AC	4 ms	4 MB
clang++-18	small_05	AC	4 ms	4 MB
clang++-18	small_06	AC	4 ms	4 MB
clang++-18	small_07	AC	4 ms	4 MB
clang++-18	small_08	AC	4 ms	4 MB
clang++-18	small_09	AC	4 ms	4 MB
clang++-18	small_values_00	AC	119 ms	40 MB
clang++-18	small_width_query_00	AC	149 ms	40 MB
clang++-18	small_width_query_01	AC	148 ms	40 MB
clang++-18	small_width_query_02	AC	147 ms	40 MB
clang++-18	small_width_query_03	AC	143 ms	40 MB
clang++-18	small_width_query_04	AC	150 ms	40 MB

Back to top page