結果

問題 No.649 ここでちょっとQK！
ユーザー 🦠みどりむし🦠みどりむし
提出日時 2022-10-16 17:36:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 70 ms / 3,000 ms
コード長 3,327 bytes
コンパイル時間 2,468 ms
コンパイル使用メモリ 204,408 KB
実行使用メモリ 5,656 KB
最終ジャッジ日時 2023-09-09 19:54:28
合計ジャッジ時間 7,064 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 2 ms
4,356 KB
testcase_03 AC 22 ms
4,352 KB
testcase_04 AC 70 ms
5,656 KB
testcase_05 AC 55 ms
5,524 KB
testcase_06 AC 55 ms
5,340 KB
testcase_07 AC 2 ms
4,356 KB
testcase_08 AC 1 ms
4,352 KB
testcase_09 AC 1 ms
4,352 KB
testcase_10 AC 1 ms
4,352 KB
testcase_11 AC 1 ms
4,352 KB
testcase_12 AC 30 ms
4,360 KB
testcase_13 AC 30 ms
4,352 KB
testcase_14 AC 30 ms
4,356 KB
testcase_15 AC 33 ms
4,356 KB
testcase_16 AC 31 ms
4,352 KB
testcase_17 AC 38 ms
4,476 KB
testcase_18 AC 41 ms
4,416 KB
testcase_19 AC 46 ms
4,352 KB
testcase_20 AC 49 ms
4,492 KB
testcase_21 AC 53 ms
4,508 KB
testcase_22 AC 56 ms
4,780 KB
testcase_23 AC 59 ms
4,484 KB
testcase_24 AC 64 ms
4,528 KB
testcase_25 AC 67 ms
4,828 KB
testcase_26 AC 70 ms
4,640 KB
testcase_27 AC 2 ms
4,352 KB
testcase_28 AC 1 ms
4,352 KB
testcase_29 AC 2 ms
4,352 KB
testcase_30 AC 22 ms
4,356 KB
testcase_31 AC 25 ms
4,356 KB
testcase_32 AC 2 ms
4,352 KB
testcase_33 AC 1 ms
4,352 KB
testcase_34 AC 1 ms
4,352 KB
testcase_35 AC 2 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ GCC */
/* #region tmplate */
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_JUDGE
    #include<debug>
    #define debug(...) Debug::debug(Debug::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
    #define DEBUG(...) do { Debug::DEBUG(nullptr, "\033[3;35m#" + to_string(__LINE__) + "\033[m  "); Debug::DEBUG(__VA_ARGS__); Debug::DEBUG(nullptr, "\033[m\n"); } while(0);
#else
    #define debug(...) { ; }
    #define DEBUG(...) { ; }
#endif

#define INF32 2147483647
#define INF64 9223372036854775807LL

#define until(...) while(!(__VA_ARGS__))

#define REP(i,n) for(int i=0, i##_length=int(n); i<i##_length; ++i)
#define REPD(i,n) for(int i=(n)-1; i>=0; --i)
#define LOOP(n) REP(_$, (n))
#define FOR(i,l,r) for(ll i=(l), i##_last=ll(r); i<=i##_last; ++i)
#define FORD(i,l,r) for(ll i=(l), i##_last=ll(r); i>=i##_last; --i)

#define ITRP(x,v) for(auto x : (v))
#define ITRR(x,v) for(auto &x : (v))
#define ITR(x,v) for(const auto &x : (v))
#define ITRMP(x,y,v) for(auto [x, y] : (v))
#define ITRMR(x,y,v) for(auto &[x, y] : (v))
#define ITRM(x,y,v) for(const auto [x, y] : (v))

#define ALL(x) begin((x)),end((x))
#define RALL(x) rbegin((x)),rend((x))

#define $F first
#define $S second

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr char ln = '\n';
constexpr char spc = ' ';

inline void fast_io() { ios::sync_with_stdio(false), cin.tie(nullptr); }

template<class T1, class T2> inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }

template<class T> inline bool chmax(T &a, T b) { return (a<b ? a=b, true : false); }
template<class T> inline bool chmin(T &a, T b) { return (a>b ? a=b, true : false); }

template<class T> auto operator<<(ostream &out, const T &val) -> decltype(val.val(), out)& {
    return out << val.val();
}
/* #endregion */

template<class T, class Container = vector<T>, class CompA = less<T>, class CompB = greater<T>> struct KthElement {
  private:
    size_t K;
    priority_queue<T,Container,CompA> small;
    priority_queue<T,Container,CompB> large;

  public:
    KthElement(size_t K) : K(K) {}

    inline T get() const {
       return small.top();
    }
    inline bool has() const {
        return small.size() == K;
    }

    inline void push(T v) {
        if(small.size() < K) {
            small.push(v);
            return;
        }

        T kth = small.top();

        if(v < kth) {
            small.pop(); small.push(v);
            large.push(kth);
        }
        else {
            large.push(v);
        }
    }

    inline void pop() {
        small.pop();

        if(large.empty()) return;
        T v = large.top(); large.pop();
        small.push(v);
    }
};

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int q, k; cin >> q >> k;
    KthElement<ll> kth(k);
    LOOP(q) {
        int type; cin >> type;
        if(type == 1) {
            ll v; cin >> v;
            kth.push(v);
        }
        if(type == 2) {
            if(!kth.has()) {
                cout << -1 << ln;
                continue;
            }
            cout << kth.get() << ln;
            kth.pop();
        }
    }

    return 0;
}
0