結果

問題 No.649 ここでちょっとQK！
ユーザー jjjjjjjtgpptmjjjjjjjjjtgpptmjj
提出日時 2020-05-25 19:02:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 332 ms / 3,000 ms
コード長 3,559 bytes
コンパイル時間 2,230 ms
コンパイル使用メモリ 219,472 KB
実行使用メモリ 34,544 KB
最終ジャッジ日時 2024-10-13 02:09:33
合計ジャッジ時間 9,483 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 248 ms
7,528 KB
testcase_04 AC 208 ms
34,544 KB
testcase_05 AC 208 ms
34,516 KB
testcase_06 AC 55 ms
8,648 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 149 ms
17,464 KB
testcase_13 AC 145 ms
17,460 KB
testcase_14 AC 144 ms
17,464 KB
testcase_15 AC 142 ms
17,464 KB
testcase_16 AC 139 ms
17,420 KB
testcase_17 AC 165 ms
18,872 KB
testcase_18 AC 186 ms
20,280 KB
testcase_19 AC 197 ms
21,560 KB
testcase_20 AC 216 ms
23,172 KB
testcase_21 AC 231 ms
24,580 KB
testcase_22 AC 257 ms
26,052 KB
testcase_23 AC 271 ms
27,400 KB
testcase_24 AC 276 ms
28,928 KB
testcase_25 AC 316 ms
30,208 KB
testcase_26 AC 332 ms
31,620 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 111 ms
13,364 KB
testcase_31 AC 109 ms
13,368 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>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
template<typename T>
class BIT{
  public:
    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){print(data);}
    // k-th number (k is 1 - indexed)
    T get(int k){
        T res = 0;
        int sz = 1;
        while(sz < (int)data.size()) sz <<= 1;
        for(int i = sz / 2; i > 0; i >>= 1){
            if(res + i <= N && data[res + i] < k){
                k -= data[res + i];
                res += i;
            }
        }
        return res + 1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    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);
            }
        }
    }
}
0