結果
| 問題 | No.2804 Fixer And Ratism |
| ユーザー |
 kakel-san
|
| 提出日時 | 2024-07-13 19:28:28 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 192 ms / 2,000 ms |
| コード長 | 9,941 bytes |
| コンパイル時間 | 17,497 ms |
| コンパイル使用メモリ | 166,880 KB |
| 実行使用メモリ | 190,848 KB |
| 最終ジャッジ日時 | 2024-07-13 19:28:52 |
| 合計ジャッジ時間 | 15,275 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 31 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (93 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();static int[] LList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => int.Parse(ReadLine())).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (n, q) = (c[0], c[1]);var que = new AvlTree<Pair>();var dic = new Dictionary<string, Pair>();var ans = new List<string>();for (var i = 0; i < q; ++i){var s = ReadLine().Split();if (s[0] == "1"){var r = int.Parse(s[2]);var p = new Pair(r, s[1]);que.Insert(p);dic[s[1]] = p;if (que.GetCount() > n){var ret = que.ElementAt(0);que.Delete(ret);ans.Add(ret.Name);}}else if (s[0] == "2"){var x = int.Parse(s[1]);n -= x;var sub = new List<Pair>();while (que.GetCount() > n){var ret = que.ElementAt(0);que.Delete(ret);sub.Add(ret);}sub.Sort((l, r) => l.Rate.CompareTo(r.Rate));ans.AddRange(sub.Select(si => si.Name));}else{var x = int.Parse(s[2]);n += x;var fixer = dic[s[1]];que.Delete(fixer);fixer.Fixed = true;que.Insert(fixer);}}WriteLine(string.Join("\n", ans));}class Pair : IComparable<Pair>{public int Rate;public string Name;public bool Fixed;public Pair(int rate, string name){Rate = rate; Name = name;}public int CompareTo(Pair b){var d = Fixed.CompareTo(b.Fixed);if (d != 0) return d;return Rate.CompareTo(b.Rate);}}public class AvlTree<T> where T: IComparable<T>{private class Node<U> where U: IComparable<U>{public U Value;public Node<U> Lc = null;public Node<U> Rc = null;public int Height;public int Count;public int CCount;public Node(int height, U value){Height = height;Count = 1;CCount = 1;Value = value;}}private Node<T> root = null;static int GetHeight(Node<T> t){return t == null ? 0 : t.Height;}static int GetCount(Node<T> t){return t == null ? 0 : t.Count;}static int GetBalance(Node<T> t){return GetHeight(t.Lc) - GetHeight(t.Rc);}static void Recalc(Node<T> t){if (t == null) return;t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc));t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc);}static Node<T> RotateLeft(Node<T> t){Node<T> u = t.Rc;Node<T> t2 = u.Lc;u.Lc = t;t.Rc = t2;Recalc(t);Recalc(u);return u;}static Node<T> RotateRight(Node<T> t){Node<T> u = t.Lc;Node<T> t2 = u.Rc;u.Rc = t;t.Lc = t2;Recalc(t);Recalc(u);return u;}static Node<T> RotateLR(Node<T> t){t.Lc = RotateLeft(t.Lc);return RotateRight(t);}static Node<T> RotateRL(Node<T> t){t.Rc = RotateRight(t.Rc);return RotateLeft(t);}static Node<T> BalanceLeft(Node<T> t){if (GetBalance(t) > 1){if (GetBalance(t.Lc) < 0) t = RotateLR(t);else t = RotateRight(t);}Recalc(t);return t;}static Node<T> BalanceRight(Node<T> t){if (GetBalance(t) < -1){if (GetBalance(t.Rc) > 0) t = RotateRL(t);else t = RotateLeft(t);}Recalc(t);return t;}/// <summary>valueを挿入する</summary>public void Insert(T value){root = Insert(root, value);}Node<T> Insert(Node<T> cur, T value){if (cur == null){return new Node<T>(1, value);}var d = value.CompareTo(cur.Value);if (d < 0){cur.Lc = Insert(cur.Lc, value);return BalanceLeft(cur);}else if (d > 0){cur.Rc = Insert(cur.Rc, value);return BalanceRight(cur);}else{++cur.CCount;Recalc(cur);return cur;}}/// <summary>valueを削除する 存在しない場合はなにもしない</summary>public void Delete(T value){root = Delete(root, value);}Node<T> Delete(Node<T> cur, T value){if (cur == null) return null;var d = value.CompareTo(cur.Value);if (d < 0){cur.Lc = Delete(cur.Lc, value);return BalanceRight(cur);}else if (d > 0){cur.Rc = Delete(cur.Rc, value);return BalanceLeft(cur);}else{--cur.CCount;if (cur.CCount == 0){if (cur.Lc != null){Node<T> del = null;var max = DeleteMax(cur.Lc, ref del);cur.Lc = max;cur.Value = del.Value;cur.CCount = del.CCount;return BalanceRight(cur);}else{return cur.Rc;}}else{Recalc(cur);return cur;}}}Node<T> DeleteMax(Node<T> t, ref Node<T> del){if (t.Rc == null){del = t;return t.Lc;}else{var max = DeleteMax(t.Rc, ref del);t.Rc = max;return BalanceLeft(t);}}/// <summary>小さいほうからpos番目の要素を取得する</summary>public T ElementAt(int pos){if (pos < 0 || pos >= GetCount(root)) return default;var t = ElementAt(root, pos);return t.Value;}/// <summary>小さいほうからpos番目の要素を取得する</summary>public T ElementAt(int pos, T defaultValue){if (pos < 0 || pos >= GetCount(root)) return defaultValue;return ElementAt(pos);}Node<T> ElementAt(Node<T> cur, int pos){if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos);if (pos < GetCount(cur.Lc) + cur.CCount) return cur;if (pos < cur.Count) return ElementAt(cur.Rc, pos - GetCount(cur.Lc) - cur.CCount);return null;}public void Debug(){if (root == null) return;Console.WriteLine($"root val:{root.Value}, CCount:{root.CCount}, Count:{root.Count}");Debug(root.Value, root.Lc);Debug(root.Value, root.Rc);}void Debug(T pval, Node<T> cur){if (cur == null) return;Console.WriteLine($"{pval} -> val:{cur.Value}, CCount:{cur.CCount}, Count:{cur.Count}");Debug(cur.Value, cur.Lc);Debug(cur.Value, cur.Rc);}/// <summary>value以上でもっとも小さい値とその場所を返却する</summary>public T LowerBound(T value, ref int index){var cur = root;T ans = default;var add = 0;index = GetCount(root);while (cur != null){if (value.CompareTo(cur.Value) <= 0){ans = cur.Value;index = add + GetCount(cur.Lc);cur = cur.Lc;}else{add += GetCount(cur.Lc) + cur.CCount;cur = cur.Rc;}}return ans;}/// <summary>要素の個数を求める</summary>public int GetCount(){return GetCount(root);}}}