結果

問題 No.649 ここでちょっとQK！
ユーザー utanutan
提出日時 2021-12-15 19:19:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,004 bytes
コンパイル時間 1,796 ms
コンパイル使用メモリ 176,508 KB
実行使用メモリ 9,604 KB
最終ジャッジ日時 2024-07-23 20:00:56
合計ジャッジ時間 7,206 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 4 ms
6,944 KB
testcase_02 WA -
testcase_03 AC 290 ms
7,936 KB
testcase_04 AC 193 ms
9,604 KB
testcase_05 AC 193 ms
9,604 KB
testcase_06 AC 189 ms
9,604 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 WA -
testcase_13 AC 119 ms
7,148 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 4 ms
6,944 KB
testcase_28 AC 3 ms
6,940 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 3 ms
6,940 KB
testcase_33 AC 3 ms
6,940 KB
testcase_34 AC 3 ms
6,940 KB
testcase_35 AC 4 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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