sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D" #include <bits/stdc++.h> #include "../../data-structure/sparse_table.hpp" using namespace std; struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return min(a, b); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, L; cin >> N >> L; vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i]; SparseTable<MinMonoid> st(a); for (int i = 0; i < N - L + 1; i++) { cout << st.fold(i, i + L); if (i < N - L) cout << " "; else cout << "\n"; } }
#line 1 "test/aoj/DSL_3_D.sparse_table.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D" #include <bits/stdc++.h> #line 3 "data-structure/sparse_table.hpp" #include <bit> #line 5 "data-structure/sparse_table.hpp" template <typename M> class SparseTable { using T = M::T; public: SparseTable() = default; explicit SparseTable(const std::vector<T>& v) { const int n = v.size(); const int b = std::bit_width((unsigned int)n); lookup.resize(b, std::vector<T>(n)); std::ranges::copy(v, lookup[0].begin()); for (int i = 1; i < b; ++i) { for (int j = 0; j + (1 << i) <= n; ++j) { lookup[i][j] = M::op(lookup[i - 1][j], lookup[i - 1][j + (1 << (i - 1))]); } } } T fold(int l, int r) const { if (l == r) return M::id(); int i = std::bit_width((unsigned int)(r - l)) - 1; return M::op(lookup[i][l], lookup[i][r - (1 << i)]); } private: std::vector<std::vector<T>> lookup; }; #line 7 "test/aoj/DSL_3_D.sparse_table.test.cpp" using namespace std; struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return min(a, b); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N, L; cin >> N >> L; vector<int> a(N); for (int i = 0; i < N; i++) cin >> a[i]; SparseTable<MinMonoid> st(a); for (int i = 0; i < N - L + 1; i++) { cout << st.fold(i, i + L); if (i < N - L) cout << " "; else cout << "\n"; } }