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

Depends on

Code

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

/*
 * AtCoder Beginner Contest 223 H - Xor Query
 * https://atcoder.jp/contests/abc223/submissions/68663949
 */

#include "../../Src/Sequence/OfflineRangeProduct.hpp"

#include <iostream>
#include <array>
#include <bit>
#include <vector>
using namespace zawa;
using namespace std;
struct M {
    using Element = array<unsigned long long, 60>;
    static unsigned long long reduce(const Element& B, unsigned long long v) {
        for (int i = 59 ; i >= 0 and v ; i--)
            if (v & (1ull << i))
                v ^= B[i];
        return v;
    }
    static bool insert(Element& B, unsigned long long v) {
        v = reduce(B, v);
        if (v) {
            B[bit_width(v) - 1] = v;
            return true;
        }
        return false;
    }
    static Element identity() {
        Element res;
        res.fill(0);
        return res;
    }
    static Element operation(Element l, Element r) {
        for (unsigned long long v : r)
            if (v)
                insert(l, v);
        return l;
    }
    static Element acted(Element l, unsigned long long v) {
        insert(l, v);
        return l;
    }
};
struct query {
    int l, r;
};
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<unsigned long long> A(N), X(Q);
    for (int i = 0 ; i < N ; i++)
       cin >> A[i];
    vector<query> lr(Q);
    for (int i = 0 ; i < Q ; i++) {
        int l, r;
        cin >> l >> r >> X[i];
        l--;
        lr[i] = {l, r};
    }
    auto ans = OfflineRangeProduct<M>(A, lr);
    for (int i = 0 ; i < Q ; i++)
        cout << (M::reduce(ans[i], X[i]) == 0 ? "Yes\n" : "No\n");
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc223_h.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc223/tasks/abc223_h"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 223 H - Xor Query
 * https://atcoder.jp/contests/abc223/submissions/68663949
 */

#line 2 "Src/Sequence/OfflineRangeProduct.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/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 2 "Src/Algebra/Action/ActionConcept.hpp"

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

namespace zawa {

namespace concepts {

template <class G, class X>
concept Action = requires {
    typename G::Element;
    { G::action(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<X>;
};

// Is appropriate name X-set?
template <class G, class X>
concept Acted = requires {
    typename G::Element;
    { G::acted(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<typename G::Element>;
};

} // namespace concepts

} // namespace zawa
#line 6 "Src/Sequence/OfflineRangeProduct.hpp"

#include <algorithm>
#include <cassert>
#line 10 "Src/Sequence/OfflineRangeProduct.hpp"
#include <numeric>
#include <vector>

namespace zawa {

namespace offline_range_product_internal {

template <class R>
concept Range = requires (R lr) {
    { lr.l } -> std::convertible_to<usize>;
    { lr.r } -> std::convertible_to<usize>;
};

template <class M, class S, class R>
concept condition = concepts::Monoid<M> and Range<R> and (std::same_as<typename M::Element, S> or concepts::Acted<M, S>);

} // namespace offline_range_product_internal

template <class M, class S, class Range>
requires offline_range_product_internal::condition<M, S, Range>
std::vector<typename M::Element> OfflineRangeProduct(const std::vector<S>& as, const std::vector<Range>& qs) {
    std::vector<typename M::Element> sum(as.size() + 1), res(qs.size(), M::identity());
    auto f = [&](usize m, const std::vector<usize>& idx) -> void {
        sum[m] = M::identity();
        usize L = m, R = m;
        for (usize i : idx) {
            L = std::min<usize>(L, qs[i].l);
            R = std::max<usize>(R, qs[i].r);
        }
        for (usize i = m ; i-- > L ; ) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i] = M::operation(as[i], sum[i + 1]);
            else
                sum[i] = M::acted(sum[i + 1], as[i]);
        }
        for (usize i = m ; i < R ; i++) {
            if constexpr (std::same_as<typename M::Element, S>)
                sum[i + 1] = M::operation(sum[i], as[i]);
            else
                sum[i + 1] = M::acted(sum[i], as[i]);
        }
        for (usize i : idx)
            res[i] = M::operation(sum[qs[i].l], sum[qs[i].r]);
    };
    auto rec = [&](auto rec, usize L, usize R, std::vector<usize> idx) -> void {
        if (L >= R)
            return;
        if (L + 1 == R) {
            f(L, idx);
            return;
        }
        const usize mid = (L + R) / 2;
        std::vector<usize> toL, toR, cur;
        for (auto&& i : idx) {
            assert(qs[i].l <= qs[i].r and static_cast<usize>(qs[i].r) <= as.size());
            if (static_cast<usize>(qs[i].r) <= mid)
                toL.push_back(std::move(i));
            else if (mid <= static_cast<usize>(qs[i].l))
                toR.push_back(std::move(i));
            else
                cur.push_back(std::move(i));
        }
        if (cur.size())
            f(mid, cur);
        if (toL.size())
            rec(rec, L, mid, toL);
        if (toR.size())
            rec(rec, mid, R, toR);
    };
    std::vector<usize> idx(qs.size());
    std::iota(idx.begin(), idx.end(), 0);
    rec(rec, 0, as.size(), idx);
    return res;
}

} // namespace zawa
#line 10 "Test/AtCoder/abc223_h.test.cpp"

#include <iostream>
#include <array>
#include <bit>
#line 15 "Test/AtCoder/abc223_h.test.cpp"
using namespace zawa;
using namespace std;
struct M {
    using Element = array<unsigned long long, 60>;
    static unsigned long long reduce(const Element& B, unsigned long long v) {
        for (int i = 59 ; i >= 0 and v ; i--)
            if (v & (1ull << i))
                v ^= B[i];
        return v;
    }
    static bool insert(Element& B, unsigned long long v) {
        v = reduce(B, v);
        if (v) {
            B[bit_width(v) - 1] = v;
            return true;
        }
        return false;
    }
    static Element identity() {
        Element res;
        res.fill(0);
        return res;
    }
    static Element operation(Element l, Element r) {
        for (unsigned long long v : r)
            if (v)
                insert(l, v);
        return l;
    }
    static Element acted(Element l, unsigned long long v) {
        insert(l, v);
        return l;
    }
};
struct query {
    int l, r;
};
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector<unsigned long long> A(N), X(Q);
    for (int i = 0 ; i < N ; i++)
       cin >> A[i];
    vector<query> lr(Q);
    for (int i = 0 ; i < Q ; i++) {
        int l, r;
        cin >> l >> r >> X[i];
        l--;
        lr[i] = {l, r};
    }
    auto ans = OfflineRangeProduct<M>(A, lr);
    for (int i = 0 ; i < Q ; i++)
        cout << (M::reduce(ans[i], X[i]) == 0 ? "Yes\n" : "No\n");
#else
    cout << "Hello World\n";
#endif
}
Back to top page