結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー jjjjjjjtgpptmjj
提出日時 2020-05-25 19:02:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 456 ms / 3,000 ms
コード長 3,559 bytes
コンパイル時間 2,622 ms
コンパイル使用メモリ 210,348 KB
最終ジャッジ日時 2025-01-10 15:38:09
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#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 all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
template<typename T>
class BIT{
  public:
    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){print(data);}
    // k-th number (k is 1 - indexed)
    T get(int k){
        T res = 0;
        int sz = 1;
        while(sz < (int)data.size()) sz <<= 1;
        for(int i = sz / 2; i > 0; i >>= 1){
            if(res + i <= N && data[res + i] < k){
                k -= data[res + i];
                res += i;
            }
        }
        return res + 1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int Q, K;
    cin >> Q >> K;
    vec<l_l> qs;
    vec<ll> v;
    rep(i,Q){
        int ord;
        cin >> ord;
        if(ord == 1){
            ll tmp;
            cin >> tmp;
            v.push_back(tmp);
            qs.emplace_back(ord, tmp);
        }
        if(ord == 2){
            qs.emplace_back(ord, -1);
        }
    }
    //vを座圧する
    map<ll,ll> mp;
    map<ll,ll> mp2;
    ll cnt = 1;
    sort(all(v));
    rep(i,v.size()){
        if(i == 0){
            mp[v[i]] = cnt;
            mp2[cnt] = v[i];
            cnt++;
        }
        else if(v[i-1] != v[i]){
            mp[v[i]] = cnt;
            mp2[cnt] = v[i];
            cnt++;
        }
    }
    ll N = mp.size();
    BIT<ll> B(N);
    rep(i,Q){
        int ord = qs[i].first;
        if(ord == 1){
            ll x = qs[i].second;
            B.add(mp[x],1);
        }
        if(ord == 2){
            if(B.sum(N) < K){
                cout << -1 << endl;
            }
            else{
                ll res_idx = B.get(K);
                cout << mp2[res_idx] << endl;
                B.add(res_idx,-1);
            }
        }
    }
}
0