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

Depends on

Code

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

#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
#include "../../Src/DataStructure/FenwickTree/DualFenwickTree.hpp"
#include "../../Src/Sequence/CompressedSequence.hpp"

/*
 * AtCoder Beginner Contest 389 - F Rated Range
 * https://atcoder.jp/contests/abc389/submissions/63396294
 */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace zawa;
int N, L[200020], R[200020], Q, X[300030];
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 >> L[i] >> R[i];
        R[i]++;
    }
    std::cin >> Q;
    for (int i = 0 ; i < Q ; i++) std::cin >> X[i];
    CompressedSequence<int> comp(X, X + Q);    
    auto init = comp.comped();
    DualFenwickTree<AdditiveGroup<int>> fen{init.begin(), init.end()};
    auto idx = [&](int v) -> int {
        auto it = fen.maxRight(0, [&](int x) -> bool { return x < v; });
        return it ? it.value() : (int)comp.size();    
    };
    for (int i = 0 ; i < N ; i++) {
        int l = idx(L[i]), r = idx(R[i]);
        fen.operation(l, r, 1);
    }
    for (int i = 0 ; i < Q ; i++) {
        std::cout << fen[comp.at(X[i])] << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc389_f.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc389/tasks/abc389_f"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#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/FenwickTree/DualFenwickTree.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/FenwickTree/DualFenwickTree.hpp"

#include <bit>
#include <cassert>
#line 9 "Src/DataStructure/FenwickTree/DualFenwickTree.hpp"
#include <iterator>
#include <optional>
#include <vector>

namespace zawa {

namespace concepts {

template <class F, class V>
concept Predicate = requires {
    { std::declval<F>()(std::declval<V>()) } -> std::same_as<bool>; 
};

} // namespace Concept

template <concepts::Group G>
class DualFenwickTree {
public:

    using V = typename G::Element;

    constexpr static u32 Log2(usize n) noexcept {
        return static_cast<u32>(
                    std::bit_width(n) - (std::has_single_bit(n) ? 1 : 0)
                );
    }

    DualFenwickTree() = default;

    DualFenwickTree(usize n) : n_{n}, lg_{Log2(n)}, dat_(n+1, G::identity()) {
        assert(n);
    }

    DualFenwickTree(const std::vector<V>& d) : n_{d.size()}, lg_{Log2(n_)}, dat_(d.size() + 1, G::identity()) {
        assert(d.size());
        add(0, d[0]);
        for (usize i = 1 ; i < d.size() ; i++) add(i, G::operation(G::inverse(d[i - 1]), d[i]));
    }

    template <std::input_iterator It>
    DualFenwickTree(It first, It last) 
    : n_{static_cast<usize>(std::distance(first, last))}, lg_{Log2(n_)}, dat_(n_ + 1, G::identity()) {
        assert(first != last);
        V pv = static_cast<V>(*first);
        add(0, pv);
        for (usize i = 1 ; i < n_ ; i++) {
            first++;
            V v = static_cast<V>(*first);
            add(i, G::operation(G::inverse(pv), v));
            pv = v;
        } 
    }

    inline usize size() const noexcept {
        return n_;
    }

    void operation(usize l, usize r, const V& v) {
        assert(l <= r and r <= size());
        if (l < r) {
            add(l, v);
            if (r < size()) add(r, G::inverse(v));
        }
    }

    void operation(usize i, const V& v) {
        assert(i < size());
        operation(i, i + 1, v);
    }

    V operator[](i32 i) const {
        assert(0 <= i and i < (i32)size());
        V res = G::identity();
        for (i++ ; i ; i -= lsb(i)) res = G::operation(dat_[i], res);
        return res;
    }

    void set(usize i, V v) {
        assert(0 <= i and i < size());
        v = G::operation(G::inverse((*this)[i]), v);
        operation(i, v);
    }

    template <class F>
    std::optional<usize> maxRight(usize l, F f) const requires concepts::Predicate<F, V> {
        assert(l < size());
        V sum = l ? (*this)[l - 1] : G::identity();
        usize r = 0;
        for (u32 w = lg_ ; w <= lg_ ; w--) {
            usize next = r | (1u << w);
            if (next >= dat_.size()) continue;
            V nsum = G::operation(sum, dat_[next]);
            if (f(nsum)) {
                sum = std::move(nsum);
                r = std::move(next);
            }
        }
        assert(l <= r);
        return r == size() and f(sum) ? std::nullopt : std::optional{r};
    }

    // 実装が合いません。頭が悪いので
    // template <class F>
    // requires Concept::Predicate<F, V>
    // std::optional<usize> minLeft(usize r, F f) const {
    //     assert(r <= n_);
    //     V sum = G::identity();
    //     usize l = 0;
    //     for (u32 w = lg_ ; w <= lg_ ; w--) {
    //         u32 next = l | (1u << w);
    //         if (next >= r) continue;
    //         V nsum = G::operation(dat_[next], sum);
    //         if (!f(nsum)) {
    //             sum = std::move(nsum);
    //             l = std::move(next);
    //         }
    //     }
    //     assert(l <= r);
    //     if (l + 1 == r and !f(sum)) return r;
    //     return l == 0u and f(sum) ? std::nullopt : std::optional{l};
    // }

private:

    usize n_;

    u32 lg_;

    std::vector<V> dat_;

    constexpr i32 lsb(i32 x) const noexcept {
        return x & -x;
    }

    void add(i32 i, const V& v) {
        for (i++ ; i <= (i32)size() ; i += lsb(i)) dat_[i] = G::operation(dat_[i], v);
    }
};

} // namespace zawa
#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 4 "Src/Sequence/CompressedSequence.hpp"

#line 6 "Src/Sequence/CompressedSequence.hpp"
#include <algorithm>
#line 9 "Src/Sequence/CompressedSequence.hpp"
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 7 "Test/AtCoder/abc389_f.test.cpp"

/*
 * AtCoder Beginner Contest 389 - F Rated Range
 * https://atcoder.jp/contests/abc389/submissions/63396294
 */

#line 15 "Test/AtCoder/abc389_f.test.cpp"
#include <iostream>
#line 17 "Test/AtCoder/abc389_f.test.cpp"
using namespace zawa;
int N, L[200020], R[200020], Q, X[300030];
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 >> L[i] >> R[i];
        R[i]++;
    }
    std::cin >> Q;
    for (int i = 0 ; i < Q ; i++) std::cin >> X[i];
    CompressedSequence<int> comp(X, X + Q);    
    auto init = comp.comped();
    DualFenwickTree<AdditiveGroup<int>> fen{init.begin(), init.end()};
    auto idx = [&](int v) -> int {
        auto it = fen.maxRight(0, [&](int x) -> bool { return x < v; });
        return it ? it.value() : (int)comp.size();    
    };
    for (int i = 0 ; i < N ; i++) {
        int l = idx(L[i]), r = idx(R[i]);
        fen.operation(l, r, 1);
    }
    for (int i = 0 ; i < Q ; i++) {
        std::cout << fen[comp.at(X[i])] << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page