結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー tsuyu93
提出日時 2020-12-07 23:38:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 267 ms / 3,000 ms
コード長 6,318 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 185,120 KB
実行使用メモリ 10,248 KB
最終ジャッジ日時 2024-09-17 14:08:50
合計ジャッジ時間 6,531 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
             author:ryo3ihara
            　　　　　　　”継続は力なり、雨だれ石を穿つ”
            　　　　　　　　　　”slow but steady wins the race”


*/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

//#include<atcoder/all>
//using namespace atcoder;

/* 
// 多倍長テンプレ
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
*/

using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pii = pair<int, int>;
using pld = pair<ll, ld>;
using ppiii =  pair<pii, int>;
using ppiill = pair<pii, ll>;
using ppllll = pair<pll, ll>;
using pplii = pair<pli, int>;
using mii = map<int, int>;
using dll = deque<ll>;
using qll = queue<ll>;
using pqll = priority_queue<ll>;
using pqrll = priority_queue<ll, vector<ll>, greater<ll>>;
using vint = vector<int>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vector<ll>>;
using vvint = vector<vector<int>>;
using vvpll = vector<vector<pll>>;

//マクロ
//forループ
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define ALL(x) x.begin(),x.end() 
#define rALL(x) x.rbegin(),x.rend() 
#define SIZE(x) ll(x.size()) 
#define fs first
#define sc second
#define INF32 2147483647 //2.147483647x10^{9}:32bit整数のinf
#define INF64 9223372036854775807 //9.223372036854775807x10^{18}:64bit整数のinf
//定数
const ll MOD = 1000000007;
const int inf = 1e9;
const ll INF = 1e18;
const ll MAXR = 100000; //10^5:配列の最大のrange

inline void Yes(bool b = true) { cout << (b ? "Yes" : "No") << '\n'; }
inline void YES(bool b = true) { cout << (b ? "YES" : "NO") << '\n'; }

//最大化問題最小化問題
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
//高速冪乗化　modの時は一部入れ替える
ll power(ll a, ll b) {
    ll res=1;
    while (b>0) {
        if (b&1){
            res*=a;
            //res%=MOD;
        }
        b/=2;
        a*=a;
        //a%=MOD;
    }
    return res;
}
ll power2(ll x, ll y) {
    if(y == 0) return 1;
    if(y == 1) {
        return x;
        // return x % MOD;
    }
    ll ans;
    if(y % 2 == 1) {
        ll r = power(x,(y-1)/2);
        //ans = r * r % MOD;
        //ans = ans * x % MOD;
        ans = x * r * r;
    }
    else {
        ll r = power(x,y/2);
        //ans = r * r % MOD;
        ans = r * r;
    }
    return ans;
}
/*
Bint powerb(Bint x, Bint y) {
    if(y == 0) return 1;
    if(y == 1) {
        return x;
        // return x % MOD;
    }
    Bint ans;
    if(y % 2 == 1) {
        Bint r = powerb(x,(y-1)/2);
        //ans = r * r % MOD;
        //ans = ans * x % MOD;
        ans = x * r * r;
    }
    else {
        Bint r = powerb(x,y/2);
        //ans = r * r % MOD;
        ans = r * r;
    }
    return ans;
}
*/

//数列a(a[0],a[1],…,a[n-1])についての区間和と点更新を扱う
//点更新,区間和,二分探索はO(log{n})で動作する
//https://qiita.com/DaikiSuyama/items/7295f5160a51684554a7
class BIT {
public:
    //データの長さ
    ll n;
    //データの格納先
    vector<ll> a;
    //コンストラクタ
    BIT(ll n):n(n),a(n+1,0){}

    //a[i]にxを加算する
    void add(ll i,ll x){
        i++;
        if(i==0) return;
        for(ll k=i;k<=n;k+=(k & -k)){
            a[k]+=x;
        }
    }

    //a[i]+a[i+1]+…+a[j]を求める [i,j]
    ll sum(ll i,ll j){
        return sum_sub(j)-sum_sub(i-1);
    }

    //a[0]+a[1]+…+a[i]を求める [0,i]
    ll sum_sub(ll i){
        i++;
        ll s=0;
        if(i==0) return s;
        for(ll k=i;k>0;k-=(k & -k)){
            s+=a[k];
        }
        return s;
    }

    //a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)
    ll lower_bound(ll x){
        if(x<=0){
            return 0;
        }else{
            ll i=0;ll r=1;
            while(r<n) r=r<<1;
            for(int len=r;len>0;len=len>>1) {
                if(i+len<n && a[i+len]<x){
                    x-=a[i+len];
                    i+=len;
                }
            }
            return i;
        }
    }
    //k-th number (k is 0-indexed)
    ll get(ll k) {
        ++k;
        ll res = 0;
        ll na = 1; while(na < (ll)a.size()) na *= 2;
        for(ll i = na / 2; i > 0; i /= 2) {
            if(res + i < (ll)a.size() && a[res + i] < k) {
                k -= a[res + i];
                res += i;
            }
        }
        return res; //0-indexed
    }
    //debug
    void print() {
        for(int i = 0; i < n; ++i) cout << sum(i, i) << ",";
        cout << endl;
    }
};

//BIT bit(n)で宣言
//sumは両閉区間

 template<typename T>
    vector<T> compress(vector<T> A){
        sort(A.begin(), A.end());
        A.erase(unique(A.begin(), A.end()), A.end());
        return A;
    }

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    ll Q,K;
    cin >> Q >> K;
    vll T(Q);
    vll V(Q);

    BIT bit(210000);
    vll queries;

    REP(i,Q){
        cin >> T[i];
        if(T[i]==1) cin >> V[i], queries.push_back(V[i]);   
    }

    sort(queries.begin(), queries.end());
    queries.erase(unique(queries.begin(), queries.end()), queries.end());

    REP(i,Q){
        if(T[i]==1){
            ll index = lower_bound(ALL(queries),V[i]) - queries.begin();
            //++index;
            bit.add(index,1);
        }
        else{
            ll size = bit.sum(0,209999);
            if(K>size){
                cout << -1 << endl;
            }
            else{
                ll n = bit.lower_bound(K);
                cout << queries[n] << endl;
                bit.add(n,-1);
            }
        }
    }

  return 0;
}
0