結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 mino_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
ソースコード
<?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個の１列に繋がった木を作る。値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;//標準では左端を１番目とする。左端を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);
}
}
?>