結果

問題 No.649 ここでちょっとQK！
ユーザー zawakasu
提出日時 2025-04-07 22:50:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 3,000 ms
コード長 4,219 bytes
コンパイル時間 1,355 ms
コンパイル使用メモリ 98,488 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-07 22:50:07
合計ジャッジ時間 4,943 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
// #define PROBLEM "https://yukicoder.me/problems/no/649"

/*
 * yukicoder No.649 ここでちょっとQK！
 * https://yukicoder.me/submissions/1065558
 */



#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


#include <concepts>

namespace zawa {

namespace Concept {

template <class T>
concept Monoid = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace

} // namespace zawa

namespace zawa {

namespace Concept {

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

#include <cassert>
#include <optional>
#include <utility>
#include <queue>

namespace zawa {

// 1-indexed
template <Concept::Group G>
class PriorityProductSet {
public:

    using V = G::Element;

    PriorityProductSet() = default;

    PriorityProductSet(usize K) : m_K{K} {}

    void insert(V&& v) {
        pushSmall(std::move(v));
        adjust();
    }

    void insert(const V& v) {
        insert(V{v});
    }

    usize size() const {
        return m_small.size() + m_big.size();
    }

    inline usize K() const {
        return m_K;
    }

    void setK(usize K) {
        m_K = K;
        adjust();
    }

    std::optional<V> product() const {
        return m_small.size() == m_K ? std::optional<V>{m_sv} : std::nullopt;
    }

    std::optional<V> productRemain() const {
        return m_small.size() == m_K ? std::optional<V>{m_bv} : std::nullopt;
    }

    V productAll() const {
        return G::operation(m_sv, m_bv);
    }

    V popK() {
        assert(m_K >= 1u and size() >= m_K);
        V res = popSmall(); 
        adjust();
        return res;
    }

private:

    std::priority_queue<V> m_small;

    std::priority_queue<V, std::vector<V>, std::greater<V>> m_big;

    V m_sv = G::identity(), m_bv = G::identity();

    usize m_K = 0;

    void pushSmall(V&& v) {
        m_sv = G::operation(m_sv, v);
        m_small.push(std::move(v));
    }

    V popSmall() {
        assert(m_small.size());
        V res = m_small.top();
        m_small.pop();
        m_sv = G::operation(m_sv, G::inverse(res));
        return res;
    }

    void pushBig(V&& v) {
        m_bv = G::operation(m_bv, v);
        m_big.push(std::move(v));
    }

    V popBig() {
        assert(m_big.size());
        V res = m_big.top();
        m_big.pop();
        m_bv = G::operation(m_bv, G::inverse(res));
        return res;
    }

    void adjust() {
        while (m_small.size() > m_K) pushBig(popSmall());
        while (m_small.size() < m_K and m_big.size()) pushSmall(popBig());
    }
};

} // namespace zawa

struct G {
    using Element = long long;
    static Element identity() { return 0; }
    static Element operation(Element,Element) { return 0; }
    static Element inverse(Element) { return 0; }
};

#include <iostream>
int Q, K;
void solve() {
    std::cin >> Q >> K;
    zawa::PriorityProductSet<G> set(K);
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 1) {
            long long v;
            std::cin >> v;
            set.insert(v);
        }
        else if (t == 2) {
            if (set.size() < (int)K) {
                std::cout << -1 << '\n';
            }
            else {
                std::cout << set.popK() << '\n';
            }
        }
        else {
            assert(false);
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    solve();
#else
    std::cout << "Hello World\n";
#endif
}
0