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

Depends on

Code

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

/*
 * AtCoder Regular Contest 197 (Div. 2) C - Removal of Multiples
 * https://atcoder.jp/contests/arc197/submissions/74416251
 */

#include "../../Src/DataStructure/Bucket/BucketRangeProduct.hpp"
#include "../../Src/Algebra/Group/AdditiveGroup.hpp"
using namespace zawa;

#include <iostream>
using namespace std;

int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int Q;
    cin >> Q;
    const int MAX = 3000000;
    vector<bool> del(MAX);
    const int B = 2500;
    BucketRangeQuery<AdditiveGroup<int>> buc(vector<int>(MAX,1),B);
    while (Q--) {
        int A,B;
        cin >> A >> B;
        if (A < MAX and !del[A]) {
            for (int i = 1 ; i * A < MAX ; i++)
                if (!del[A*i]) {
                    del[A*i] = 1;
                    buc.operation(A*i,-1);
                }
        }
        cout << buc.maxRight(1,[&](int v) { return v < B; }) << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/arc197_c.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/arc197/tasks/arc197_c"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Regular Contest 197 (Div. 2) C - Removal of Multiples
 * https://atcoder.jp/contests/arc197/submissions/74416251
 */

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

#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <vector>

namespace zawa {

template <concepts::Monoid M>
class BucketRangeQuery {
public:

    using V = typename M::Element;

    inline usize size() const {
        return m_n;
    }

    inline usize bucketSize() const {
        return m_b;
    }

    BucketRangeQuery() = default;

    BucketRangeQuery(usize N,usize B = std::numeric_limits<usize>::max()) 
        : m_n{N},m_b{BucketSize(N,B)}, m_data(N,M::identity()), m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    BucketRangeQuery(std::vector<V> A,usize B = std::numeric_limits<usize>::max())
        : m_n{A.size()},m_b{BucketSize(A.size(),B)},m_data(std::move(A)),m_bucket((m_n+m_b-1)/m_b,M::identity()) {
        for (usize i = 0 ; i < size() ; i++)
            m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],m_data[i]);
    }

    V product(usize l,usize r) const {
        assert(l <= r and r <= size());
        V res = M::identity();
        while (l < r and l % bucketSize())
            res = M::operation(res,m_data[l++]);
        while (l + bucketSize() <= r) {
            res = M::operation(res,m_bucket[l/bucketSize()]);
            l += bucketSize();
        }
        while (l < r)
            res = M::operation(res,m_data[l++]);
        return res;
    }

    V operator[](usize i) const {
        assert(i < size());
        return m_data[i];
    }

    V bucketValue(usize i) const {
        assert(i < m_bucket.size());
        return m_bucket[i];
    }

    void assign(usize i,V x) {
        assert(i < size());
        const usize idx = i/bucketSize();
        if constexpr (concepts::Group<M>) {
            m_bucket[idx] = M::operation(m_bucket[idx],M::inverse(m_data[i]));
            m_data[i] = std::move(x);
            m_bucket[idx] = M::operation(m_bucket[idx],m_data[i]);
        }
        else {
            m_data[i] = std::move(x);
            m_bucket[idx] = M::identity();
            const usize l = idx*bucketSize(),r = std::min(size(),(idx+1)*bucketSize());
            for (usize j = l ; j < r ; j++)
                m_bucket[idx] = M::operation(m_bucket[idx],m_data[j]);
        }
    }

    void operation(usize i,V x) {
        assert(i < size());
        m_bucket[i/bucketSize()] = M::operation(m_bucket[i/bucketSize()],x);
        m_data[i] = M::operation(m_data[i],x);
    }

    template <class F>
    requires std::predicate<F,V>
    usize maxRight(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i < size() and i % bucketSize()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i++;
        }
        while (i + bucketSize() <= size()) {
            V nxt = M::operation(pd,m_bucket[i/bucketSize()]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i += bucketSize();
        }
        while (i < size()) {
            V nxt = M::operation(pd,m_data[i]);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i++;
        }
        return i;
    }

    template <class F>
    requires std::predicate<F,V>
    usize minLeft(usize i,F f) const {
        assert(i <= size());
        assert(f(M::identity()));
        V pd = M::identity();
        while (i % bucketSize()) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                return i;
            pd = std::move(nxt);
            i--;
        }
        while (i) {
            V nxt = M::operation(m_bucket[i/bucketSize()-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i -= bucketSize();
        }
        while (i) {
            V nxt = M::operation(m_data[i-1],pd);
            if (!f(nxt))
                break;
            pd = std::move(nxt);
            i--;
        }
        return i;
    }

private:

    usize m_n,m_b;

    std::vector<V> m_data,m_bucket;

    static usize BucketSize(usize N,usize B) {
        return B == std::numeric_limits<usize>::max() ? std::max<usize>(1,sqrtl(N)) : B;
    }
};


} // 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/arc197_c.test.cpp"
using namespace zawa;

#include <iostream>
using namespace std;

int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int Q;
    cin >> Q;
    const int MAX = 3000000;
    vector<bool> del(MAX);
    const int B = 2500;
    BucketRangeQuery<AdditiveGroup<int>> buc(vector<int>(MAX,1),B);
    while (Q--) {
        int A,B;
        cin >> A >> B;
        if (A < MAX and !del[A]) {
            for (int i = 1 ; i * A < MAX ; i++)
                if (!del[A*i]) {
                    del[A*i] = 1;
                    buc.operation(A*i,-1);
                }
        }
        cout << buc.maxRight(1,[&](int v) { return v < B; }) << '\n';
    }
#else
    cout << "Hello World\n";
#endif
}
Back to top page