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

Depends on

Code

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

/*
 * AtCoder Beginner Contest 440 F - Egoism
 * https://atcoder.jp/contests/abc440/submissions/72451553
 */

#include "../../Src/DataStructure/Heap/PartitionedProducts.hpp"
using namespace zawa;

#include <iostream>
using namespace std;
struct OP {
    using Element = pair<long long, int>;
    static Element identity() {
        return {0, 0};
    }
    static void add(Element& e, const Element& v) {
        e.first += v.first;
        e.second += v.second == -1;
    }
    static void remove(Element& e, const Element& v) {
        e.first -= v.first;
        e.second -= v.second == -1;
    }
};
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), B(N);
    long long sum = 0;
    int cnt = 0;
    for (int i = 0 ; i < N ; i++) {
        cin >> A[i] >> B[i];
        sum += A[i];
        cnt += B[i] == 2;
    }
    auto make = [&](int i) -> pair<int, int> {
        assert(0 <= i and i < N);
        return {A[i], B[i] == 2 ? -1 : i};
    };
    PartitionedProducts<OP, pair<int, int>> que{[&]() {
            vector<pair<int, int>> res(N);
            for (int i = 0 ; i < N ; i++)
                res[i] = make(i);
            return res;
        }()};
    auto eval = [&]() -> long long {
        que.adjustBig(cnt);
        if (cnt == 0)
            return sum;
        auto [a, b] = que.bigProd();
        long long res = sum + a;
        if (b == cnt) {
            res -= que.bigTop().first;
            if (cnt < N)
                res += que.smallTop().first;
        }
        return res;
    };
    while (Q--) {
        int idx, X, Y;
        cin >> idx >> X >> Y;
        idx--;
        que.erase(make(idx));
        sum -= A[idx];
        cnt -= B[idx] == 2;
        A[idx] = X;
        B[idx] = Y;
        sum += A[idx];
        cnt += B[idx] == 2;
        que.insert(make(idx));
        cout << eval() << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc440_f.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc440/tasks/abc440_f"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 440 F - Egoism
 * https://atcoder.jp/contests/abc440/submissions/72451553
 */

#line 2 "Src/DataStructure/Heap/PartitionedProducts.hpp"

#line 2 "Src/DataStructure/Heap/EraseablePriorityQueue.hpp"

#line 2 "Src/DataStructure/Heap/BinaryHeap.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/DataStructure/Heap/BinaryHeap.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>
#include <functional>

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class BinaryHeap {
private:

    Comp m_comp;

    std::vector<T> m_dat;

public:

    inline usize size() const {
        return m_dat.size() - 1;
    }

    inline bool empty() const {
        return m_dat.size() == 1;
    }

    inline const Comp& comp() const {
        return m_comp;
    }

    using const_iterator = typename decltype(m_dat)::const_iterator;

    const_iterator begin() const {
        return m_dat.begin() + 1;
    }

    const_iterator end() const {
        return m_dat.end();
    }

    BinaryHeap(Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    BinaryHeap(It first, It last, Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {
        m_dat.insert(m_dat.end(), first, last);
        build();
    }

    BinaryHeap(std::vector<T>&& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()), m_dat.begin() + 1);
        build();
    }

    BinaryHeap(const std::vector<T>& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(a.begin(), a.end(), m_dat.begin() + 1);
        build();
    }

    const T& top() const {
        assert(size() and "HeapUnderFlow");
        return m_dat[1];
    }

    void push(T&& v) {
        m_dat.push_back(std::move(v));
        upHeap(size());
    }

    void push(const T& v) {
        m_dat.push_back(v);
        upHeap(size());
    }

    void pop() {
        assert(size() and "HeapUnderFlow");
        if (size() > 1)
            std::swap(m_dat[1], m_dat.back());
        m_dat.pop_back();
        if (size() > 1)
            downHeap(1, size());
    }

private:

    void build() {
        const usize n = size();
        for (usize i = (n >> 1) ; i ; i--) 
            downHeap(i, n);
    }

    void upHeap(usize i) {
        while (i >> 1 and m_comp(m_dat[i], m_dat[i >> 1])) {
            std::swap(m_dat[i], m_dat[i >> 1]);
            i >>= 1;
        }
    }

    void downHeap(usize i, usize n) {
        while ((i << 1) <= n) {
            usize j = i << 1;
            if (j + 1 <= n and m_comp(m_dat[j + 1], m_dat[j]))
                j++;
            if (!m_comp(m_dat[j], m_dat[i]))
                break;
            std::swap(m_dat[i], m_dat[j]);
            i = j;
        }
    }
};

} // namespace zawa
#line 4 "Src/DataStructure/Heap/EraseablePriorityQueue.hpp"

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class EraseablePriorityQueue {
private:

    BinaryHeap<T, Comp> m_que, m_rm;

    usize m_cnt = 0;

public:

    inline usize size() const {
        return m_cnt;
    }

    inline bool empty() const {
        return m_cnt == 0;
    }

    EraseablePriorityQueue(Comp comp = {}) 
        : m_que{comp}, m_rm{comp}, m_cnt{0} {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    EraseablePriorityQueue(It first, It last, Comp comp = {})
        : m_que{first, last, comp}, m_rm{comp}, m_cnt{m_que.size()} {}

    EraseablePriorityQueue(std::vector<T> a, Comp comp = {}) 
        : m_que{a, comp}, m_rm{comp}, m_cnt{m_que.size()} {}

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void push(U&& v) {
        m_que.push(std::forward<U>(v));
        m_cnt++;
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void erase(U&& v) {
        assert(size() and "HeapUnderFlow");
        m_rm.push(std::forward<U>(v));
        m_cnt--;
    }

    const T& top() {
        assert(size() and "HeapUnderFlow");
        normalize();
        return m_que.top();
    }

    T pop() {
        assert(size() and "HeapUnderFlow");
        normalize();
        T res = m_que.top();
        m_que.pop();
        m_cnt--;
        return res;
    }

    std::vector<T> container() const {
        BinaryHeap que = m_que, rm = m_rm;  
        std::vector<T> res;
        while (que.size()) {
            if (rm.empty() or que.comp()(que.top(), rm.top())) {
                res.push_back(que.top());
                que.pop();
            }
            else if (que.top() == rm.top())
                que.pop(), rm.pop();
            else
                rm.pop();
        }
        return res;
    }

private:

    void normalize() {
        while (m_rm.size() and m_que.size()) {
            if (m_que.top() == m_rm.top())
                m_que.pop(), m_rm.pop();
            else if (m_que.comp()(m_rm.top(), m_que.top()))
                m_rm.pop();
            else
                break;
        }
    }
};

} // namespace zawa
#line 2 "Src/Algebra/Action/SetOperator.hpp"

#line 4 "Src/Algebra/Action/SetOperator.hpp"

namespace zawa {

namespace concepts {

template <class S, class T>
concept SetOperator = requires {
    typename S::Element;
    { S::identity() } -> std::same_as<typename S::Element>;
    { S::add(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
    { S::remove(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
};

} // namespace concepts

} // namespace zawa
#line 5 "Src/DataStructure/Heap/PartitionedProducts.hpp"

#line 7 "Src/DataStructure/Heap/PartitionedProducts.hpp"

namespace zawa {

namespace internal {

template <class Comp>
struct ReverseComp {

    [[no_unique_address]] Comp comp;

    ReverseComp() = default;

    explicit ReverseComp(Comp c) : comp(std::move(c)) {}

    template <class T, class U>
    bool operator()(T&& a, U&& b) const noexcept(noexcept(std::invoke(comp, std::forward<U>(b), std::forward<T>(a)))) {
        return std::invoke(comp, std::forward<U>(b), std::forward<T>(a));
    }
};

} // namespace internal

template <class S, class T, class Comp = std::less<T>>
requires concepts::SetOperator<S, T> and std::strict_weak_order<Comp, const T&, const T&>
class PartitionedProducts {
public:

    PartitionedProducts(Comp comp = {}) 
        : m_sm{internal::ReverseComp{comp}}, m_bg{comp}, m_comp{comp} {}

    PartitionedProducts(std::vector<T> a, Comp comp = {}) 
        : m_sm{}, m_bg{comp}, m_comp{comp} {
        for (const T& x : a)
            S::add(m_prodS, x);
        m_sm = EraseablePriorityQueue{std::move(a), internal::ReverseComp{comp}};
    }

    inline usize size() const {
        return m_sm.size() + m_bg.size();
    }

    inline usize smallSize() const {
        return m_sm.size();
    }

    inline usize bigSize() const {
        return m_bg.size();
    }

    inline bool empty() const {
        return m_sm.empty() and m_bg.empty();
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void insert(U&& v) {
        if (m_sm.empty())
            addBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            addSmall(std::forward<U>(v));
        else
            addBig(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void erase(U&& v) {
        if (m_sm.empty())
            eraseBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            eraseSmall(std::forward<U>(v));
        else
            eraseBig(std::forward<U>(v));
    }

    bool adjustSmall(usize K) {
        if (size() < K)
            return false;
        adjust(K);
        return true;
    }

    bool adjustBig(usize K) {
        if (size() < K)
            return false;
        adjust(size() - K);
        return true;
    }

    const T& smallTop() {
        assert(smallSize() and "HeapUnderFlow: small");
        return m_sm.top();
    }

    const S::Element& smallProd() const {
        return m_prodS;
    }

    const T& bigTop() {
        assert(bigSize() and "HeapUnderFlow: big");
        return m_bg.top();
    }

    const S::Element& bigProd() const {
        return m_prodB;
    }

    std::pair<std::vector<T>, std::vector<T>> container() const {
        return {m_sm.container(), m_bg.container()};
    }

private:

    EraseablePriorityQueue<T, internal::ReverseComp<Comp>> m_sm;

    EraseablePriorityQueue<T, Comp> m_bg;

    Comp m_comp;

    S::Element m_prodS = S::identity(), m_prodB = S::identity();

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addSmall(U&& v) {
        S::add(m_prodS, v);
        m_sm.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addBig(U&& v) {
        S::add(m_prodB, v);
        m_bg.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseSmall(U&& v) {
        S::remove(m_prodS, v);
        m_sm.erase(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseBig(U&& v) {
        S::remove(m_prodB, v);
        m_bg.erase(std::forward<U>(v));
    }

    void adjust(usize K) {
        while (smallSize() > K) {
            addBig(m_sm.top());
            S::remove(m_prodS, m_sm.top());
            m_sm.pop();
        }
        while (smallSize() < K) {
            addSmall(m_bg.top());
            S::remove(m_prodB, m_bg.top());
            m_bg.pop();
        }
    }
};

} // namespace zawa
#line 10 "Test/AtCoder/abc440_f.test.cpp"
using namespace zawa;

#include <iostream>
using namespace std;
struct OP {
    using Element = pair<long long, int>;
    static Element identity() {
        return {0, 0};
    }
    static void add(Element& e, const Element& v) {
        e.first += v.first;
        e.second += v.second == -1;
    }
    static void remove(Element& e, const Element& v) {
        e.first -= v.first;
        e.second -= v.second == -1;
    }
};
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), B(N);
    long long sum = 0;
    int cnt = 0;
    for (int i = 0 ; i < N ; i++) {
        cin >> A[i] >> B[i];
        sum += A[i];
        cnt += B[i] == 2;
    }
    auto make = [&](int i) -> pair<int, int> {
        assert(0 <= i and i < N);
        return {A[i], B[i] == 2 ? -1 : i};
    };
    PartitionedProducts<OP, pair<int, int>> que{[&]() {
            vector<pair<int, int>> res(N);
            for (int i = 0 ; i < N ; i++)
                res[i] = make(i);
            return res;
        }()};
    auto eval = [&]() -> long long {
        que.adjustBig(cnt);
        if (cnt == 0)
            return sum;
        auto [a, b] = que.bigProd();
        long long res = sum + a;
        if (b == cnt) {
            res -= que.bigTop().first;
            if (cnt < N)
                res += que.smallTop().first;
        }
        return res;
    };
    while (Q--) {
        int idx, X, Y;
        cin >> idx >> X >> Y;
        idx--;
        que.erase(make(idx));
        sum -= A[idx];
        cnt -= B[idx] == 2;
        A[idx] = X;
        B[idx] = Y;
        sum += A[idx];
        cnt += B[idx] == 2;
        que.insert(make(idx));
        cout << eval() << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
Back to top page