結果

問題 No.649 ここでちょっとQK！
ユーザー poohbearpoohbear
提出日時 2020-08-28 13:39:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 285 ms / 3,000 ms
コード長 3,175 bytes
コンパイル時間 2,442 ms
コンパイル使用メモリ 212,484 KB
実行使用メモリ 11,372 KB
最終ジャッジ日時 2024-11-09 01:11:56
合計ジャッジ時間 9,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 285 ms
7,628 KB
testcase_04 AC 213 ms
11,092 KB
testcase_05 AC 211 ms
11,216 KB
testcase_06 AC 192 ms
11,092 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 131 ms
7,328 KB
testcase_13 AC 130 ms
7,328 KB
testcase_14 AC 128 ms
7,324 KB
testcase_15 AC 129 ms
7,324 KB
testcase_16 AC 130 ms
7,328 KB
testcase_17 AC 142 ms
7,584 KB
testcase_18 AC 155 ms
7,964 KB
testcase_19 AC 168 ms
8,224 KB
testcase_20 AC 184 ms
9,372 KB
testcase_21 AC 198 ms
9,712 KB
testcase_22 AC 211 ms
10,092 KB
testcase_23 AC 225 ms
10,348 KB
testcase_24 AC 241 ms
10,608 KB
testcase_25 AC 252 ms
10,860 KB
testcase_26 AC 268 ms
11,372 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 3 ms
5,248 KB
testcase_30 AC 94 ms
7,196 KB
testcase_31 AC 93 ms
7,332 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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