test/ds/st.test.cpp

• View this file on GitHub
• Last update: 2025-10-01 17:55:45+08:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• src/ds/st.hpp
• src/misc/read.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#include "../../src/ds/st.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  vector<int> a(n);
  for (auto& x : a) {
    x = read();
  }
  SparseTable st(a, [](int lhs, int rhs) { return min(lhs, rhs); });
  while (q--) {
    int l = read(), r = read();
    cout << st.query(l, r) << "\n";
  }
  return 0;
}

#line 1 "test/ds/st.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#line 1 "src/ds/st.hpp"
template <typename T, typename Op>
struct SparseTable {
  int n, m;
  Op op;
  vector<vector<T>> data;
  SparseTable(vector<T> vec, Op op)
      : n(vec.size()), m(32 - __builtin_clz(n)), op(op), data(m, vector<T>(n)) {
    data[0] = move(vec);
    for (int j = 1; j < m; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        data[j][i] = op(data[j - 1][i], data[j - 1][i + (1 << (j - 1))]);
  }
  T query(int l, int r) const {
    int q = __lg(r - l);
    return op(data[q][l], data[q][r - (1 << q)]);
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 8 "test/ds/st.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  vector<int> a(n);
  for (auto& x : a) {
    x = read();
  }
  SparseTable st(a, [](int lhs, int rhs) { return min(lhs, rhs); });
  while (q--) {
    int l = read(), r = read();
    cout << st.query(l, r) << "\n";
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	99 ms	46 MB
g++	max_random_01	AC	93 ms	46 MB
g++	max_random_02	AC	89 ms	46 MB
g++	max_random_03	AC	86 ms	46 MB
g++	max_random_04	AC	86 ms	46 MB
g++	random_00	AC	75 ms	37 MB
g++	random_01	AC	74 ms	43 MB
g++	random_02	AC	40 ms	7 MB
g++	random_03	AC	35 ms	40 MB
g++	random_04	AC	31 ms	27 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	4 MB
g++	small_values_00	AC	77 ms	46 MB
g++	small_width_query_00	AC	102 ms	46 MB
g++	small_width_query_01	AC	114 ms	46 MB
g++	small_width_query_02	AC	113 ms	46 MB
g++	small_width_query_03	AC	103 ms	46 MB
g++	small_width_query_04	AC	114 ms	46 MB

Back to top page