結果

問題 No.649 ここでちょっとQK！
ユーザー poohbear
提出日時 2020-08-28 13:39:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 331 ms / 3,000 ms
コード長 3,175 bytes
コンパイル時間 2,547 ms
コンパイル使用メモリ 204,464 KB
最終ジャッジ日時 2025-01-13 15:58:35
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
//typedef vector<vector<ll> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e9;
/*座標圧縮
vector vecを受け取り、座標圧縮した結果に書き換える
com[k]で座標圧縮後のkが示す実際の座標を返す
*/

template<typename T>
struct Compress{
    vector<T> res;
    Compress(vector<T> &vec){
        res = vec;
        sort(res.begin(),res.end());
        res.erase(unique(res.begin(),res.end()),res.end());
        for(ll i=0;i<(ll)vec.size();i++){
            vec[i] = lower_bound(res.begin(),res.end(),vec[i])-res.begin();
        }
    }

    ll get(const T &x){
        return lower_bound(res.begin(),res.end(),x) - res.begin();
    }

    const T &operator[](ll k) const{
        return res[k];
    }
};

/*BIT
    区間和と値の更新が対数時間でできる
    1-indexedであることに注意
    add(k,x)=要素kに値xを加える
    sum(k)=a_1+a_2+...+a_kを計算する
    query(l,r)=a_l+a_l+1+...a_rを計算する
    lower_bound(w)=a_1+a_2+...+a_x>=wとなる最小のxを求める(a_iが負の時は使えない)
    (全て足してもw未満であった場合要素数+1を返す)
    prll()=現在の各要素の値を確認する
*/

template<typename T>
struct BIT{
    ll n;//要素数
    vector< T > data;

    BIT(ll n_):n(n_+1),data(n,0){}

    void add(ll k, T x){
        for(ll i = k;i < n;i += (i & -i)){
            data[i] += x;
        }
    }

    T sum(ll k){
        T s(0);
        for(ll i = k; i > 0; i -= (i & -i)){
            s += data[i];
        }
        return s;
    }

    T query(ll l,ll r){
        return sum(r) - sum(l-1);
    }

    ll lower_bound(T w){
        if(w <= 0)return 0;
        else{
            ll x = 0;
            ll r = 1;
            while(r < n) r = r << 1;
            for(ll len = r; len > 0; len = len >> 1){
                if(x+len<n && data[x+len]<w){
                    w -= data[x+len];
                    x += len;
                }
            }
            return x+1;
        }
    }

    void print(){
        for(ll i=1;i<n;i++){
            cout << query(i,i) << ' ';
        }
        cout << endl;
    }
};

int main(){
    ll q,k;
    cin >> q >> k;
    vector<P>que;
    vector<ll>seen;
    rep(i,q){
        ll x;
        cin >> x;
        if(x==1){
            ll y;
            cin >> y;
            seen.push_back(y);
            que.push_back({x,y});
        }
        else{
            que.push_back({x,0});
        }
    }
    Compress<ll>com(seen);
    BIT<ll>bit(seen.size());
    rep(i,q){
        if(que[i].first==1){
            ll idx = com.get(que[i].second);
            bit.add(idx+1,1);
        }
        else{
            ll w = bit.lower_bound(k);
            if(w==seen.size()+1)cout << -1 << endl;
            else cout << com[w-1] << endl;
            bit.add(w,-1);
        }
    }
    return 0;
}
0