結果
問題 |
No.3298 K-th Slime
|
ユーザー |
![]() |
提出日時 | 2025-10-05 14:41:14 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 450 ms / 2,000 ms |
コード長 | 11,949 bytes |
コンパイル時間 | 10,447 ms |
コンパイル使用メモリ | 170,852 KB |
実行使用メモリ | 235,888 KB |
最終ジャッジ日時 | 2025-10-05 14:41:35 |
合計ジャッジ時間 | 16,093 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (105 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("5 3 8"); WillReturn.Add("1 2 3 4 5"); WillReturn.Add("1 6"); WillReturn.Add("3"); WillReturn.Add("2 4"); WillReturn.Add("3"); WillReturn.Add("1 10"); WillReturn.Add("3"); WillReturn.Add("2 10"); WillReturn.Add("3"); //3 //4 //4 //5 } else if (InputPattern == "Input2") { WillReturn.Add("5 3 13"); WillReturn.Add("3 8 5 2 9"); WillReturn.Add("2 6"); WillReturn.Add("2 1"); WillReturn.Add("1 1"); WillReturn.Add("1 10"); WillReturn.Add("2 7"); WillReturn.Add("1 4"); WillReturn.Add("3"); WillReturn.Add("1 10"); WillReturn.Add("1 8"); WillReturn.Add("3"); WillReturn.Add("1 5"); WillReturn.Add("2 3"); WillReturn.Add("3"); //4 //4 //5 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static long[] GetSplitArr(string pStr) { return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray(); } static void Main() { List<string> InputList = GetInputList(); long[] wkArr = { }; Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr); SplitAct(InputList[0]); long K = wkArr[1]; long[] AArr = GetSplitArr(InputList[1]); var Ins_AVL_Set_MultiSet = new AVL_Set_MultiSet<long>(); Ins_AVL_Set_MultiSet.IsMultiSet = true; foreach (long EachA in AArr) { Ins_AVL_Set_MultiSet.Add(EachA); } var sb = new System.Text.StringBuilder(); foreach (string EachStr in InputList.Skip(2)) { SplitAct(EachStr); long Type = wkArr[0]; if (Type == 1) { long X = wkArr[1]; Ins_AVL_Set_MultiSet.Add(X); } if (Type == 2) { long Y = wkArr[1]; long GetVal = Ins_AVL_Set_MultiSet[(int)K - 1]; Ins_AVL_Set_MultiSet.RemoveAt((int)K - 1); Ins_AVL_Set_MultiSet.Add(GetVal + Y); } if (Type == 3) { long GetVal = Ins_AVL_Set_MultiSet[(int)K - 1]; sb.Append(GetVal); sb.AppendLine(); } } Console.Write(sb.ToString()); } } #region AVL_Set_MultiSet /// <summary> /// 要素の追加、削除、検索、取得が可能な集合を表します. /// </summary> /// <typeparam name="T">優先度付きキュー内の要素の型を指定します.</typeparam> /// <remarks>内部的にはAVL木によって実装されています.</remarks> internal class AVL_Set_MultiSet<T> { Node root; readonly IComparer<T> comparer; readonly Node nil; /// <summary> /// 多重集合かどうかを表します. /// </summary> internal bool IsMultiSet { get; set; } internal AVL_Set_MultiSet(IComparer<T> comparer) { nil = new Node(default(T)); root = nil; this.comparer = comparer; } internal AVL_Set_MultiSet() : this(Comparer<T>.Default) { } /// <summary> /// 要素をコレクションに追加します. /// </summary> /// <remarks>この操作は計算量 O(log N) で実行されます.</remarks> internal bool Add(T v) { return insert(ref root, v); } /// <summary> /// v が存在するならコレクションから削除します. /// </summary> /// <remarks>この操作は計算量 O(log N) で実行されます.</remarks> internal bool Remove(T v) { return remove(ref root, v); } /// <summary> /// 0-indexed で index 番目の要素をコレクションから取得します. /// </summary> /// <remarks>この操作は計算量 O(log N) で実行されます.</remarks> internal T this[int index] { get { return find(root, index); } } internal int Count { get { return root.Count; } } internal void RemoveAt(int k) { if (k < 0 || k >= root.Count) throw new ArgumentOutOfRangeException(); removeAt(ref root, k); } /// <summary> /// このコレクションに含まれる要素を昇順に並べて返します. /// </summary> /// <remarks>この操作は計算量 O(N) で実行されます.</remarks> internal T[] Items { get { T[] ret = new T[root.Count]; int k = 0; walk(root, ret, ref k); return ret; } } private void walk(Node t, T[] a, ref int k) { if (t.Count == 0) return; walk(t.lst, a, ref k); a[k++] = t.Key; walk(t.rst, a, ref k); } private bool insert(ref Node t, T key) { if (t.Count == 0) { t = new Node(key); t.lst = t.rst = nil; t.Update(); return true; } int cmp = comparer.Compare(t.Key, key); bool res; if (cmp > 0) res = insert(ref t.lst, key); else if (cmp == 0) { if (IsMultiSet) res = insert(ref t.lst, key); else return false; } else res = insert(ref t.rst, key); balance(ref t); return res; } private bool remove(ref Node t, T key) { if (t.Count == 0) return false; int cmp = comparer.Compare(key, t.Key); bool ret; if (cmp < 0) ret = remove(ref t.lst, key); else if (cmp > 0) ret = remove(ref t.rst, key); else { ret = true; var k = t.lst.Count; if (k == 0) { t = t.rst; return true; } if (t.rst.Count == 0) { t = t.lst; return true; } t.Key = find(t.lst, k - 1); removeAt(ref t.lst, k - 1); } balance(ref t); return ret; } private void removeAt(ref Node t, int k) { int cnt = t.lst.Count; if (cnt < k) removeAt(ref t.rst, k - cnt - 1); else if (cnt > k) removeAt(ref t.lst, k); else { if (cnt == 0) { t = t.rst; return; } if (t.rst.Count == 0) { t = t.lst; return; } t.Key = find(t.lst, k - 1); removeAt(ref t.lst, k - 1); } balance(ref t); } private void balance(ref Node t) { int balance = t.lst.Height - t.rst.Height; if (balance == -2) { if (t.rst.lst.Height - t.rst.rst.Height > 0) { rotR(ref t.rst); } rotL(ref t); } else if (balance == 2) { if (t.lst.lst.Height - t.lst.rst.Height < 0) rotL(ref t.lst); rotR(ref t); } else t.Update(); } private T find(Node t, int k) { if (k < 0 || k > root.Count) throw new ArgumentOutOfRangeException(); while (true) { if (k == t.lst.Count) return t.Key; else if (k < t.lst.Count) t = t.lst; else { k -= t.lst.Count + 1; t = t.rst; } } } /// <summary> /// コレクションに含まれる要素であって、 v 以上の最小の要素の番号を返します。 /// </summary> /// <remarks>この操作は計算量 O(log N) で実行されます.</remarks> internal int LowerBound(T v) { // 追加機能 件数が0なら-1を返す if (this.Count == 0) { return -1; } // 追加機能 v 以上な要素が無い場合は-1を返す T MaxVal = this[this.Count - 1]; int cmp = comparer.Compare(MaxVal, v); if (cmp == -1) return -1; int k = 0; Node t = root; while (true) { if (t.Count == 0) return k; if (comparer.Compare(v, t.Key) <= 0) t = t.lst; else { k += t.lst.Count + 1; t = t.rst; } } } /// <summary> /// コレクションに含まれる要素であって、 v より真に大きい、最小の要素の番号を返します。 /// </summary> /// <remarks>この操作は計算量 O(log N) で実行されます.</remarks> internal int UpperBound(T v) { // 追加機能 件数が0なら-1を返す if (this.Count == 0) { return -1; } // 追加機能 v 超えな要素が無い場合は-1を返す T MaxVal = this[this.Count - 1]; int cmp = comparer.Compare(MaxVal, v); if (cmp <= 0) return -1; int k = 0; Node t = root; while (true) { if (t.Count == 0) return k; if (comparer.Compare(t.Key, v) <= 0) { k += t.lst.Count + 1; t = t.rst; } else t = t.lst; } } // 追加機能 V未満で最大の要素の番号を返す internal int Lower_Max(T v) { // 件数が0なら-1を返す if (this.Count == 0) { return -1; } // v 未満な要素が無い場合は-1を返す T MinVal = this[0]; int cmp = comparer.Compare(MinVal, v); if (cmp >= 0) return -1; // v 以上の件数を調べる int More_Or_Equal_cnt = this.Count; int UB = this.Count - 1; int LowerB = LowerBound(v); if (IsValidInd(LowerB)) { More_Or_Equal_cnt -= (UB - LowerB + 1); } return More_Or_Equal_cnt - 1; } // 追加機能 V以下で最大の要素の番号を返す internal int LowerOrEqual_Max(T v) { // 件数が0なら-1を返す if (this.Count == 0) { return -1; } // v 以下な要素が無い場合は-1を返す T MinVal = this[0]; int cmp = comparer.Compare(MinVal, v); if (cmp > 0) return -1; // v 超えの件数を調べる int More_cnt = this.Count; int UB = this.Count - 1; int UpperB = UpperBound(v); if (IsValidInd(UpperB)) { More_cnt -= (UB - UpperB + 1); } return More_cnt - 1; } // 追加機能 LowerBoundなどで返したIndが、有効範囲かを判定 internal bool IsValidInd(int pInd) { if (pInd < 0) return false; if (this.Count <= pInd) return false; return true; } // 追加機能 Vを含むかを返す internal bool Contains(T v) { int LowerB = LowerBound(v); if (IsValidInd(LowerB) == false) { return false; } int cmp = comparer.Compare(this[LowerB], v); return cmp == 0; } private void rotR(ref Node t) { Node l = t.lst; t.lst = l.rst; l.rst = t; t.Update(); l.Update(); t = l; } private void rotL(ref Node t) { Node r = t.rst; t.rst = r.lst; r.lst = t; t.Update(); r.Update(); t = r; } class Node { internal Node(T key) { Key = key; } internal int Count { get; private set; } internal int Height { get; private set; } internal T Key { get; set; } internal Node lst, rst; internal void Update() { Count = 1 + lst.Count + rst.Count; Height = 1 + Math.Max(lst.Height, rst.Height); } public override string ToString() { return string.Format("Count = {0}, Key = {1}", Count, Key); } } } #endregion