結果

問題 No.649 ここでちょっとQK!
ユーザー 🦠みどりむし🦠みどりむし
提出日時 2022-10-16 17:36:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 3,000 ms
コード長 3,327 bytes
コンパイル時間 2,255 ms
コンパイル使用メモリ 200,232 KB
最終ジャッジ日時 2025-02-08 07:08:46
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0