Test/AtCoder/abc247_d.test.cpp

View this file on GitHub
Last update: 2023-07-29 13:13:36+09:00
Problem: https://atcoder.jp/contests/abc247/tasks/abc247_d

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc247/tasks/abc247_d"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Sequence/RunLengthEncoding.hpp"

#include <iostream>

using namespace zawa;

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

    RunLengthEncoding<u32, u64> rle;
   
    usize Q; std::cin >> Q;
    for (u32 _{} ; _ < Q ; _++) {
        u32 t; std::cin >> t;
        if (t == 1) {
            u32 x, c; std::cin >> x >> c;
            rle.pushBack(x, c);
        }
        else if (t == 2) {
            u32 c; std::cin >> c;
            u64 ans{};
            for (const auto& data : rle.popFront(c)) {
                ans += (u64)data.value() * data.number();
            }
            std::cout << ans << std::endl;
        }
        else {
            assert(!"input failed");
        }
    }
}

#line 1 "Test/AtCoder/abc247_d.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc247/tasks/abc247_d"

#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/Sequence/RunLengthEncoding.hpp"

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

#include <deque>
#include <vector>
#include <cassert>

namespace zawa {

template <class Value, class Number = u64>
class RunLengthEncoding {
public:
    class Data {
    private:
        Value value_;
        Number number_;
    public:
        Data() = default;
        Data(const Value& value, Number number) : value_{ value }, number_{ number } {}

        const Value& value() const noexcept {
            return value_;
        }

        Number number() const noexcept {
            return number_;
        }

        friend RunLengthEncoding;
    };

private:
    std::deque<Data> seq_;
    u64 sum_{};

    template <class InputIterator>
    inline void build(InputIterator first, InputIterator last) {
        for (auto it{ first } ; it != last ; it++) {
            if (seq_.empty() or seq_.back().value() != *it) {
                seq_.emplace_back(*it, Number{1});
            }
            else {
                seq_.back().number_++;
            }
            sum_++;
        }
    }

public:
    RunLengthEncoding() = default;

    template <class InputIterator>
    RunLengthEncoding(InputIterator first, InputIterator last) {
        build(first, last);
    }

    RunLengthEncoding(const std::vector<Value>& a) {
        build(a.begin(), a.end());
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr u64 sum() const noexcept {
        return sum_;
    }

    const Data& operator[](u32 i) const noexcept {
        assert(i < size());
        return seq_[i];
    }

    const Value& value(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].value();
    }

    const Number number(u32 i) const noexcept {
        assert(i < size());
        return seq_[i].number();
    }

    typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

    const Data& front() const noexcept {
        assert(size());
        return seq_.front();
    }

    const Data& back() const noexcept {
        assert(size());
        return seq_.back();
    }

    void pushBack(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.back().value() != value) {
            seq_.emplace_back(value, number);
        }
        else {
            seq_.back().number_ += number;
        }
    }

    void pushFront(const Value& value, const Number number = Number{1}) {
        sum_ += number;
        if (seq_.empty() or seq_.front().value() != value) {
            seq_.emplace_front(value, number);
        }
        else {
            seq_.front().number_ += number;
        }
    }

    void popBack() {
        assert(size());
        sum_ -= seq_.back().number();
        seq_.pop_back();
    }

    void popFront() {
        assert(size());
        sum_ -= seq_.front().number();
        seq_.pop_front();
    }

    std::vector<Data> popBack(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.back().number()) {
            res.push_back(seq_.back());
            number -= seq_.back().number();
            seq_.pop_back();
        }
        if (number) {
            res.emplace_back(seq_.back().value(), number);
            seq_.back().number_ -= number;
        }
        return res;
    }

    std::vector<Data> popFront(u64 number) {
        assert(number <= sum());
        sum_ -= number;
        std::vector<Data> res;
        while (number and number >= seq_.front().number()) {
            res.push_back(seq_.front());
            number -= seq_.front().number();
            seq_.pop_front();
        }
        if (number) {
            res.emplace_back(seq_.front().value(), number);
            seq_.front().number_ -= number;
        }
        return res;
    }
};

} // namespace zawa
#line 5 "Test/AtCoder/abc247_d.test.cpp"

#include <iostream>

using namespace zawa;

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

    RunLengthEncoding<u32, u64> rle;
   
    usize Q; std::cin >> Q;
    for (u32 _{} ; _ < Q ; _++) {
        u32 t; std::cin >> t;
        if (t == 1) {
            u32 x, c; std::cin >> x >> c;
            rle.pushBack(x, c);
        }
        else if (t == 2) {
            u32 c; std::cin >> c;
            u64 ans{};
            for (const auto& data : rle.popFront(c)) {
                ans += (u64)data.value() * data.number();
            }
            std::cout << ans << std::endl;
        }
        else {
            assert(!"input failed");
        }
    }
}