結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー utan
提出日時 2021-12-15 19:27:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 277 ms / 3,000 ms
コード長 2,031 bytes
コンパイル時間 2,021 ms
コンパイル使用メモリ 176,888 KB
実行使用メモリ 9,604 KB
最終ジャッジ日時 2024-07-23 20:01:11
合計ジャッジ時間 7,236 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;

typedef unsigned long long ull;


const double pi = 3.141592653589793;
int inf = 1001001001;
ll INF = 1001001001001001001;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define rep(i, n) FOR(i, 0, n)
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
using P = pair<ll, ll>;


ll mod2 = 998244353;


struct binary_indexed_tree{
    int N;
    vector<ll> bit;
    binary_indexed_tree(int n):N(n){
        bit.resize(N+1,0);
    }
    ll addition(ll x, ll y){
        return (x+y);
    }
    void add(int x,ll a){
        x++;
        for(x; x<=N; x+=(x&-x)) bit[x] = addition(bit[x],a);
    }
    ll sum(int x){
        x++;
        ll ret=0;
        for(x; x>0; x-=(x&-x)) ret = addition(ret,bit[x]);
        return ret;
    }

    ll get(ll k) {
        k++;
        ll res = 0;
        ll si = 1;
        while(si<bit.size()) si*=2;
        for (ll i = si/2; i>0; i/=2) {
            if (res+i<si&&bit[res+i]<k) {
                k-=bit[res+i];
                res+=i;
            }
        }

        return res;


    }

    
};



int main() {
    ll Q, K;cin >> Q >> K;
    vector<ll> V(Q);
    vector<ll> V2;
    vector<ll> T(Q);
    rep(i, Q) {
        cin >> T[i];
        if (T[i]==1) {
            ll v;cin >> v;
            V[i] = v;
            V2.pb(v);
            

        } 
    }

    sort(all(V2));
    V2.erase(unique(all(V2)), V2.end());
    
    binary_indexed_tree bit(200010);

    ll si = 0;


    rep(i, Q) {
        if (T[i]==1) {
            ll ind = lower_bound(all(V2), V[i])-V2.begin();
            bit.add(ind, 1);
            
            si++;

        } else {
            
            
            if (si<K) cout << -1 << endl;
            else {

                ll val = bit.get(K-1);
                cout << V2[val] << endl;
                bit.add(val, -1);
                si--;
            }
            
        }

        

            


        
    }

    return 0;
}
0