algorithm/monotone_minima.cpp

• View this file on GitHub
• Last update: 2021-12-28 21:38:32+09:00

Depends on

• utility/rep.cpp

Code

#pragma once
#include <queue>
#include <tuple>
#include <vector>
#include "../utility/rep.cpp"

template <class Select> std::vector<int> monotone_minima(const int row, const int column, const Select& select) {
    std::vector<int> ret(row);
    std::queue<std::tuple<int, int, int, int>> que;
    que.emplace(0, row, 0, column);
    while (!que.empty()) {
        const auto [l, r, d, u] = que.front();
        que.pop();
        const int m = (l + r) / 2;
        ret[m] = d;
        for (const int i : rep(d + 1, u))
            if (select(m, ret[m], i)) ret[m] = i;
        if (l != m) que.emplace(l, m, d, ret[m] + 1);
        if (m + 1 != r) que.emplace(m + 1, r, ret[m], u);
    }
    return ret;
}

#line 2 "algorithm/monotone_minima.cpp"
#include <queue>
#include <tuple>
#include <vector>
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 6 "algorithm/monotone_minima.cpp"

template <class Select> std::vector<int> monotone_minima(const int row, const int column, const Select& select) {
    std::vector<int> ret(row);
    std::queue<std::tuple<int, int, int, int>> que;
    que.emplace(0, row, 0, column);
    while (!que.empty()) {
        const auto [l, r, d, u] = que.front();
        que.pop();
        const int m = (l + r) / 2;
        ret[m] = d;
        for (const int i : rep(d + 1, u))
            if (select(m, ret[m], i)) ret[m] = i;
        if (l != m) que.emplace(l, m, d, ret[m] + 1);
        if (m + 1 != r) que.emplace(m + 1, r, ret[m], u);
    }
    return ret;
}

Back to top page