test/aoj/DSL_3_D.sparse_table.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

• Sparse Table (data-structure/sparse_table.hpp)

Code

#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";
    }
}

Back to top page