This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#include "../SparseTable.cpp"
int op(int a, int b) { return min(a, b); }
int e() { return 1000000000; }
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
disjointsparsetable<int, op, e> st(a);
while (m--) {
int l, r;
cin >> l >> r;
cout << st.query(l, r) << "\n";
}
}
#line 1 "test/SparseTableDisjoint.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq
#line 1 "SparseTable.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T, T (*op)(T, T), T (*e)()>
struct sparsetable {
vector<vector<T>> table;
vector<int> logtable;
sparsetable() = default;
sparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= (int)v.size()) len++;
table.assign(len, vector<T>(1 << len));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
for (int j = 0; j + (1 << i) <= (1 << len); j++) {
table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
logtable.resize((int)v.size() + 1);
for (int i = 2; i < (int)logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
assert(l <= r);
if (l == r) return e();
int len = logtable[r - l];
return op(table[len][l], table[len][r - (1 << len)]);
}
};
template <class T, T (*op)(T, T), T (*e)()>
struct disjointsparsetable {
vector<vector<T>> table;
vector<int> logtable;
disjointsparsetable() = default;
disjointsparsetable(vector<T> v) {
int len = 0;
while ((1 << len) <= v.size()) len++;
table.assign(len, vector<T>(1 << len, e()));
for (int i = 0; i < (int)v.size(); i++) table[0][i] = v[i];
for (int i = 1; i < len; i++) {
int shift = 1 << i;
for (int j = 0; j < (int)v.size(); j += shift << 1) {
int t = min(j + shift, (int)v.size());
table[i][t - 1] = v[t - 1];
for (int k = t - 2; k >= j; k--) table[i][k] = op(v[k], table[i][k + 1]);
if (v.size() <= t) break;
table[i][t] = v[t];
int r = min(t + shift, (int)v.size());
for (int k = t + 1; k < r; k++) table[i][k] = op(table[i][k - 1], v[k]);
}
}
logtable.resize(1 << len);
for (int i = 2; i < logtable.size(); i++) {
logtable[i] = logtable[(i >> 1)] + 1;
}
}
T query(int l, int r) {
if (l == r) return e();
if (l >= --r) return table[0][l];
int len = logtable[l ^ r];
return op(table[len][l], table[len][r]);
};
};
#line 3 "test/SparseTableDisjoint.test.cpp"
int op(int a, int b) { return min(a, b); }
int e() { return 1000000000; }
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
disjointsparsetable<int, op, e> st(a);
while (m--) {
int l, r;
cin >> l >> r;
cout << st.query(l, r) << "\n";
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | max_random_00 |
![]() |
164 ms | 48 MB |
g++ | max_random_01 |
![]() |
168 ms | 48 MB |
g++ | max_random_02 |
![]() |
163 ms | 48 MB |
g++ | max_random_03 |
![]() |
162 ms | 48 MB |
g++ | max_random_04 |
![]() |
161 ms | 48 MB |
g++ | random_00 |
![]() |
134 ms | 47 MB |
g++ | random_01 |
![]() |
142 ms | 48 MB |
g++ | random_02 |
![]() |
77 ms | 8 MB |
g++ | random_03 |
![]() |
61 ms | 48 MB |
g++ | random_04 |
![]() |
65 ms | 46 MB |
g++ | small_00 |
![]() |
5 ms | 4 MB |
g++ | small_01 |
![]() |
4 ms | 4 MB |
g++ | small_02 |
![]() |
4 ms | 4 MB |
g++ | small_03 |
![]() |
4 ms | 4 MB |
g++ | small_04 |
![]() |
4 ms | 4 MB |
g++ | small_05 |
![]() |
4 ms | 4 MB |
g++ | small_06 |
![]() |
4 ms | 4 MB |
g++ | small_07 |
![]() |
4 ms | 4 MB |
g++ | small_08 |
![]() |
4 ms | 4 MB |
g++ | small_09 |
![]() |
4 ms | 4 MB |
g++ | small_values_00 |
![]() |
148 ms | 48 MB |
g++ | small_width_query_00 |
![]() |
171 ms | 48 MB |
g++ | small_width_query_01 |
![]() |
170 ms | 48 MB |
g++ | small_width_query_02 |
![]() |
176 ms | 48 MB |
g++ | small_width_query_03 |
![]() |
170 ms | 48 MB |
g++ | small_width_query_04 |
![]() |
176 ms | 48 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | max_random_00 |
![]() |
160 ms | 48 MB |
clang++ | max_random_01 |
![]() |
172 ms | 48 MB |
clang++ | max_random_02 |
![]() |
160 ms | 48 MB |
clang++ | max_random_03 |
![]() |
165 ms | 48 MB |
clang++ | max_random_04 |
![]() |
160 ms | 48 MB |
clang++ | random_00 |
![]() |
136 ms | 47 MB |
clang++ | random_01 |
![]() |
149 ms | 48 MB |
clang++ | random_02 |
![]() |
82 ms | 8 MB |
clang++ | random_03 |
![]() |
60 ms | 48 MB |
clang++ | random_04 |
![]() |
65 ms | 47 MB |
clang++ | small_00 |
![]() |
5 ms | 4 MB |
clang++ | small_01 |
![]() |
4 ms | 4 MB |
clang++ | small_02 |
![]() |
4 ms | 4 MB |
clang++ | small_03 |
![]() |
4 ms | 4 MB |
clang++ | small_04 |
![]() |
4 ms | 4 MB |
clang++ | small_05 |
![]() |
4 ms | 4 MB |
clang++ | small_06 |
![]() |
4 ms | 4 MB |
clang++ | small_07 |
![]() |
4 ms | 4 MB |
clang++ | small_08 |
![]() |
4 ms | 4 MB |
clang++ | small_09 |
![]() |
4 ms | 4 MB |
clang++ | small_values_00 |
![]() |
158 ms | 48 MB |
clang++ | small_width_query_00 |
![]() |
196 ms | 48 MB |
clang++ | small_width_query_01 |
![]() |
187 ms | 48 MB |
clang++ | small_width_query_02 |
![]() |
187 ms | 48 MB |
clang++ | small_width_query_03 |
![]() |
182 ms | 48 MB |
clang++ | small_width_query_04 |
![]() |
180 ms | 48 MB |