結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 mino_yellow
|
| 提出日時 | 2023-02-09 16:08:57 |
| 言語 | PHP (8.3.4) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,846 bytes |
| コンパイル時間 | 907 ms |
| コンパイル使用メモリ | 18,604 KB |
| 実行使用メモリ | 61,824 KB |
| 最終ジャッジ日時 | 2023-09-21 00:06:54 |
| 合計ジャッジ時間 | 41,947 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 16 ms
19,000 KB |
| testcase_01 | AC | 15 ms
18,976 KB |
| testcase_02 | AC | 16 ms
18,904 KB |
| testcase_03 | AC | 371 ms
18,976 KB |
| testcase_04 | AC | 473 ms
61,764 KB |
| testcase_05 | AC | 455 ms
61,688 KB |
| testcase_06 | AC | 409 ms
61,824 KB |
| testcase_07 | AC | 15 ms
18,980 KB |
| testcase_08 | AC | 15 ms
18,964 KB |
| testcase_09 | AC | 15 ms
18,788 KB |
| testcase_10 | AC | 16 ms
18,908 KB |
| testcase_11 | AC | 16 ms
18,832 KB |
| testcase_12 | AC | 1,800 ms
39,372 KB |
| testcase_13 | AC | 1,785 ms
39,236 KB |
| testcase_14 | AC | 1,732 ms
39,428 KB |
| testcase_15 | AC | 1,882 ms
39,416 KB |
| testcase_16 | AC | 1,858 ms
39,452 KB |
| testcase_17 | AC | 2,093 ms
39,384 KB |
| testcase_18 | AC | 2,347 ms
40,040 KB |
| testcase_19 | AC | 2,586 ms
40,536 KB |
| testcase_20 | AC | 2,806 ms
41,348 KB |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
コンパイルメッセージ
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);
}
}
?>