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

Depends on

Code

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

/*
 * AtCoder Beginner Contest 403 G - Odd Position Sum Query
 * https://atcoder.jp/contests/abc403/submissions/67039553
 */

#include "../../Src/DataStructure/SegmentTree/SparseSegmentTree.hpp"

#include <iostream>

struct D {
    int cnt{};
    long long sum[2]{0,0};
    D() = default;
    D(int c, long long x) : cnt{c} { // x ga c ko
        sum[0] = x * ((c + 1) / 2);
        sum[1] = x * (c / 2);
    }
};

struct M {
    using Element = D;
    static Element identity() {
        return D{};
    }
    static Element operation(Element L, Element R) {
        if (L.cnt % 2) std::swap(R.sum[0], R.sum[1]);
        L.cnt += R.cnt;
        L.sum[0] += R.sum[0];
        L.sum[1] += R.sum[1];
        return L;
    }
};

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int Q;
    std::cin >> Q;
    const int N = (int)1e9;
    long long z = 0;
    zawa::SparseSegmentTree<M> seg(N + 1);
    while (Q--) {
        long long y;
        std::cin >> y;
        y = (z + y) % N + 1;
        auto v = seg.get(y);
        seg.assign(y, D{v.cnt + 1, y});
        z = seg.product(0, N + 1).sum[0];
        std::cout << z << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc403_g.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc403/tasks/abc403_g"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 403 G - Odd Position Sum Query
 * https://atcoder.jp/contests/abc403/submissions/67039553
 */

#line 2 "Src/DataStructure/SegmentTree/SparseSegmentTree.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 5 "Src/DataStructure/SegmentTree/SparseSegmentTree.hpp"

#include <cassert>
#include <limits>
#include <optional>
#include <vector>

namespace zawa {

template <concepts::Monoid Monoid>
class SparseSegmentTree {
public:

    using VM = Monoid;

    using V = typename VM::Element;

    using OM = Monoid;

    using O = typename OM::Element;

    SparseSegmentTree() = default;

    explicit SparseSegmentTree(usize n, usize poolSize = 0u) : m_n{n}, m_pool(1) {
        m_pool.reserve(poolSize);
    }

    inline usize size() const {
        return m_n;
    }

    void assign(usize p, V v) {
        assert(p < size());
        set(0, p, v, 0, size());
    }

    [[nodiscard]] V get(usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V operator[](usize p) const {
        return get(0, p, 0, size());
    }

    [[nodiscard]] V product(usize l, usize r) const {
        assert(l <= r and r <= size());
        return product(0, l, r, 0, size());
    }

private:

    struct node {
        static constexpr usize INVALID = std::numeric_limits<usize>::max();
        usize lch{INVALID}, rch{INVALID};
        V v{VM::identity()};
    };

    static constexpr usize mid(usize l, usize r) {
        return (l & r) + ((l ^ r) >> 1);
    }
    
    void set(usize i, usize p, const V& v, usize l, usize r) {
        if (l + 1 == r) {
            m_pool[i].v = v;
            return;
        }
        const usize m = mid(l, r);
        if (p < m) {
            if (m_pool[i].lch == node::INVALID) m_pool[i].lch = makeNode();
            set(m_pool[i].lch, p, v, l, m);
        }
        else {
            if (m_pool[i].rch == node::INVALID) m_pool[i].rch = makeNode();
            set(m_pool[i].rch, p, v, m, r);
        }
        m_pool[i].v = VM::operation(
                m_pool[i].lch == node::INVALID ? VM::identity() : m_pool[m_pool[i].lch].v,
                m_pool[i].rch == node::INVALID ? VM::identity() : m_pool[m_pool[i].rch].v
                );
    }

    V get(usize i, usize p, usize l, usize r) const {
        if (i == node::INVALID) return VM::identity();
        if (l + 1 == r) return m_pool[i].v;
        const usize m = mid(l, r);
        if (p < m) return get(m_pool[i].lch, p, l, m);
        else return get(m_pool[i].rch, p, m, r);
    }

    V product(usize i, usize l, usize r, usize curL, usize curR) const {
        if (i == node::INVALID) return VM::identity();
        if (r <= curL or curR <= l) return VM::identity();
        if (l <= curL and curR <= r) return m_pool[i].v;
        else {
            const usize m = mid(curL, curR);
            return VM::operation(
                        product(m_pool[i].lch, l, r, curL, m),
                        product(m_pool[i].rch, l, r, m, curR)
                    );
        }
    }

    usize makeNode() {
        usize res = m_pool.size();
        m_pool.emplace_back();
        return res;
    }

    usize m_n{};

    std::vector<node> m_pool{};
};

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

#include <iostream>

struct D {
    int cnt{};
    long long sum[2]{0,0};
    D() = default;
    D(int c, long long x) : cnt{c} { // x ga c ko
        sum[0] = x * ((c + 1) / 2);
        sum[1] = x * (c / 2);
    }
};

struct M {
    using Element = D;
    static Element identity() {
        return D{};
    }
    static Element operation(Element L, Element R) {
        if (L.cnt % 2) std::swap(R.sum[0], R.sum[1]);
        L.cnt += R.cnt;
        L.sum[0] += R.sum[0];
        L.sum[1] += R.sum[1];
        return L;
    }
};

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int Q;
    std::cin >> Q;
    const int N = (int)1e9;
    long long z = 0;
    zawa::SparseSegmentTree<M> seg(N + 1);
    while (Q--) {
        long long y;
        std::cin >> y;
        y = (z + y) % N + 1;
        auto v = seg.get(y);
        seg.assign(y, D{v.cnt + 1, y});
        z = seg.product(0, N + 1).sum[0];
        std::cout << z << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}
Back to top page