結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー Gandalfr
提出日時 2023-04-06 20:36:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 3,000 ms
コード長 7,339 bytes
コンパイル時間 1,823 ms
コンパイル使用メモリ 202,940 KB
最終ジャッジ日時 2025-02-11 23:20:38
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 1 "library/gandalfr/other/io_supporter.hpp"


#line 7 "library/gandalfr/other/io_supporter.hpp"

std::ostream &operator<<(std::ostream &dest, __uint128_t value) {
	std::ostream::sentry s(dest);
	if (s) {
		__uint128_t tmp = value;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		int len = std::end(buffer) - d;
		if (dest.rdbuf()->sputn(d, len) != len) {
			dest.setstate(std::ios_base::badbit);
		}
	}
	return dest;
}

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
	std::ostream::sentry s(dest);
	if (s) {
		__int128_t tmp = value < 0 ? -value : value;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) {
			--d;
			*d = '-';
		}
		int len = std::end(buffer) - d;
		if (dest.rdbuf()->sputn(d, len) != len) {
			dest.setstate(std::ios_base::badbit);
		}
	}
	return dest;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for(int i=0; i<(int)v.size(); i++) os << v[i] << (i+1 != (int)v.size() ? " " : "");
    return os;
}
template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v){
    for(T &in : v) is >> in;
    return is;
}

template<typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2>& p) {
    os << p.first << " " << p.second;
    return os;
}
template<typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> v) {
    int N = v.size();
    for(int i=0; i<N; i++) {
        os << v.front() << (i+1 != N ? " " : "");
        v.pop();
    }
    return os;
}
template<typename T>
std::istream &operator>>(std::istream &is, std::queue<T> &v) {
    for(T &in : is) v.push(is);
    return is;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
    for(const T &x : st){
        std::cout << x << " ";
    }
    return os;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
    for(const T &x : st){
        std::cout << x << " ";
    }
    return os;
}



#line 3 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MAXINT = std::numeric_limits<int>::max();
const int MININT = std::numeric_limits<int>::min();
const ll INFLL = 1001001001001001001;
const ll MAXLL = std::numeric_limits<ll>::max();
const ll MINLL = std::numeric_limits<ll>::min();
const ll MOD  = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define fore(i,a) for(auto &i : a)
#define all(a) (a).begin(),(a).end()
#define lr(a, l, r) (a).begin()+(l),(a).begin()+(r)
#define LF cout << endl
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }
/*using mint = mod_integer<MOD>;
using _mint = mod_integer<_MOD>;
using binom = binomial_coefficients<mint>;
using _binom = binomial_coefficients<_mint>;*/
template<class T, std::size_t n, std::size_t idx = 0>
auto make_vec(const size_t (&d)[n], const T& init) noexcept {
    if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
    else return init;
}
template<class T, std::size_t n>
auto make_vec(const size_t (&d)[n]) noexcept { return make_vec(d, T{}); }

template<class T>
class Kth_hold_multiset{
  private:
    std::multiset<T> low, high;// low のサイズを K に保つ
    const int k;
    void refill(){
        while((int)low.size() < k) {
            auto it = high.begin();
            low.insert(*it);
            high.erase(it);
        }
        while((int)low.size() > k) {
            auto it = prev(low.end());
            high.insert(*it);
            low.erase(it);
        }
    }

    class Iterator {
      public:
        Iterator(typename std::multiset<T>::iterator it, std::multiset<T>& low, std::multiset<T>& high)
            : it_(it), low_(low), high_(high) {}

        bool operator==(const Iterator& other) const { return it_ == other.it_; }
        bool operator!=(const Iterator& other) const { return it_ != other.it_; }

        const T& operator*() const { return *it_; }

        Iterator& operator++() {
            ++it_;
            if(it_ == low_.end()) it_ = high_.begin();
            return *this;
        }

        Iterator operator++(int) {
            Iterator tmp = *this;
            ++(*this);
            return tmp;
        }

      private:
        typename std::multiset<T>::iterator it_;
        std::multiset<T>& low_;
        std::multiset<T>& high_;
    };


  public:
    Kth_hold_multiset(int K) : k(K) {}

    void insert(T x){
        if((int)low.size() < k) {
            low.insert(x);
            return;
        }
        
        T Kth = *prev(low.end());
        if(x >= Kth) high.insert(x);
        else low.insert(x);
        refill();
    }

    void erase_a_element(T x){
        if(high.empty()) {
            auto low_it = low.find(x); 
            if(low_it != low.end()) low.erase(low_it);
            return;
        }

        auto high_it = high.find(x); 
        auto low_it = low.find(x); 
        if(high_it != high.end()) high.erase(high_it);
        else if(low_it != low.end()) low.erase(low_it);
        refill();
    }

    void erase_all_element(T x){
        low.erase(x);
        high.erase(x);
        refill();
    }

    Iterator find(T x){
        auto low_it = low.find(x);
        if(low_it != low.end()) return Iterator(low_it, low, high);
        else return Iterator(high.find(x), low, high);
    }

    int size(){
        return low.size() + high.size();
    }

    T get_Kth_value(){
        return *prev(low.end());
    }

    int count(T x){
        return low.count(x) + high.count(x);
    }
    
    void dump(){
        int loop = low.size() + high.size();
        for(auto x : *this){
            loop--;
            std::cout << x << (loop ? " " : "");
        }
    }

    Iterator begin() {
        return low.empty() ? Iterator(high.end(), low, high) : Iterator(low.begin(), low, high);
    }
    Iterator end() {
        return Iterator(high.end(), low, high);
    }

};

int main(void){

    /*ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
    ofstream fout("output.txt");*/

 
    //input

    int Q, K;
    cin >> Q >> K;

    //calculate
    
    vector<ll> ans;
    Kth_hold_multiset<ll> st(K);
    rep(i,0,Q){
        int q;
        cin >> q;
        if(q == 1){
            ll x;
            cin >> x;
            st.insert(x);
        }
        else{
            if(st.size() < K){
                ans.push_back(-1);
            }
            else{
                ans.push_back(st.get_Kth_value());
                st.erase_a_element(st.get_Kth_value());
            }
        }
        //st.dump();
    }

    for(auto x : ans) cout << x << endl;

}
0