cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/CF/EC162-D.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"
#include "../../Src/Algebra/Monoid/SameMonoid.hpp"
#include "../../Src/DataStructure/SparseTable/SparseTable.hpp"
#include "../../Src/Utility/BinarySearch.hpp"

using namespace zawa;
using M = SameMonoid<long long>;
using D = M::Element;

#include <algorithm>
#include <iostream>

/*
 * Educational Codeforces Round 162 - D. Slimes
 * https://codeforces.com/contest/1923/submission/248125965
 */

void solve() {
    int testcase; std::cin >> testcase;
    while (testcase--) {
        int n; std::cin >> n;
        std::vector<long long> a(n);
        for (auto& x : a) std::cin >> x;
        const int INF{(int)1e9};
        std::vector<int> ans(n, INF);
        for (int t{} ; t < 2 ; t++) {
            Ruisekiwa<long long> s{a};
            std::vector<D> in(n);
            for (int i{} ; i < n ; i++) in[i] = D{a[i]};
            SparseTable<M> spt{in};
            for (int i{1} ; i < n ; i++) {
                if (a[i - 1] > a[i]) {
                    ans[i] = 1;
                    continue;
                }
                auto f{[&](int v) -> bool {
                    return s.product(v, i) > a[i];
                }};
                auto g{[&](int v) -> bool {
                    return !spt.product(v, i).same();
                }};
                int L1{-INF}, L2{-INF};
                if (f(0)) L1 = BinarySearch(0, i, f);
                if (g(0)) L2 = BinarySearch(0, i, g);
                ans[i] = std::min(ans[i], i - std::min(L1, L2));
            }
            if (t == 0) {
                std::reverse(a.begin(), a.end());
                std::reverse(ans.begin(), ans.end());
            }
        }
        for (int i{n - 1} ; i >= 0 ; i--) {
            std::cout << (ans[i] == INF ? -1 : ans[i]) << (i == 0 ? '\n' : ' ');
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    SetFastIO();
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/CF/EC162-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

#line 2 "Src/Algebra/Group/AdditiveGroup.hpp"

namespace zawa {

template <class T>
class AdditiveGroup {
public:
    using Element = T;
    static constexpr T identity() noexcept {
        return T{};
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        return l + r;
    }
    static constexpr T inverse(const T& v) noexcept {
        return -v;
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#line 4 "Src/DataStructure/PrefixSum1D/PrefixSum1D.hpp"

#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <type_traits>
#include <functional>

namespace zawa {

template <class Group>
class PrefixSum1D {
private:
    using T = typename Group::Element;
    std::vector<T> dat_;

    constexpr bool rangeCheck(u32 l, u32 r) const {
        return (l <= r and r < dat_.size());
    }

public:
    PrefixSum1D() = default; 
    PrefixSum1D(const std::vector<T>& A) : dat_(A.size() + 1, Group::identity()) {
        dat_.shrink_to_fit();
        for (u32 i = 0 ; i < A.size() ; i++) {
            dat_[i + 1] = Group::operation(dat_[i], A[i]);
        }
    }

    inline T operator[](u32 i) const {
        assert(i < dat_.size());
        return dat_[i];
    }

    inline usize size() const {
        return dat_.size();
    }

    T product(u32 l, u32 r) const {
        assert(rangeCheck(l, r));
        return Group::operation(Group::inverse(dat_[l]), dat_[r]);
    }

    u32 lowerBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::lower_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    u32 upperBound(u32 l, u32 r, const T& v) const {
        assert(rangeCheck(l, r));
        T value = Group::operation(v, dat_[l]);
        return std::upper_bound(dat_.begin() + l, dat_.begin() + r, value) - dat_.begin();
    }

    template <class F>
    u32 maxRight(u32 l, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(l < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(v, Group::inverse(dat_[l])));
        };
        return std::partition_point(dat_.begin() + l, dat_.end(), f_) - dat_.begin();
    }

    template <class F>
    u32 minLeft(u32 r, const F& f) const {
        static_assert(std::is_convertible_v<decltype(f), std::function<bool(T)>>, "f must be function bool(T)");
        assert(r < dat_.size());
        assert(f(Group::identity()));
        auto f_ = [&](const T& v) -> bool {
            return f(Group::operation(Group::inverse(v), dat_[r]));
        };
        return dat_.rend() - std::partition_point(dat_.rbegin() + (dat_.size() - r - 1), dat_.rend(), f_) - 1;
    }

    const auto begin() const {
        return dat_.begin();
    }

    const auto end() const {
        return dat_.end();
    }
};

} // namespace zawa
#line 5 "Src/DataStructure/PrefixSum1D/StaticRangeSumSolver.hpp"

namespace zawa {

    template <class T>
    using StaticRangeSumSolver = PrefixSum1D<AdditiveGroup<T>>;

    template <class T>
    using Ruisekiwa = PrefixSum1D<AdditiveGroup<T>>;

};
#line 2 "Src/Algebra/Monoid/SameMonoid.hpp"

#include <optional>

namespace zawa {

template <class T>
class SameMonoidData {
private:
    std::optional<T> element_{};
    bool same_{true};
public:

    static std::optional<T> merge(const std::optional<T>& l, const std::optional<T>& r) noexcept {
        if (l and r) return (l.value() == r.value() ? l : std::nullopt);
        if (l) return l;
        if (r) return r;
        return std::nullopt;
    }

    SameMonoidData() = default;
    SameMonoidData(const T& element) 
        : element_{element}, same_{true} {}
    SameMonoidData(const std::optional<T>& element, bool same)
        : element_{element}, same_{same} {}

    bool empty() const noexcept {
        return same_ and !element_.has_value();
    }
    bool same() const noexcept {
        return same_;
    }
    std::optional<T> element() const noexcept {
        return element_;
    }
    T value() const noexcept {
        return element_.value();
    }
};

template <class T>
struct SameMonoid {
public:
    using Element = SameMonoidData<T>;
    static Element identity() noexcept {
        return Element{}; 
    }
    static Element operation(const Element& l, const Element& r) {
        if (l.empty() and r.empty()) return identity();
        if (l.empty()) return r;
        if (r.empty()) return l;
        std::optional<T> element{Element::merge(l.element(), r.element())};
        return Element{element, l.same() and r.same() and element.has_value()};
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/SparseTable/SparseTable.hpp"

#line 4 "Src/DataStructure/SparseTable/SparseTable.hpp"

#line 7 "Src/DataStructure/SparseTable/SparseTable.hpp"
#include <ostream>

namespace zawa {

template <class Structure>
class SparseTable {
private:
    using Value = typename Structure::Element;
    std::vector<u32> L;
    std::vector<std::vector<Value>> dat;
public:

    SparseTable() : L{}, dat{} {}
    SparseTable(const std::vector<Value>& a) : L(a.size() + 1), dat{} {
        for (u32 i{1} ; i < L.size() ; i++) {
            L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
        }
        dat.resize(L.back() + 1);
        dat[0] = a;
        for (u32 i{1}, len{2} ; i < dat.size() ; i++, len <<= 1) {
            dat[i] = dat[i - 1];
            for (u32 j{} ; j + len - 1 < dat[i].size() ; j++) {
                dat[i][j] = Structure::operation(dat[i - 1][j], dat[i - 1][j + (len >> 1)]);
            }
        }
    }

    Value product(u32 l, u32 r) const {
        assert(l <= r);
        assert(l < dat[0].size());
        assert(r <= dat[0].size());
        u32 now{L[r - l]};
        return Structure::operation(dat[now][l], dat[now][r - (1 << now)]);
    }

    friend std::ostream& operator<<(std::ostream& os, const SparseTable<Structure>& spt) {
        for (u32 i{}, len{1} ; i < spt.dat.size() ; i++, len <<= 1) {
            os << "length = " << len << '\n';
            for (u32 j{} ; j + len - 1 < spt.dat[i].size() ; j++) {
                os << spt.dat[i][j] << (j + len == spt.dat[i].size() ? '\n' : ' ');
            }
        }
        return os;
    }
};

} // namespace zawa
#line 2 "Src/Utility/BinarySearch.hpp"

#line 4 "Src/Utility/BinarySearch.hpp"

#line 8 "Src/Utility/BinarySearch.hpp"
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
#line 8 "Test/CF/EC162-D.test.cpp"

using namespace zawa;
using M = SameMonoid<long long>;
using D = M::Element;

#line 15 "Test/CF/EC162-D.test.cpp"

/*
 * Educational Codeforces Round 162 - D. Slimes
 * https://codeforces.com/contest/1923/submission/248125965
 */

void solve() {
    int testcase; std::cin >> testcase;
    while (testcase--) {
        int n; std::cin >> n;
        std::vector<long long> a(n);
        for (auto& x : a) std::cin >> x;
        const int INF{(int)1e9};
        std::vector<int> ans(n, INF);
        for (int t{} ; t < 2 ; t++) {
            Ruisekiwa<long long> s{a};
            std::vector<D> in(n);
            for (int i{} ; i < n ; i++) in[i] = D{a[i]};
            SparseTable<M> spt{in};
            for (int i{1} ; i < n ; i++) {
                if (a[i - 1] > a[i]) {
                    ans[i] = 1;
                    continue;
                }
                auto f{[&](int v) -> bool {
                    return s.product(v, i) > a[i];
                }};
                auto g{[&](int v) -> bool {
                    return !spt.product(v, i).same();
                }};
                int L1{-INF}, L2{-INF};
                if (f(0)) L1 = BinarySearch(0, i, f);
                if (g(0)) L2 = BinarySearch(0, i, g);
                ans[i] = std::min(ans[i], i - std::min(L1, L2));
            }
            if (t == 0) {
                std::reverse(a.begin(), a.end());
                std::reverse(ans.begin(), ans.end());
            }
        }
        for (int i{n - 1} ; i >= 0 ; i--) {
            std::cout << (ans[i] == INF ? -1 : ans[i]) << (i == 0 ? '\n' : ' ');
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    SetFastIO();
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page