結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 バカらっく
|
| 提出日時 | 2018-02-10 12:04:42 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,064 bytes |
| コンパイル時間 | 4,474 ms |
| コンパイル使用メモリ | 108,928 KB |
| 実行使用メモリ | 825,216 KB |
| 最終ジャッジ日時 | 2024-04-21 06:35:58 |
| 合計ジャッジ時間 | 7,355 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | AC | 29 ms
27,448 KB |
| testcase_02 | AC | 29 ms
27,344 KB |
| testcase_03 | AC | 129 ms
29,208 KB |
| testcase_04 | MLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;
public class Program
{
public void Proc()
{
int[] qk = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
int q = qk[0];
int k = qk[1];
StringBuilder ans = new StringBuilder();
for (int i = 0; i < q; i++) {
long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
if(inpt[0]==1) {
long num = inpt[1];
if (TreeNode.Root == null)
{
TreeNode r = new TreeNode(num);
} else {
TreeNode.Root.Add(num);
}
} else {
if(TreeNode.Root == null || TreeNode.Root.Count < k) {
ans.AppendLine("-1");
} else {
TreeNode c = TreeNode.Root.Get(k - 1);
ans.AppendLine(c.Key.ToString());
c.Remove();
}
}
}
Console.Write(ans.ToString());
}
private class TreeNode {
public void Remove() {
if(--this.ValueValue>0) {
return;
}
if(this.Left != null && this.Right != null) {
TreeNode cp = this.Parent;
TreeNode cc1;
TreeNode cc2;
if(this.Left.Length >= this.Right.Length) {
cc1 = this.Left;
cc2 = this.Right;
} else {
cc1 = this.Right;
cc2 = this.Left;
}
cc1.Parent = cp;
cc2.Parent = null;
if(cp != null) {
if(cp.Left == this) {
cp.Left = cc1;
} else {
cp.Right = cc1;
}
}
cc1.Add(cc2);
return;
}
if(this.Left == null&&this.Right == null) {
if(this.Parent == null) {
TreeNode.Root = null;
} else {
if(this.Parent.Left == this) {
this.Parent.Left = null;
} else {
this.Parent.Right = null;
}
this.Parent.Refresh();
}
} else {
TreeNode cp = this.Parent;
TreeNode cc;
if(this.Left != null) {
cc = this.Left;
} else {
cc = this.Right;
}
cc.Parent = cp;
if(cp == null) {
TreeNode.Root = cc;
} else {
if(cp.Left == this) {
cp.Left = cc;
} else {
cp.Right = cc;
}
cp.Refresh();
}
}
}
public TreeNode Get(int idx) {
if(this.Left == null && this.Right == null) {
if(idx ==0) {
return this;
} else {
return null;
}
}
if(this.Left == null) {
if(idx<this.Value) {
return this;
} else {
return this.Right.Get(idx-this.Value);
}
}
if(idx<this.Left.Count) {
return this.Left.Get(idx);
}
if(idx >=this.Left.Count&&idx<this.Left.Count+this.Value) {
return this;
} else {
return this.Right.Get(idx - this.Left.Count - this.Value);
}
}
public static TreeNode Root;
public TreeNode Parent;
public TreeNode Left;
public TreeNode Right;
private int LengthValue;
private int CountValue;
public int Length {
get {
return LengthValue;
}
}
public int Count {
get {
return CountValue;
}
}
private int ValueValue;
public int Value {
get {
return ValueValue;
}
}
private long KeyValue;
public long Key {
get {
return this.KeyValue;
}
}
public TreeNode(long k) {
this.KeyValue = k;
this.ValueValue = 1;
if(Root == null) {
Root = this;
}
}
public TreeNode Add(long k) {
return Add(new TreeNode(k));
}
public TreeNode Add(TreeNode n) {
if (n.Key == this.Key)
{
this.ValueValue++;
Refresh();
return this;
}
if (n.Key < this.Key)
{
if (this.Left == null)
{
this.Left = n;
n.Parent = this;
n.Refresh();
return n;
}
else
{
return this.Left.Add(n);
}
}
else
{
if (this.Right == null)
{
this.Right = n;
n.Parent = this;
n.Refresh();
return n;
}
else
{
return this.Right.Add(n);
}
}
}
public void Refresh() {
int count = this.Value;
int leftLength = 0;
int rightLength = 0;
if(this.Left != null) {
count += this.Left.Count;
leftLength = this.Left.Length + 1;
}
if(this.Right != null) {
count += this.Right.Count;
rightLength = this.Right.Length + 1;
}
if(Math.Abs(rightLength-leftLength)>=2) {
TreeNode cp = this.Parent;
TreeNode cc;
if(rightLength>leftLength) {
cc = this.Right;
this.Right = null;
} else {
cc = this.Left;
this.Left = null;
}
cc.Parent = cp;
if(cp != null) {
if(cp.Right == this) {
cp.Right = cc;
} else {
cp.Left = cc;
}
}
cc.Add(this);
return;
}
int length = Math.Max(leftLength, rightLength);
if(this.Count==count&&this.Length==length&&(this.Left!=null||this.Right!=null)) {
return;
}
this.CountValue = count;
this.LengthValue = length;
if(this.Parent!=null) {
this.Parent.Refresh();
} else {
Root = this;
}
}
}
public class Reader
{
private static StringReader sr;
public static bool IsDebug = false;
public static string ReadLine()
{
if (IsDebug)
{
if (sr == null)
{
sr = new StringReader(InputText.Trim());
}
return sr.ReadLine();
}
else
{
return Console.ReadLine();
}
}
private static string InputText = @"
15 3
1 3
1 4
1 5
2
2
1 10
1 10
1 1
2
1 3
2
1 1000
2
1 0
2
";
}
public static void Main(string[] args)
{
#if DEBUG
Reader.IsDebug = true;
#endif
Program prg = new Program();
prg.Proc();
}
}