結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー yurina256
提出日時 2025-10-21 15:06:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 322 ms / 3,000 ms
コード長 3,705 bytes
コンパイル時間 4,045 ms
コンパイル使用メモリ 258,328 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2025-10-21 15:06:15
合計ジャッジ時間 10,537 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std; 
using namespace atcoder;
using mint = modint998244353;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define int long long
#define ll long long
#define ALL(v) (v).begin(), (v).end()
#define NP next_permutation
#define PLL pair<long long,long long>
#define VL vector<long long>
#define VVL vector<vector<long long>>
#define VVVL vector<vector<vector<long long>>>
#define VPLL vector<pair<long long,long long>>
#define STL set<long long>
#define MPLL map<long long,long long>
#define SP fixed << setprecision(12)

constexpr ll inf = 4001001001001001001ll;
constexpr ll mod = /* 1000000007 */ 998244353;
constexpr double pi = 3.141592653589793;
constexpr double eps = 0.00000000001;
vector<ll> d8x = {1,1,0,-1,-1,-1,0,1};
vector<ll> d8y = {0,1,1,1,0,-1,-1,-1};
vector<ll> d4x = {1,0,-1,0};
vector<ll> d4y = {0,1,0,-1};
//小数出力
//cout << setprecision(12);
//struct
struct Ruiseki{
  vector<ll> v;
  Ruiseki(vector<ll> &vec){
    ll n = vec.size();
    v.resize(n+1);
    rep(i,n) v[i+1] = v[i] + vec[i];
  }
  ll get(ll l,ll r){//閉区間!!
    return v[r+1]-v[l];
  }
};
//max
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
//min
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
//join
template<typename T> string join(vector<T> &vec ,const string &sp=" "){
    int si = vec.size();
    if(si==0){
        return "";
    }else{
        stringstream ss;
        rep(i,si-1){
            ss << vec[i] << sp;
        }
        ss << vec[si - 1];
        return ss.str();
    }
}
//print
void print() { cout << endl; }
template<typename T>
void print(const T &t) { cout << t << endl; }
template<typename T>
void print(pair<T,T> &p) {cout << p.first << ' ' << p.second << endl;}
template<typename T>
void print(vector<T> &vec){cout << join(vec) << endl; }
template<typename Head, typename... Tail>
void print(const Head &head, const Tail &... tail) {
    cout << head << ' ';
    print(tail...);
}
//Yes
string Yes(bool x){
  if(x) return "Yes\n";
  return "No\n";
}
string YES(bool x){
  if(x) return "YES\n";
  return "NO\n";
}
bool in_range(int l,int x,int r){//閉区間
 return ((l <= x ) && (x <= r) )||( (r <= x ) && (x <= l));
 }
int div_ceil(int x,int y){
  return (x+y-1)/y;
}
void yakubun(ll &a,ll &b){
  ll g = gcd(a,b);
  a /= g;
  b /= g;
}
ll _sqrt(ll x){
	ll a=sqrt(x);
	while((a+1)*(a+1)<=x) a++;
	while(a*a>x) a--;
	return a;
}
//Template End
struct GetKth{
  multiset<ll> lower;
  multiset<ll> upper;
  ll k;
  GetKth(ll a){
    k = a;
  }
  void insert(ll n){
    lower.insert(n);
    if((ll)lower.size() > k){
      ll a = *lower.rbegin();
      lower.erase(lower.find(a));
      upper.insert(a);
    }
  }
  ll get(){
    if((ll)lower.size() < k) return inf;
    else return *lower.rbegin();
  }
  void erase(ll n){
    if(n <= get()){
    //  print("erase",n);
      lower.erase(lower.find(n));
      if((ll)upper.size() > 0){
        ll a = *upper.begin();
    //    print("move",a);
        upper.erase(upper.find(a));
        lower.insert(a);
      }
    }else{
      upper.erase(upper.find(n));
    }
  }
  ll size(){
    return upper.size() + lower.size();
  }
};
signed main(void){
  ll q,k;
  cin >> q >> k;
  GetKth gk(k);
  rep(i,q){
    ll t;
    cin >> t;
    if(t == 1){
      ll a;
      cin >> a;
      gk.insert(a);
    }else{
      ll a = gk.get();
      if(a == inf) cout << -1 << endl;
      else{
        cout << a << endl;
        gk.erase(a);
      }
    }
  }
  
}
0