yukicoder No.649 ここでちょっとQK！

yukicoder.me

類題がこれとこれ。

coonevo.hatenablog.com

coonevo.hatenablog.com

上記の類題と違うのは値の範囲が広いこと。こういうやつはクエリ先読みすると種類数が少ないから順序データに座標圧縮すればよい。あとはライブラリでやるだけ。

座圧のうまい書き方知らないからいつもmapでやってしまう・・・。

提出へのリンク

int main() {
    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);
            }
        }
    }
}