結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 271 ms
7,396 KB
testcase_04 AC 258 ms
34,572 KB
testcase_05 AC 245 ms
34,664 KB
testcase_06 AC 69 ms
8,508 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 175 ms
17,332 KB
testcase_13 AC 172 ms
17,456 KB
testcase_14 AC 174 ms
17,456 KB
testcase_15 AC 174 ms
17,460 KB
testcase_16 AC 167 ms
17,464 KB
testcase_17 AC 191 ms
18,740 KB
testcase_18 AC 218 ms
20,272 KB
testcase_19 AC 232 ms
21,684 KB
testcase_20 AC 262 ms
23,240 KB
testcase_21 AC 280 ms
24,560 KB
testcase_22 AC 302 ms
25,864 KB
testcase_23 AC 324 ms
27,392 KB
testcase_24 AC 346 ms
28,804 KB
testcase_25 AC 382 ms
30,336 KB
testcase_26 AC 411 ms
31,732 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 130 ms
13,368 KB
testcase_31 AC 127 ms
13,364 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 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