結果

問題 No.649 ここでちょっとQK!
ユーザー mino_yellowmino_yellow
提出日時 2023-02-09 16:08:57
言語 PHP
(8.3.4)
結果
AC  
実行時間 2,908 ms / 3,000 ms
コード長 6,846 bytes
コンパイル時間 2,554 ms
コンパイル使用メモリ 30,828 KB
実行使用メモリ 57,284 KB
最終ジャッジ日時 2024-07-06 18:52:55
合計ジャッジ時間 38,150 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
31,348 KB
testcase_01 AC 34 ms
31,284 KB
testcase_02 AC 34 ms
31,112 KB
testcase_03 AC 330 ms
31,260 KB
testcase_04 AC 377 ms
54,208 KB
testcase_05 AC 366 ms
54,588 KB
testcase_06 AC 338 ms
54,588 KB
testcase_07 AC 36 ms
31,372 KB
testcase_08 AC 34 ms
31,248 KB
testcase_09 AC 36 ms
31,136 KB
testcase_10 AC 35 ms
30,968 KB
testcase_11 AC 34 ms
31,440 KB
testcase_12 AC 1,250 ms
43,060 KB
testcase_13 AC 1,233 ms
43,064 KB
testcase_14 AC 1,250 ms
42,936 KB
testcase_15 AC 1,324 ms
43,056 KB
testcase_16 AC 1,302 ms
43,188 KB
testcase_17 AC 1,459 ms
44,212 KB
testcase_18 AC 1,636 ms
44,852 KB
testcase_19 AC 1,794 ms
45,620 KB
testcase_20 AC 1,948 ms
46,388 KB
testcase_21 AC 2,152 ms
50,740 KB
testcase_22 AC 2,260 ms
51,000 KB
testcase_23 AC 2,479 ms
51,124 KB
testcase_24 AC 2,648 ms
57,156 KB
testcase_25 AC 2,794 ms
57,156 KB
testcase_26 AC 2,908 ms
57,284 KB
testcase_27 AC 43 ms
31,032 KB
testcase_28 AC 41 ms
31,192 KB
testcase_29 AC 42 ms
30,992 KB
testcase_30 AC 1,252 ms
43,064 KB
testcase_31 AC 1,330 ms
43,316 KB
testcase_32 AC 35 ms
31,124 KB
testcase_33 AC 34 ms
31,248 KB
testcase_34 AC 33 ms
30,992 KB
testcase_35 AC 34 ms
31,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff #

<?php
fscanf(STDIN,"%d%d",$Q,$K);
$spt = new SprayTree(0);
for($i=0;$i<$Q;++$i){
    $in = array_map('intval',explode(" ", trim(fgets(STDIN))));
    if($in[0]==1){
        $spt->push($in[1]);
    }elseif($spt->sz[$spt->root] >= $K){
        list($r,$x) = $spt->delite($K);
        echo $spt->v[$x] . PHP_EOL;
    }else{
        echo -1 . PHP_EOL;
    }
}



class SprayTree{
    // 左の子l、右の子r、親pr、値v、自分を根としたグラフのサイズsz、根root、次のキーnextkey
    // 子どもlrとか親prは、全て値ではなくキーを指してる。値は比較する時やいくつなのか見たい時だけvを見て使う。
    public $l,$r,$pr,$v,$sz,$root,$nextkey;
    //n = 0 ... 中身を空で作る。$this->pushなどで辺を張っていくこと。値v基準で順序を決めていく場合はこっち。(いらんかも)
    //n > 0 ... n個の1列に繋がった木を作る。値vが空なので後で代入すること。要素の順番で順序を付ける場合とかはこっち
    function __construct($n){
        $this->nextkey = 0;
        $this->sz[-1] = 0;
        for($i=0;$i<$n;++$i){
            $this->l[$i] = $i-1;
            $this->r[$i] = -1;
            $this->pr[$i] = $i+1;
            $this->v[$i] = NULL;
            $this->sz[$i] = 1;
            $this->resize($i);
        }
        if($n > 0) $this->pr[$n-1] = -1;
        $this->root = $n-1;
    }

    function route($me){//一段上に上げるように回転
        $p = $this->pr[$me]; $pp = $this->pr[$p];
        if($this->l[$p] == $me){//自分が左の子
            $son = $this->r[$me];
            $this->r[$me] = $p;
            $this->l[$p] = $son;
        }else{//自分が右の子
            $son = $this->l[$me];
            $this->l[$me] = $p;
            $this->r[$p] = $son;
        }
        if($pp!=-1 && $this->l[$pp] == $p) $this->l[$pp] = $me;
        elseif($pp!=-1 && $this->r[$pp] == $p) $this->r[$pp] = $me;
        $this->pr[$me] = $pp;
        $this->pr[$p] = $me;
        if($son!=-1)$this->pr[$son] = $p;

        $this->resize($p);
        $this->resize($me);
    }

    function resize($me){
        $this->sz[$me] = 1 + $this->sz[$this->l[$me]] + $this->sz[$this->r[$me]];
    }

    function splay($me){//この操作でどうして平衡になるのかは謎
        while($this->lrcheck($me) != 0){
            $p = $this->pr[$me];
            if($this->pr[$p] == -1){//親が根
                $this->route($me);
            }elseif($this->lrcheck($me) == $this->lrcheck($p)){//まっすぐ
                $this->route($p);
                $this->route($me);
            }elseif($this->lrcheck($me) != $this->lrcheck($p)){//くの字
                $this->route($me);
                $this->route($me);
            }
        }
        $this->root = $me;
    }

    function lrcheck($me){
        $p = $this->pr[$me];
        if($p==-1) return 0;
        elseif($this->l[$p] == $me) return -1;
        elseif($this->r[$p] == $me) return 1;
    }

    function get($x){//左からx番目のキーを返す
        --$x;//標準では左端を1番目とする。左端を0番目とするような問題の場合はその値を++するか、この行を消しておく
        $now = $this->root;
        while(true){
            $lsz = $this->sz[$this->l[$now]];
            if($x < $lsz){
                $now = $this->l[$now];
            }elseif($x == $lsz){
                $this->splay($now);
                return $now;
            }else{
                $now = $this->r[$now];
                $x -= $lsz + 1; //左のノードの分 xをずらす (少しややこしい)
            }
        }
    }

    function merge($lro,$rro){//合体した後の根を返す。引数は必ず各木の根であること!
        if($lro == -1) return $rro;
        if($rro == -1) return $lro;
        $this->root = $lro;
        $lro = $this->get($this->sz[$lro]);//左の木の右端を根にして、その右の子として右の木をくっつける
        $this->r[$lro] = $rro;
        $this->pr[$rro] = $lro;
        $this->resize($lro);
        $this->root = $lro;
        return $lro;
    }

    function splitt($x){//x番目とx+1番目を切り離す
    //この瞬間だけは根が複数になるため、どっちの根がいくつか自力で覚えておく必要があるため要注意!
    //基本的にsplittして用が済んだらすぐにmergeすること。そもそも複数の木を扱いたいなら、別の変数に別の木を用意するべし
    //標準ではspilittした左の木の方をthis->rootとしている。
        if($x == 0) return [-1,$this->root];
        if($x == $this->sz[$this->root]) return [$this->root,-1];
        $this->root = $this->get($x);//x番目を根にしてそいつと右の子を切り離す
        $lro = $this->root;
        $rro = $this->r[$lro];
        $this->r[$lro] = -1;
        $this->pr[$rro] = -1;
        $this->resize($lro);
        return [$lro,$rro];
    }

    function insert($x,$me){//x番目がmeになるように入れる
        list($lro,$rro) = $this->splitt($x-1);
        $this->root = $this->merge($this->merge($lro,$me),$rro);
    }

    function delite($x){//x番目の頂点を木からもぐ。木の根ともいだキーを返す。
      //deliteと書いてるけど本体の木と切り離すだけで消すわけじゃない
        $ro = $this->get($x);//x番目を根にする
        $lro = $this->l[$ro];
        $rro = $this->r[$ro];
        if($lro != -1) $this->pr[$lro] = -1;
        if($rro != -1) $this->pr[$rro] = -1;
        $this->l[$ro] = -1;
        $this->r[$ro] = -1;
        $this->resize($ro);
        $this->root = $this->merge($lro,$rro);//x番目を取って、辺情報を整理したらx番目の右左をmerge
        return [$this->root,$ro];
    }

    function push($a){//値vを基準に正しい場所に新しい頂点を挿入。試作段階(作ったけどいらんかも)
        $k = $this->nextkey;
        ++$this->nextkey;
        $this->l[$k] = -1;
        $this->r[$k] = -1;
        $this->v[$k] = $a;
        $this->sz[$k] = 1;
        if($this->root == -1){
            $this->root = $k;
            $this->pr[$k] = -1;
            return;
        }
        $now = $this->root;
        while($now != -1){
            //その値vが今見てる頂点未満なら左、以上なら右にいくようにする。
            //つまり今見てる頂点と新しい頂点が同じ値の場合はその右側に行くようになる。
            $p = $now;
            if($a < $this->v[$now]) $now = $this->l[$now];
            else $now = $this->r[$now];
        }
        $this->pr[$k] = $p;
        if($a < $this->v[$p]) $this->l[$p] = $k;
        else $this->r[$p] = $k;
        $this->splay($k);
    }
}


?>
0