結果

問題 No.649 ここでちょっとQK！
ユーザー pppppp
提出日時 2018-02-15 02:03:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,152 ms / 3,000 ms
コード長 5,349 bytes
コンパイル時間 839 ms
コンパイル使用メモリ 101,756 KB
実行使用メモリ 12,808 KB
最終ジャッジ日時 2023-08-25 02:36:09
合計ジャッジ時間 18,933 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 253 ms
4,376 KB
testcase_04 AC 1,016 ms
12,748 KB
testcase_05 AC 1,020 ms
12,808 KB
testcase_06 AC 1,028 ms
12,800 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 529 ms
7,608 KB
testcase_13 AC 532 ms
7,648 KB
testcase_14 AC 525 ms
7,600 KB
testcase_15 AC 543 ms
7,616 KB
testcase_16 AC 537 ms
7,668 KB
testcase_17 AC 613 ms
8,084 KB
testcase_18 AC 674 ms
8,572 KB
testcase_19 AC 738 ms
8,980 KB
testcase_20 AC 762 ms
9,420 KB
testcase_21 AC 860 ms
9,768 KB
testcase_22 AC 945 ms
10,144 KB
testcase_23 AC 959 ms
10,572 KB
testcase_24 AC 1,077 ms
11,044 KB
testcase_25 AC 1,079 ms
11,456 KB
testcase_26 AC 1,152 ms
11,880 KB
testcase_27 AC 6 ms
4,376 KB
testcase_28 AC 6 ms
4,376 KB
testcase_29 AC 7 ms
4,380 KB
testcase_30 AC 528 ms
7,652 KB
testcase_31 AC 526 ms
7,604 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 2 ms
4,376 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <random>

using namespace std;

#define INT_MAX_VALUE 2147483647
#define LONG_LONG_MAX_VALUE 9223372036854775807
#define ll long long

template <class T>
T mymax(T a,T b){
    if(a>=b) return a;
    return b;
}
template <class T>
T mymin(T a,T b){
    if(a<=b) return a;
    return b;
}

ll gcd(ll a, ll b){
    if(a<b){
        swap(a,b);
    }
    while(b){
        ll r = a%b;
        a=b;
        b=r;
    }
    return a;
}

ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}

struct XX{
    ll a;
    int b;
    int j;
    int i;
};

class xxGreater {
public:
    bool operator()(const XX& riLeft, const XX& riRight) const {
        //第2条件
        if((riLeft.a) == (riRight.a)){
            return riLeft.i < riRight.i;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)
            //プライオリティキューの場合は > で、top()すると値の小さいものがとれる
        }
        //第1条件
        return (riLeft.a) < (riRight.a);
    }
};
class xxrevGreater {
public:
    bool operator()(const XX& riLeft, const XX& riRight) const {
        //第2条件
        if((riLeft.i) == (riRight.i)){
            return riLeft.i < riRight.i;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)
            //プライオリティキューの場合は > で、top()すると値の小さいものがとれる
        }
        //第1条件
        return (riLeft.i) < (riRight.i);
    }
};

//map<long long,long long> prime_f(long long n){
//    map<long long,long long>res;
//    for(int i=2;i*i<=n;i++){
//        while(n%i==0){
//            ++res[i];
//            n/=i;
//        }
//    }
//    if(n!=1)res[n]=1;
//    return res;
//}

//https://www.slideshare.net/iwiwi/2-12188757
//キー(val)の2分探索木
//優先度(pri)の2分ヒープ(各々のノードはそのノードの子よりも大きいか等しくなる)
struct node_t{
    ll val;//値
    node_t *ch[2];//左右ポインタ
    int pri;//優先度(ランダムな数値)
    int cnt;//部分木のサイズ
    ll sum;//部分木の値の和
    
    node_t(ll v,double p):val(v),pri(p),cnt(1),sum(1){
        ch[0]=ch[1]=NULL;
    }
};
int count(node_t *t){
    return !t ? 0:t->cnt;
}
ll sum(node_t *t){
    return !t ? 0:t->sum;
}
node_t *update(node_t *t){
    t->cnt=count(t->ch[0])+count(t->ch[1])+1;
    t->sum=sum(t->ch[0])+sum(t->ch[1])+t->val;
    return t;
}
node_t *rotate(node_t *t,int b){//b==0 or 1
    node_t *s=t->ch[1-b];//子(p)を保存
    t->ch[1-b]=s->ch[b]; //bを親(q)の左に付ける
    s->ch[b]=t;          //子(p)の右に親を付ける
    update(t);
    update(s);
    return s;            //子を親にする
}
//     q
//    / \
//   p   c
//  / \
// a   b
//これを下に回転
//     p
//    / \
//   a   q
//      / \
//     b   c

//tが根となっている木のk番目に値val,優先度priのノード挿入
node_t *insert(node_t *t,int k,ll val,int pri){
    if(!t){
        return new node_t(val,pri);
    }

    int b=(val > t->val);
    t->ch[b]=insert(t->ch[b],k,val,pri);
    update(t);
    if(t->pri > t->ch[b]->pri){
        t=rotate(t,1-b);
    }
    return t;
}
node_t *merge(node_t *l,node_t *r){
    if(!l || !r){
        return !l ? r:l;
    }
    if(l->pri > r->pri){
        l->ch[1]=merge(l->ch[1],r);
        return update(l);
    }else{
        r->ch[0]=merge(l,r->ch[0]);
        return update(r);
    }
}
pair<node_t*,node_t*> split(node_t *t,int k){//[0,k),[k,n)
    if(!t){
        node_t* ret=NULL;
        return make_pair(ret,ret);
    }
    if(k<=count(t->ch[0])){
        pair<node_t*,node_t*>s=split(t->ch[0],k);
        t->ch[0]=s.second;
        return make_pair(s.first,update(t));
    }else{
        pair<node_t*,node_t*>s=split(t->ch[1],k-count(t->ch[0])-1);
        t->ch[1]=s.first;
        return make_pair(update(t),s.second);
    }
}
node_t *t=NULL;

int main(int argc, const char * argv[])
{
    //scanf("%s",S);
    //scanf("%d",&N);
    //scanf("%lld %lld",&target1,&target2);
    //sscanf(tmp.c_str(),"%dd%d%d",&time[i], &dice[i], &z[i]);
    //getline(cin, target);
    //cin >> x >> y;
    //テスト用
    //ifstream ifs( "1_06.txt" );
    //ifs >> a;
    //ここから
    
    //入力高速化
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int Q,K;
    cin >> Q >> K;
    
    for(int i=0;i<Q;i++){
        ll tmp;
        cin >> tmp;
        if(tmp==1){
            ll tmp2;
            cin >> tmp2;
            std::random_device rnd;
            int r=rnd();
            t=insert(t,0,tmp2,r);
        }else{
            if(t==NULL || t->cnt<K){
                cout << -1 << endl;
            }else{
                pair<node_t*,node_t*>p1=split(t,K);
                pair<node_t*,node_t*>p2=split(p1.first,K-1);
                cout << p2.second->val << endl;
                t=merge(p2.first,p1.second);
            }
        }
    }

    
    
    //ここまで
    //cout << "ans" << endl;改行含む
    //printf("%.0f\n",ans);//小数点以下表示なし
    //printf("%.7f\n",p);
    
    return 0;
}
0