cp-library-cpp

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

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/datastructure/util/priority_sum/agc018_c.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/agc018/tasks/agc018_c"

#include <iostream>
#include <vector>

#include "library/datastructure/util/priority_sum.hpp"
#include "library/util/permutation.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x, y, z;
    std::cin >> x >> y >> z;

    const int n = x + y + z;
    std::vector<long long> b(n), c(n), d(n);

    long long sum_a = 0;
    for (int i = 0; i < n; i++) {
        long long a, x, y;
        std::cin >> a >> x >> y;
        b[i] = a - x;
        c[i] = a - y;
        d[i] = x - y;
        sum_a += a;
    }

    auto p = suisen::Permutation::index_sort(b);
    b = p.permute(b);
    c = p.permute(c);
    d = p.permute(d);

    std::vector<long long> sum_t(n);
    suisen::MaximumPrioritySum<long long> topk_t;
    for (int i = n - 1; i >= y - 1; --i) {
        if (i <= y + z - 1) {
            sum_t[i] = topk_t.get_sum();
            topk_t.incr_k();
        }
        topk_t.insert(c[i]);
    }
    std::vector<long long> sum_h(n);
    suisen::MaximumPrioritySum<long long> topk_h;
    long long sum_b = 0;
    for (int i = 0; i <= y + z - 1; ++i) {
        sum_b += b[i];
        topk_h.insert(d[i]);
        if (i >= y - 1) {
            sum_h[i] = topk_h.get_sum() + sum_b;
            topk_h.incr_k();
        }
    }
    long long ans = 0;
    for (int i = y - 1; i < y + z; i++) {
        ans = std::max(ans, sum_a - (sum_h[i] + sum_t[i]));
    }
    std::cout << ans << std::endl;
    return 0;
}
#line 1 "test/src/datastructure/util/priority_sum/agc018_c.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/agc018/tasks/agc018_c"

#include <iostream>
#include <vector>

#line 1 "library/datastructure/util/priority_sum.hpp"



#include <queue>
#include <utility>

namespace suisen {
    namespace internal::priority_sum {
        template <typename T, typename Comparator, typename RevComparator>
        struct PrioritySum {
            using value_type = T;
            using comparator_type = Comparator;
            using reverse_comparator_type = RevComparator;

            PrioritySum() : PrioritySum(0) {}
            PrioritySum(int k) : _k(k), _sum(0), _cmp(), _rev_cmp(), _head_k(_cmp), _del_head_k(_cmp), _tail(_rev_cmp), _del_tail(_rev_cmp) {}

            value_type get_sum() const {
                return _sum;
            }

            void insert(const value_type &v) {
                _sum += v;
                _head_k.push(v);
                fix();
            }

            void erase(const value_type &v) {
                if (_head_k.size() and v == _head_k.top()) {
                    _sum -= v;
                    _head_k.pop();
                } else if (_head_k.size() and _rev_cmp(v, _head_k.top())) {
                    _sum -= v;
                    _del_head_k.push(v);
                } else {
                    _del_tail.push(v);
                }
                fix();
            }

            int get_k() const { return _k; }

            void set_k(int new_k) { _k = new_k, fix(); }
            void incr_k() { set_k(get_k() + 1); }
            void decr_k() { set_k(get_k() - 1); }

            int size() const {
                return int((_head_k.size() + _tail.size()) - (_del_head_k.size() + _del_tail.size()));
            }

        private:
            int _k;
            value_type _sum;
            comparator_type _cmp;
            reverse_comparator_type _rev_cmp;
            std::priority_queue<value_type, std::vector<value_type>, comparator_type> _head_k, _del_head_k;
            std::priority_queue<value_type, std::vector<value_type>, reverse_comparator_type> _tail, _del_tail;

            void fix() {
                while (int(_head_k.size() - _del_head_k.size()) < _k and _tail.size()) {
                    value_type v = std::move(_tail.top());
                    _tail.pop();
                    if (_del_tail.size() and _del_tail.top() == v) {
                        _del_tail.pop();
                    } else {
                        _sum += v;
                        _head_k.push(std::move(v));
                    }
                }
                while (int(_head_k.size() - _del_head_k.size()) > _k) {
                    value_type v = std::move(_head_k.top());
                    _head_k.pop();
                    if (_del_head_k.size() and _del_head_k.top() == v) {
                        _del_head_k.pop();
                    } else {
                        _sum -= v;
                        _tail.push(std::move(v));
                    }
                }
            }
        };
    } // internal::priority_sum

    template <typename T>
    using MaximumPrioritySum = internal::priority_sum::PrioritySum<T, std::less<T>, std::greater<T>>;
    template <typename T>
    using MinimumPrioritySum = internal::priority_sum::PrioritySum<T, std::greater<T>, std::less<T>>;
} // namespace suisen



#line 1 "library/util/permutation.hpp"



#include <algorithm>
#include <cassert>
#include <numeric>
#line 8 "library/util/permutation.hpp"

namespace suisen {
    struct Permutation : public std::vector<int> {
        using base_type = std::vector<int>;
        using base_type::base_type;

        Permutation() : Permutation(0) {}
        Permutation(std::size_t n) : Permutation(int(n)) {}
        Permutation(int n) : base_type(n) {
            std::iota(begin(), end(), 0);
        }
        Permutation(const std::vector<int>& a) : std::vector<int>(a) {}
        Permutation(std::vector<int>&& a) : std::vector<int>(std::move(a)) {}

        // returns b s.t. b[i] = a[p[i]]
        template <typename T>
        std::vector<T> permute(const std::vector<T>& a) const {
            const int n = a.size();
            std::vector<T> res(n);
            for (int i = 0; i < n; ++i) res[i] = a[(*this)[i]];
            return res;
        }
        // returns b s.t. b[p[i]] = a[i]
        template <typename T>
        std::vector<T> inv_permute(const std::vector<T>& a) const {
            const int n = a.size();
            std::vector<T> res(n);
            for (int i = 0; i < n; ++i) res[(*this)[i]] = a[i];
            return res;
        }

        // returns p * q s.t. (p * q)[i] = p[q[i]]
        friend Permutation operator*(const Permutation& p, const Permutation& q) {
            return q.permute(p);
        }
        Permutation& operator*=(const Permutation& q) {
            return *this = *this * q;
        }
        Permutation inv() const {
            const int n = size();
            Permutation res(n);
            for (int i = 0; i < n; ++i) res[(*this)[i]] = i;
            return res;
        }
        Permutation pow(long long k) const {
            assert(k >= 0);
            const int n = size();
            std::vector<int8_t> seen(n, false);
            Permutation res(n);
            for (int s = 0; s < n; ++s) {
                if (seen[s]) continue;
                std::vector<int> cycle { s };
                for (int v = (*this)[s]; v != s; v = (*this)[v]) cycle.push_back(v);
                const int l = cycle.size();
                for (int j = 0; j < l; ++j) {
                    int v = cycle[j];
                    seen[v] = true;
                    res[v] = cycle[(j + k) % l];
                }
            }
            return res;
        }

        template <typename T, typename Comp = std::less<T>>
        static Permutation index_sort(const std::vector<T>& a, Comp comp = Comp{}) {
            Permutation p(a.size());
            std::sort(p.begin(), p.end(), [&](int i, int j) { return comp(a[i], a[j]); });
            return p;
        }
    };

    template <typename hash_t>
    struct PermutationHash {
        hash_t operator()(const Permutation &p) const {
            return hash(p);
        }
        /**
         * minimal perfect hash function for permutations.
         * complexity: O(n) time, O(n) extra space
         * reference: https://twitter.com/noshi91/status/1452081886025555972?s=20
         */
        static hash_t hash(const Permutation &per) {
            hash_t h = 0;
            const int n = per.size();
            Permutation p = per;
            Permutation q = per.inv();
            for (int i = n - 1; i >= 0; --i) {
                h = h * (i + 1) + p[i];
                p[q[i]] = p[i];
                q[p[i]] = q[i];
            }
            return h;
        }
        static Permutation unhash(int n, hash_t h) {
            Permutation p = Permutation(n), q = p;
            for (int i = 0; i < n; ++i) {
                p[i] = h % (i + 1), q[i] = q[p[i]];
                q[p[i]] = p[q[i]] = i;
                h /= i + 1;
            }
            return p;
        }
    };
} // namespace suisen


#line 8 "test/src/datastructure/util/priority_sum/agc018_c.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x, y, z;
    std::cin >> x >> y >> z;

    const int n = x + y + z;
    std::vector<long long> b(n), c(n), d(n);

    long long sum_a = 0;
    for (int i = 0; i < n; i++) {
        long long a, x, y;
        std::cin >> a >> x >> y;
        b[i] = a - x;
        c[i] = a - y;
        d[i] = x - y;
        sum_a += a;
    }

    auto p = suisen::Permutation::index_sort(b);
    b = p.permute(b);
    c = p.permute(c);
    d = p.permute(d);

    std::vector<long long> sum_t(n);
    suisen::MaximumPrioritySum<long long> topk_t;
    for (int i = n - 1; i >= y - 1; --i) {
        if (i <= y + z - 1) {
            sum_t[i] = topk_t.get_sum();
            topk_t.incr_k();
        }
        topk_t.insert(c[i]);
    }
    std::vector<long long> sum_h(n);
    suisen::MaximumPrioritySum<long long> topk_h;
    long long sum_b = 0;
    for (int i = 0; i <= y + z - 1; ++i) {
        sum_b += b[i];
        topk_h.insert(d[i]);
        if (i >= y - 1) {
            sum_h[i] = topk_h.get_sum() + sum_b;
            topk_h.incr_k();
        }
    }
    long long ans = 0;
    for (int i = y - 1; i < y + z; i++) {
        ans = std::max(ans, sum_a - (sum_h[i] + sum_t[i]));
    }
    std::cout << ans << std::endl;
    return 0;
}
Back to top page