結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2018-02-09 23:13:13 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 713 ms / 3,000 ms |
コード長 | 14,153 bytes |
コンパイル時間 | 2,242 ms |
コンパイル使用メモリ | 116,608 KB |
実行使用メモリ | 34,048 KB |
最終ジャッジ日時 | 2024-10-08 22:20:13 |
合計ジャッジ時間 | 14,308 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.Diagnostics;using System.IO;using System.Linq;using System.Numerics;using System.Text;using static System.Convert;using static System.Math;using static Constants;using static Extensions;using static MathExtensions;public static class Program{public static void Solve(){var (q, k) = (I, I);var v = new List<long>(q);var t = Repeat(q, () =>{var x = I;if (x == 1) v.Add(L);return x;}).ToArray();var vc = new CoordinateCompressor<long>(v);var ft = new FenwickTree<int, SumGroup_Int32>(v.Count);var vi = 0;Repeat(q, i =>{if (t[i] == 1){ft[vc.Compress(v[vi++])]++;}else if (t[i] == 2){var l = BinarySearch.LowerBound(j => ft.Concat(j), 0, v.Count - 1, k);if (l > v.Count - 1) Console.WriteLine(-1);else{Console.WriteLine(vc.Decompress(l));ft[l]--;}}});}#region Scannersstatic TextScanner _ts;static char C => char.Parse(_ts.Next());static string S => _ts.Next();static int I => int.Parse(_ts.Next());static long L => long.Parse(_ts.Next());static BigInteger B => BigInteger.Parse(_ts.Next());static double D => double.Parse(_ts.Next());static decimal M => decimal.Parse(_ts.Next());#endregionpublic static void Main(){var sw = new StreamWriter(Console.OpenStandardOutput());sw.NewLine = "\n";#if DEBUGsw.AutoFlush = true;#elsesw.AutoFlush = false;#endifConsole.SetOut(sw);_ts = new TextScanner(Console.In);Solve();Console.Out.Flush();}}public static partial class Extensions{}#region Librarypublic class CoordinateCompressor<T> where T : IComparable<T>, IEquatable<T>{private readonly Dictionary<T, int> _compress;private readonly T[] _decompress;public CoordinateCompressor(IEnumerable<T> coordinates){var arr = coordinates.ToArray();Array.Sort(arr);_compress = new Dictionary<T, int>(arr.Length);_decompress = arr;var pi = default(int);var pa = default(T);if (arr.Any()) _compress.Add(arr[0], 0);for (var i = 0; i < arr.Length; i++)if (i > 0 && !arr[i].Equals(pa)) _compress[pa = arr[i]] = pi = i;}public int Compress(T coordinate) => _compress[coordinate];public T Decompress(int index) => _decompress[index];}public interface IMonoid<T>{T Unit { get; }T Append(T left, T right);}public interface IGroup<T> : IMonoid<T>{T Invert(T value);}public struct SumGroup_Int32 : IGroup<int>{public int Unit => 0;public int Append(int left, int right) => left + right;public int Invert(int value) => -value;}public class FenwickTreeOnMonoid<T, TMonoid>where TMonoid : struct, IMonoid<T> // commutative{[DebuggerBrowsable(DebuggerBrowsableState.Never)]private static readonly TMonoid _monoid = default(TMonoid);protected readonly T[] _tree;public FenwickTreeOnMonoid(int length){_tree = Enumerable.Repeat(_monoid.Unit, length + 1).ToArray();}public FenwickTreeOnMonoid(IReadOnlyList<T> collection){var count = collection.Count;_tree = new T[count + 1];for (var i = 0; i < count; i++) _tree[i + 1] = collection[i];for (var i = 1; i < count; i++){var j = i + (i & -i);if (j < count + 1) _tree[j] = _monoid.Append(_tree[j], _tree[i]);}}public int Length => _tree.Length - 1;public T Concat(int r){var acc = _monoid.Unit;for (r++; r > 0; r -= r & -r) acc = _monoid.Append(acc, _tree[r]);return acc;}public void Append(int i, T value){for (i++; i <= this.Length; i += i & -i) _tree[i] = _monoid.Append(_tree[i], value);}}public class FenwickTree<T, TGroup> : FenwickTreeOnMonoid<T, TGroup>where TGroup : struct, IGroup<T> // commutative{[DebuggerBrowsable(DebuggerBrowsableState.Never)]private static readonly TGroup _group = default(TGroup);public FenwickTree(int length) : base(length) { }public FenwickTree(IReadOnlyList<T> collection) : base(collection) { }public T this[int i]{get { return this[i, i]; }set { this.Append(i, _group.Append(value, _group.Invert(this[i]))); }}public T this[int l, int r]{get{var acc = _group.Unit;r++;for (; r > l; r -= r & -r) acc = _group.Append(acc, _tree[r]);for (; l > r; l -= l & -l) acc = _group.Append(acc, _group.Invert(_tree[l]));return acc;}}// for debug[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]internal IEnumerable<T> Values{get { for (var i = 0; i < this.Length; i++) yield return this[i]; }}}public static class BinarySearch{public static int LowerBound<T>(this IReadOnlyList<T> source, T value)where T : IComparable<T>=> source.LowerBound(value, Comparer<T>.Default);public static int LowerBound<T>(this IReadOnlyList<T> source, T value, IComparer<T> comparer)=> LowerBound(i => source[i], 0, source.Count - 1, value, comparer);public static int LowerBound<T>(Func<int, T> func, int minValue, int maxValue, T value)where T : IComparable<T>=> LowerBound(func, minValue, maxValue, value, Comparer<T>.Default);public static int LowerBound<T>(Func<int, T> func, int minValue, int maxValue, T value, IComparer<T> comparer){var i = Search(x => comparer.Compare(func(x), value) >= 0, minValue, maxValue);return comparer.Compare(func(i), value) < 0 ? i + 1 : i;}public static int UpperBound<T>(this IReadOnlyList<T> source, T value)where T : IComparable<T>=> source.UpperBound(value, Comparer<T>.Default);public static int UpperBound<T>(Func<int, T> func, int minValue, int maxValue, T value)where T : IComparable<T>=> UpperBound(func, minValue, maxValue, value, Comparer<T>.Default);public static int UpperBound<T>(this IReadOnlyList<T> source, T value, IComparer<T> comparer)=> UpperBound(i => source[i], 0, source.Count - 1, value, comparer);public static int UpperBound<T>(Func<int, T> func, int minValue, int maxValue, T value, IComparer<T> comparer){var i = Search(x => comparer.Compare(func(x), value) > 0, minValue, maxValue);return comparer.Compare(func(i), value) <= 0 ? i + 1 : i;}public static int Search(Predicate<int> predicate, int minValue, int maxValue){var ok = maxValue;var ng = minValue - 1;while (System.Math.Abs(ok - ng) > 1){var mid = (ok + ng) / 2;if (predicate(mid)) ok = mid;else ng = mid;}return ok;}}public class TextScanner{private readonly TextReader _tr;public TextScanner(TextReader tr){_tr = tr;}public string Next(){var sb = new StringBuilder();int i;do{i = _tr.Read();if (i == -1) throw new EndOfStreamException();}while (char.IsWhiteSpace((char)i));while (i != -1 && !char.IsWhiteSpace((char)i)){sb.Append((char)i);i = _tr.Read();}return sb.ToString();}}public static class Constants{public const int AnswerToLifeTheUniverseAndEverything = 42;public const string Yes = nameof(Yes);public const string No = nameof(No);public const string YES = nameof(YES);public const string NO = nameof(NO);public const string Possible = nameof(Possible);public const string Impossible = nameof(Impossible);}[DebuggerStepThrough]public static partial class Extensions{public static void Answer(string str){Console.WriteLine(str);Exit(0);}public static void Answer(object obj) => Answer(obj.ToString());public static void Assert(bool condition){if (!condition) throw new Exception("Assertion failed");}public static string AsString(this IEnumerable<char> source) => new string(source.ToArray());public static Dictionary<T, int> Bucket<T>(this IEnumerable<T> source) where T : IEquatable<T>{var dict = new Dictionary<T, int>();foreach (var item in source) if (dict.ContainsKey(item)) dict[item]++; else dict[item] = 1;return dict;}public static int[] Bucket<T>(this IEnumerable<T> source, int maxValue, Func<T, int> selector){var arr = new int[maxValue + 1];foreach (var item in source) arr[selector(item)]++;return arr;}public static IEnumerable<int> CumSum(this IEnumerable<int> source){var sum = 0;foreach (var item in source) yield return sum += item;}public static IEnumerable<long> CumSum(this IEnumerable<long> source){var sum = 0L;foreach (var item in source) yield return sum += item;}public static void Exit(int exitCode){Console.Out.Flush();Environment.Exit(exitCode);}public static void ForEach<T>(this IEnumerable<T> source, Action<T> action){foreach (var item in source) action(item);}public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, _> func){foreach (var item in source) func(item);}public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action){var i = 0;foreach (var item in source) action(item, i++);}public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, int, _> func){var i = 0;foreach (var item in source) func(item, i++);}public static void Repeat(int count, Action action){for (var i = 0; i < count; i++) action();}public static void Repeat(int count, Action<int> action){for (var i = 0; i < count; i++) action(i);}public static IEnumerable<T> Repeat<T>(int count, Func<T> func){for (var i = 0; i < count; i++) yield return func();}public static IEnumerable<T> Repeat<T>(int count, Func<int, T> func){for (var i = 0; i < count; i++) yield return func(i);}public static void Swap<T>(ref T x, ref T y){var tmp = x; x = y; y = tmp;}public static (T1[], T2[]) Unzip<T1, T2>(this ICollection<(T1, T2)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var i = 0;foreach (var (t1, t2) in source) { ts1[i] = t1; ts2[i] = t2; i++; }return (ts1, ts2);}public static (T1[], T2[], T3[]) Unzip<T1, T2, T3>(this ICollection<(T1, T2, T3)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var ts3 = new T3[source.Count];var i = 0;foreach (var (t1, t2, t3) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; i++; }return (ts1, ts2, ts3);}public static (T1[], T2[], T3[], T4[]) Unzip<T1, T2, T3, T4>(this ICollection<(T1, T2, T3, T4)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var ts3 = new T3[source.Count];var ts4 = new T4[source.Count];var i = 0;foreach (var (t1, t2, t3, t4) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; ts4[i] = t4; i++; }return (ts1, ts2, ts3, ts4);}}[DebuggerStepThrough]public static class MathExtensions{public static int DivCeil(int left, int right)=> left / right + (left % right == 0 ? 0 : 1);public static long DivCeil(long left, long right)=> left / right + (left % right == 0L ? 0L : 1L);public static int Gcd(int left, int right){int r;while ((r = left % right) != 0) { left = right; right = r; }return right;}public static long Gcd(long left, long right){long r;while ((r = left % right) != 0L) { left = right; right = r; }return right;}public static BigInteger Gcd(BigInteger left, BigInteger right)=> BigInteger.GreatestCommonDivisor(left, right);public static int HighestOneBit(int x){x |= x >> 01;x |= x >> 02;x |= x >> 04;x |= x >> 08;x |= x >> 16;return x - (x >> 1);}public static long HighestOneBit(long x){x |= x >> 01;x |= x >> 02;x |= x >> 04;x |= x >> 08;x |= x >> 16;x |= x >> 32;return x - (x >> 1);}public static int Lcm(int left, int right) => left / Gcd(left, right) * right;public static long Lcm(long left, long right) => left / Gcd(left, right) * right;public static BigInteger Lcm(BigInteger left, BigInteger right)=> left / Gcd(left, right) * right;public static int Pow(int value, int exponent){var r = 1;while (exponent > 0){if ((exponent & 1) == 1) r *= value;value *= value;exponent >>= 1;}return r;}public static long Pow(long value, int exponent){var r = 1L;while (exponent > 0){if ((exponent & 1) == 1) r *= value;value *= value;exponent >>= 1;}return r;}public static long Fact(int value){var r = 1L;for (var i = 2; i <= value; i++) r *= i;return r;}}#endregion