結果
問題 | No.649 ここでちょっとQK! |
ユーザー | selpoAC |
提出日時 | 2019-01-25 19:30:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,018 ms / 3,000 ms |
コード長 | 4,539 bytes |
コンパイル時間 | 2,063 ms |
コンパイル使用メモリ | 68,588 KB |
実行使用メモリ | 48,532 KB |
最終ジャッジ日時 | 2023-10-14 09:52:40 |
合計ジャッジ時間 | 30,872 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
23,776 KB |
testcase_01 | AC | 69 ms
23,980 KB |
testcase_02 | AC | 72 ms
24,096 KB |
testcase_03 | AC | 211 ms
26,076 KB |
testcase_04 | AC | 958 ms
48,532 KB |
testcase_05 | AC | 953 ms
46,516 KB |
testcase_06 | AC | 955 ms
46,560 KB |
testcase_07 | AC | 70 ms
23,832 KB |
testcase_08 | AC | 71 ms
23,872 KB |
testcase_09 | AC | 72 ms
25,816 KB |
testcase_10 | AC | 71 ms
21,804 KB |
testcase_11 | AC | 72 ms
23,828 KB |
testcase_12 | AC | 852 ms
35,312 KB |
testcase_13 | AC | 845 ms
35,412 KB |
testcase_14 | AC | 834 ms
37,308 KB |
testcase_15 | AC | 875 ms
37,864 KB |
testcase_16 | AC | 878 ms
35,904 KB |
testcase_17 | AC | 968 ms
38,808 KB |
testcase_18 | AC | 1,085 ms
39,772 KB |
testcase_19 | AC | 1,194 ms
40,836 KB |
testcase_20 | AC | 1,302 ms
43,952 KB |
testcase_21 | AC | 1,408 ms
40,568 KB |
testcase_22 | AC | 1,507 ms
43,388 KB |
testcase_23 | AC | 1,606 ms
44,124 KB |
testcase_24 | AC | 1,738 ms
43,052 KB |
testcase_25 | AC | 1,876 ms
44,012 KB |
testcase_26 | AC | 2,018 ms
45,684 KB |
testcase_27 | AC | 74 ms
24,112 KB |
testcase_28 | AC | 75 ms
23,832 KB |
testcase_29 | AC | 75 ms
23,800 KB |
testcase_30 | AC | 841 ms
33,620 KB |
testcase_31 | AC | 859 ms
36,336 KB |
testcase_32 | AC | 71 ms
23,788 KB |
testcase_33 | AC | 70 ms
23,792 KB |
testcase_34 | AC | 70 ms
23,760 KB |
testcase_35 | AC | 68 ms
24,192 KB |
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Threading.Tasks; using static System.Console; using static System.Math; class Z { static void Main() => new K(); } class K { int F => int.Parse(Str); long FL => long.Parse(Str); int[] G => Strs.Select(int.Parse).ToArray(); long[] GL => Strs.Select(long.Parse).ToArray(); string Str => ReadLine(); string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries); const int MOD = 1000000007; public K() { SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false }); Solve(); Out.Flush(); } void Solve() { /*var hoge = new List<int>(); for (var i = 0; i < 20; i++) hoge.Add(Treap<int>.rand.Next(100)); var tr = new Treap<int>(); foreach (var x in hoge) tr.Insert(x); WriteLine("hoge = " + string.Join(", ", hoge)); WriteLine("tr = " + string.Join(", ", tr)); hoge.Sort(); WriteLine("hoge = " + string.Join(", ", hoge)); WriteLine(tr); var a = hoge[Treap<int>.rand.Next(20)]; tr.Remove(a); WriteLine($"removed {a}"); WriteLine(tr);*/ var I = G; int Q = I[0], K = I[1]; var tr = new Treap<long>(); while (Q-- > 0) { var I2 = GL; if (I2[0] == 1) tr.Insert(I2[1]); else { var x = tr.At(K - 1); WriteLine(x == null ? -1 : x.Value); if (x != null) tr.Remove(x.Value); } } } } class Treap<T> : IEnumerable<T> where T : IComparable<T> { public static Random rand = new Random(471289567); public class Node : IEnumerable<T> { public static int GetSize(Node n) => n?.Size ?? 0; public int Size { get; private set; } public T Value; public readonly double Priority; public Node[] Children = new Node[2]; public Node(T v) { Priority = rand.NextDouble(); Value = v; Update(); } public Node(T v, double p, params Node[] ch) { Value = v; Priority = p; ch.CopyTo(Children, 0); Update(); } public Node Update() { Size = 1 + Children.Sum(GetSize); return this; } public IEnumerator<T> GetEnumerator() { if (Children[0] != null) foreach (var x in Children[0]) yield return x; yield return Value; if (Children[1] != null) foreach (var x in Children[1]) yield return x; } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); string Label => $"{Value}({Priority:f2})"; public override string ToString() { var sb = new StringBuilder(); ToString(sb); return sb.ToString(); } void ToString(StringBuilder sb) { sb.AppendLine(Label); for (var i = 0; i < 2; i++) if (Children[i] != null) { sb.AppendLine($"{Label} {Children[i].Label}"); Children[i].ToString(sb); } } } Node root; public void Insert(T val) { root = Insert(root, new Node(val)); } public bool Remove(T val) { var x = Find(root, val); if (x != null) root = Remove(root, x); return x != null; } public Node At(int i) { var r = root; while (r != null) { var l = Node.GetSize(r.Children[0]); if (l == i) return r; if (l < i) { i -= l + 1; r = r.Children[1]; } else r = r.Children[0]; } return null; } // r と r[id] の位置関係を変える Node Rotate(Node r, int id) { var c = r.Children[id]; r.Children[id] = c.Children[1 - id]; c.Children[1 - id] = r; c.Update(); r.Update(); return c; } Node Insert(Node r, Node v) { if (r == null) return v; var id = r.Value.CompareTo(v.Value) > 0 ? 0 : 1; r.Children[id] = Insert(r.Children[id], v).Update(); if (r.Priority < r.Children[id].Priority) r = Rotate(r, id); return r.Update(); } Node Find(Node r, T val) { if (r == null) return null; var c = r.Value.CompareTo(val); if (c == 0) return r; return Find(r.Children[c > 0 ? 0 : 1], val); } Node Remove(Node r, Node v) { if (r == null) return root; if (r == v) { if (v.Children.All(c => c == null)) return null; var id = v.Children[0] != null && (v.Children[1] == null || v.Children[0].Priority >= v.Children[1].Priority) ? 0 : 1; var s = Rotate(v, id); s.Children[1 - id] = Remove(v, v); return s.Update(); } else { var id = r.Value.CompareTo(v.Value) > 0 ? 0 : 1; r.Children[id] = Remove(r.Children[id], v); return r.Update(); } } Node Merge(Node l, Node r) { var p = new Node(default(T), 100, l, r); return Remove(p, p); } public IEnumerator<T> GetEnumerator() => root.GetEnumerator(); IEnumerator IEnumerable.GetEnumerator() => root.GetEnumerator(); public override string ToString() => root.ToString(); }