#856773 (C++17) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	Gandalfr
提出日時	2023-04-06 20:16:43
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	279 ms / 3,000 ms
コード長	7,179 bytes
コンパイル時間	2,066 ms
コンパイル使用メモリ	203,548 KB
実行使用メモリ	12,928 KB
最終ジャッジ日時	2024-04-10 16:01:59
合計ジャッジ時間	7,276 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	279 ms 6,940 KB
testcase_04	AC	230 ms 12,928 KB
testcase_05	AC	198 ms 12,800 KB
testcase_06	AC	203 ms 12,800 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	AC	108 ms 7,296 KB
testcase_13	AC	105 ms 7,296 KB
testcase_14	AC	106 ms 7,296 KB
testcase_15	AC	111 ms 7,424 KB
testcase_16	AC	110 ms 7,808 KB
testcase_17	AC	128 ms 7,936 KB
testcase_18	AC	141 ms 8,448 KB
testcase_19	AC	150 ms 8,704 KB
testcase_20	AC	158 ms 9,216 KB
testcase_21	AC	180 ms 9,472 KB
testcase_22	AC	181 ms 9,856 KB
testcase_23	AC	197 ms 10,368 KB
testcase_24	AC	209 ms 10,624 KB
testcase_25	AC	222 ms 11,008 KB
testcase_26	AC	236 ms 11,520 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	76 ms 7,424 KB
testcase_31	AC	78 ms 7,680 KB
testcase_32	AC	1 ms 6,944 KB
testcase_33	AC	1 ms 6,944 KB
testcase_34	AC	1 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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(T x){
        low.erase(x);
        high.erase(x);
        refill();
    }

    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;

}

yukicoder

結果

テストケース

ソースコード