結果
| 問題 |
No.649 ここでちょっとQK！
|
| コンテスト | |
| ユーザー |
 バカらっく
|
| 提出日時 | 2018-02-10 12:14:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 9,288 bytes |
| コンパイル時間 | 949 ms |
| コンパイル使用メモリ | 116,324 KB |
| 実行使用メモリ | 826,492 KB |
| 最終ジャッジ日時 | 2024-10-13 05:31:47 |
| 合計ジャッジ時間 | 4,751 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 4 MLE * 1 -- * 27 |
コンパイルメッセージ
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) {
this.Refresh();
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;
}
this.Right = null;
this.Left = null;
this.Parent = null;
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();
this.Parent = null;
}
} else {
TreeNode cp = this.Parent;
TreeNode cc;
if(this.Left != null) {
cc = this.Left;
this.Left = null;
} else {
cc = this.Right;
this.Right = null;
}
this.Parent = null;
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 <this.Value) {
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) {
if (k == this.Key)
{
this.ValueValue++;
Refresh();
return this;
}
if (k < this.Key)
{
if (this.Left == null)
{
TreeNode n = new TreeNode(k);
this.Left = n;
n.Parent = this;
n.Refresh();
return n;
}
else
{
return this.Left.Add(k);
}
}
else
{
if (this.Right == null)
{
TreeNode n = new TreeNode(k);
this.Right = n;
n.Parent = this;
n.Refresh();
return n;
}
else
{
return this.Right.Add(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 = @"
13 3
1 0
1 0
1 0
1 0
1 0
1 0
2
2
2
2
2
2
2
";
}
public static void Main(string[] args)
{
#if DEBUG
Reader.IsDebug = true;
#endif
Program prg = new Program();
prg.Proc();
}
}