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/AtCoder/arc196_a.test.cpp

Depends on

Code

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

/*
 * AtCoder Regular Contest 196 (Div. 1) A - Adjacent Delete
 * https://atcoder.jp/contests/arc196/submissions/64618439
 */

#include "../../Src/DataStructure/Other/PriorityProductSet.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"

#include <algorithm>
#include <iostream>
#include <vector>
using namespace zawa;
int N, A[300030];
long long solve() {
    std::vector<long long> pref(N + 1);
    {
        PriorityProductSet<AdditiveGroup<long long>> set;
        for (int i = 0 ; i < N ; i += 2) {
            set.setK(i/2);
            pref[i] = set.productRemain().value() - set.product().value();
            set.insert(A[i]);
            if (i + 1 < N) set.insert(A[i + 1]);
        }
        if (N % 2 == 0) {
            set.setK(N/2);
            pref[N] = set.productRemain().value() - set.product().value();
            return pref[N];
        }
    }
    std::vector<long long> suf(N + 1);
    {
        PriorityProductSet<AdditiveGroup<long long>> set;
        for (int i = N ; i >= 0 ; i -= 2) {
            set.setK((N-i)/2);
            suf[i] = set.productRemain().value() - set.product().value();
            if (i - 1 >= 0) set.insert(A[i - 1]);
            if (i - 2 >= 0) set.insert(A[i - 2]);
        }
    }
    // for (auto p : pref) std::cout << p << ' ';
    // std::cout << std::endl;
    // for (auto p : suf) std::cout << p << ' ';
    // std::cout << std::endl;
    long long ans = 0;
    for (int i = 0 ; i < N ; i += 2) {
        ans = std::max(ans, pref[i] + suf[i + 1]);
    }
    return ans;
}
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/arc196_a.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://atcoder.jp/contests/arc196/tasks/arc196_a"

/*
 * AtCoder Regular Contest 196 (Div. 1) A - Adjacent Delete
 * https://atcoder.jp/contests/arc196/submissions/64618439
 */

#line 2 "Src/DataStructure/Other/PriorityProductSet.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 2 "Src/Algebra/Group/GroupConcept.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 4 "Src/Algebra/Group/GroupConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Inversible = requires {
    typename T::Element;
    { T::inverse(std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

template <class T>
concept Group = Monoid<T> and Inversible<T>;

} // namespace Concept

} // namespace zawa
#line 5 "Src/DataStructure/Other/PriorityProductSet.hpp"

#include <cassert>
#include <optional>
#include <utility>
#include <queue>

namespace zawa {

// 1-indexed
template <concepts::Group G>
class PriorityProductSet {
public:

    using V = G::Element;

    PriorityProductSet() = default;

    PriorityProductSet(usize K) : m_K{K} {}

    void insert(V&& v) {
        pushSmall(std::move(v));
        adjust();
    }

    void insert(const V& v) {
        insert(V{v});
    }

    usize size() const {
        return m_small.size() + m_big.size();
    }

    inline usize K() const {
        return m_K;
    }

    void setK(usize K) {
        m_K = K;
        adjust();
    }

    std::optional<V> product() const {
        return m_small.size() == m_K ? std::optional<V>{m_sv} : std::nullopt;
    }

    std::optional<V> productRemain() const {
        return m_small.size() == m_K ? std::optional<V>{m_bv} : std::nullopt;
    }

    V productAll() const {
        return G::operation(m_sv, m_bv);
    }

    V popK() {
        assert(m_K >= 1u and size() >= m_K);
        V res = popSmall(); 
        adjust();
        return res;
    }

private:

    std::priority_queue<V> m_small;

    std::priority_queue<V, std::vector<V>, std::greater<V>> m_big;

    V m_sv = G::identity(), m_bv = G::identity();

    usize m_K = 0;

    void pushSmall(V&& v) {
        m_sv = G::operation(m_sv, v);
        m_small.push(std::move(v));
    }

    V popSmall() {
        assert(m_small.size());
        V res = m_small.top();
        m_small.pop();
        m_sv = G::operation(m_sv, G::inverse(res));
        return res;
    }

    void pushBig(V&& v) {
        m_bv = G::operation(m_bv, v);
        m_big.push(std::move(v));
    }

    V popBig() {
        assert(m_big.size());
        V res = m_big.top();
        m_big.pop();
        m_bv = G::operation(m_bv, G::inverse(res));
        return res;
    }

    void adjust() {
        while (m_small.size() > m_K) pushBig(popSmall());
        while (m_small.size() < m_K and m_big.size()) pushSmall(popBig());
    }
};

} // namespace zawa
#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 11 "Test/AtCoder/arc196_a.test.cpp"

#include <algorithm>
#include <iostream>
#include <vector>
using namespace zawa;
int N, A[300030];
long long solve() {
    std::vector<long long> pref(N + 1);
    {
        PriorityProductSet<AdditiveGroup<long long>> set;
        for (int i = 0 ; i < N ; i += 2) {
            set.setK(i/2);
            pref[i] = set.productRemain().value() - set.product().value();
            set.insert(A[i]);
            if (i + 1 < N) set.insert(A[i + 1]);
        }
        if (N % 2 == 0) {
            set.setK(N/2);
            pref[N] = set.productRemain().value() - set.product().value();
            return pref[N];
        }
    }
    std::vector<long long> suf(N + 1);
    {
        PriorityProductSet<AdditiveGroup<long long>> set;
        for (int i = N ; i >= 0 ; i -= 2) {
            set.setK((N-i)/2);
            suf[i] = set.productRemain().value() - set.product().value();
            if (i - 1 >= 0) set.insert(A[i - 1]);
            if (i - 2 >= 0) set.insert(A[i - 2]);
        }
    }
    // for (auto p : pref) std::cout << p << ' ';
    // std::cout << std::endl;
    // for (auto p : suf) std::cout << p << ' ';
    // std::cout << std::endl;
    long long ans = 0;
    for (int i = 0 ; i < N ; i += 2) {
        ans = std::max(ans, pref[i] + suf[i + 1]);
    }
    return ans;
}
int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    std::cout << solve() << '\n';
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page