結果
| 問題 |
No.649 ここでちょっとQK！
|
| コンテスト | |
| ユーザー |
 mino_yellow
|
| 提出日時 | 2023-02-09 16:08:57 |
| 言語 | PHP (843.2) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
コンパイルメッセージ
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);
}
}
?>