Test/My/DataStructure/Heap/BinaryHeapCompVector.test.cpp

View this file on GitHub
Last update: 2026-01-14 16:33:38+09:00
Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include "../../../../Src/DataStructure/Heap/BinaryHeap.hpp"
using namespace zawa;

#include <queue>
#include <random>
#include <utility>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template <class T>
ostream& operator<<(ostream& os, vector<T> a) {
    for (int i = 0 ; i < ssize(a) ; i++)
        os << a[i] << (i + 1 == ssize(a) ? "" : " ");
    return os;
}

template <class Queue>
int test(const vector<pair<int, vector<long long>>>& query) {
    Queue q;
    chrono::system_clock::time_point start = chrono::system_clock::now();
    int res = 0;
    for (auto [t, v] : query) {
        if (t == 0) {
            q.push(v);
            res += 1;
        }
        else if (t == 1) {
            if (q.size())
                q.pop();
            res += 2;
        }
    }
    chrono::system_clock::time_point end = chrono::system_clock::now();
    cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    return res;
}

int main() {
    const int Q = 3000000;
    const int K = 10;
    mt19937_64 mt{random_device{}()};
    const long long V = mt() % (long long)1e18;
    vector<pair<int, vector<long long>>> q(Q);
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[i].first = 0;
        q[i].second = vector<long long>(K, V);
    }
    for (int i = Q / 2 ; i < Q ; i++) {
        q[i].first = mt() % 2;
        q[i].second = vector<long long>(K, V);
    }
    cerr << test<BinaryHeap<vector<long long>>>(q) << endl;
    int A, B;
    cin >> A >> B;
    cout << A + B << '\n';
}

#line 1 "Test/My/DataStructure/Heap/BinaryHeapCompVector.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#line 2 "Src/DataStructure/Heap/BinaryHeap.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 4 "Src/DataStructure/Heap/BinaryHeap.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>
#include <functional>

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class BinaryHeap {
private:

    Comp m_comp;

    std::vector<T> m_dat;

public:

    inline usize size() const {
        return m_dat.size() - 1;
    }

    inline bool empty() const {
        return m_dat.size() == 1;
    }

    inline const Comp& comp() const {
        return m_comp;
    }

    using const_iterator = typename decltype(m_dat)::const_iterator;

    const_iterator begin() const {
        return m_dat.begin() + 1;
    }

    const_iterator end() const {
        return m_dat.end();
    }

    BinaryHeap(Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    BinaryHeap(It first, It last, Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {
        m_dat.insert(m_dat.end(), first, last);
        build();
    }

    BinaryHeap(std::vector<T>&& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()), m_dat.begin() + 1);
        build();
    }

    BinaryHeap(const std::vector<T>& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(a.begin(), a.end(), m_dat.begin() + 1);
        build();
    }

    const T& top() const {
        assert(size() and "HeapUnderFlow");
        return m_dat[1];
    }

    void push(T&& v) {
        m_dat.push_back(std::move(v));
        upHeap(size());
    }

    void push(const T& v) {
        m_dat.push_back(v);
        upHeap(size());
    }

    void pop() {
        assert(size() and "HeapUnderFlow");
        if (size() > 1)
            std::swap(m_dat[1], m_dat.back());
        m_dat.pop_back();
        if (size() > 1)
            downHeap(1, size());
    }

private:

    void build() {
        const usize n = size();
        for (usize i = (n >> 1) ; i ; i--) 
            downHeap(i, n);
    }

    void upHeap(usize i) {
        while (i >> 1 and m_comp(m_dat[i], m_dat[i >> 1])) {
            std::swap(m_dat[i], m_dat[i >> 1]);
            i >>= 1;
        }
    }

    void downHeap(usize i, usize n) {
        while ((i << 1) <= n) {
            usize j = i << 1;
            if (j + 1 <= n and m_comp(m_dat[j + 1], m_dat[j]))
                j++;
            if (!m_comp(m_dat[j], m_dat[i]))
                break;
            std::swap(m_dat[i], m_dat[j]);
            i = j;
        }
    }
};

} // namespace zawa
#line 4 "Test/My/DataStructure/Heap/BinaryHeapCompVector.test.cpp"
using namespace zawa;

#include <queue>
#include <random>
#line 10 "Test/My/DataStructure/Heap/BinaryHeapCompVector.test.cpp"
#include <iostream>
#include <chrono>
using namespace std;

template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template <class T>
ostream& operator<<(ostream& os, vector<T> a) {
    for (int i = 0 ; i < ssize(a) ; i++)
        os << a[i] << (i + 1 == ssize(a) ? "" : " ");
    return os;
}

template <class Queue>
int test(const vector<pair<int, vector<long long>>>& query) {
    Queue q;
    chrono::system_clock::time_point start = chrono::system_clock::now();
    int res = 0;
    for (auto [t, v] : query) {
        if (t == 0) {
            q.push(v);
            res += 1;
        }
        else if (t == 1) {
            if (q.size())
                q.pop();
            res += 2;
        }
    }
    chrono::system_clock::time_point end = chrono::system_clock::now();
    cerr << chrono::duration_cast<chrono::milliseconds>(end - start).count() << endl;
    return res;
}

int main() {
    const int Q = 3000000;
    const int K = 10;
    mt19937_64 mt{random_device{}()};
    const long long V = mt() % (long long)1e18;
    vector<pair<int, vector<long long>>> q(Q);
    for (int i = 0 ; i < Q / 2 ; i++) {
        q[i].first = 0;
        q[i].second = vector<long long>(K, V);
    }
    for (int i = Q / 2 ; i < Q ; i++) {
        q[i].first = mt() % 2;
        q[i].second = vector<long long>(K, V);
    }
    cerr << test<BinaryHeap<vector<long long>>>(q) << endl;
    int A, B;
    cin >> A >> B;
    cout << A + B << '\n';
}