結果
問題 | No.2543 Many Meetings |
ユーザー | crimsontea |
提出日時 | 2023-11-24 22:49:02 |
言語 | C# (.NET 8.0.203) |
結果 |
TLE
|
実行時間 | - |
コード長 | 10,559 bytes |
コンパイル時間 | 9,878 ms |
コンパイル使用メモリ | 168,932 KB |
実行使用メモリ | 83,524 KB |
最終ジャッジ日時 | 2024-09-26 09:42:17 |
合計ジャッジ時間 | 11,817 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
34,304 KB |
testcase_01 | AC | 62 ms
38,176 KB |
testcase_02 | AC | 62 ms
31,488 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (95 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(79,28): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(80,26): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] 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.Linq;using System.Collections;using System.IO;using System.Collections.Generic;using System.Text;using System.Numerics;using System.Runtime.Intrinsics.X86;using System.Buffers;using System.Diagnostics;using System.Runtime.CompilerServices;using static InputUtility;class Program{static void Main(){using Output output = new(false);InputNewLine();var (n, k) = (NextInt32, NextInt32);var a = new (int l, int r)[n];for (int i = 0; i < a.Length; i++){InputNewLine();a[i] = (NextInt32, NextInt32);}a = a.OrderBy(x => x.r).ThenBy(x => x.l).ToArray();var times = a.Select(x => x.r - x.l).ToArray();int[] nexts = Enumerable.Repeat(-1, n).ToArray();{Queue<(int index, int right)> q = new();for (int i = 0; i < a.Length; i++){while (q.Count > 0 && q.Peek().right <= a[i].l){var (index, _) = q.Dequeue();nexts[index] = i;}q.Enqueue((i, a[i].r));}}PriorityQueue<(long time, int count, int last), long> queue = new();for (int i = 0; i < a.Length; i++){var t = times[i];queue.Enqueue((t, 1, i), t);}while (queue.Count > 0){var (time, count, cur) = queue.Dequeue();if (count == k){Console.WriteLine(time);return;}if (nexts[cur] == -1) { continue; }var next = nexts[cur];var nt = time + a[next].r - a[cur].r;queue.Enqueue((nt, count + 1, next), nt);}Console.WriteLine("-1");}}public static class InputUtility{private static string[]? s_inputs;private static string? s_raw;private static int s_index = 0;private static void Init() => s_index = 0;public static int NextInt32 => int.Parse(s_inputs![s_index++]!);public static uint NextUInt32 => uint.Parse(s_inputs![s_index++]!);public static long NextInt64 => long.Parse(s_inputs![s_index++]!);public static string NextString => s_inputs![s_index++];public static char NextChar => s_inputs![s_index++][0];public static int[] GetInt32Array() => s_inputs!.Select(int.Parse).ToArray();public static long[] GetInt64Array() => s_inputs!.Select(long.Parse).ToArray();public static string GetRawString() => s_raw!;#if DEBUGprivate static TextReader? s_textReader;public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));#endifpublic static bool InputNewLine(){#if DEBUGif (s_textReader is TextReader sr){Init();s_raw = sr.ReadLine()!;s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);return true;}#endifInit();s_raw = Console.ReadLine()!;s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);return true;}}public readonly struct Output : IDisposable{private readonly StreamWriter _sw;#if DEBUGpublic Output(string path){var fs = new FileStream(path, FileMode.Create, FileAccess.Write);_sw = new StreamWriter(fs);Console.SetOut(_sw);}#endifpublic Output(bool autoFlush){_sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = autoFlush };Console.SetOut(_sw);}public void Dispose(){_sw.Dispose();}[MethodImpl(MethodImplOptions.AggressiveInlining)]internal void Flush(){_sw.Flush();}}public static class ArrayExtensions{public static void Swap<T>(this T[] array, int i, int j) => (array[i], array[j]) = (array[j], array[i]);public static int LowerBound<T>(this T[] a, T target) where T : IComparable<T>{int ok = a.Length;int ng = -1;while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)(ok, ng) = a[mid].CompareTo(target) >= 0 ? (mid, ng) : (ok, mid);return ok;}public static int UpperBound<T>(this T[] a, T target) where T : IComparable<T>{int ok = a.Length;int ng = -1;while (Math.Abs(ok - ng) > 1 && (ok + ng) / 2 is int mid)(ok, ng) = a[mid].CompareTo(target) > 0 ? (mid, ng) : (ok, mid);return ok;}public struct IndexedEnumerable<T> : IEnumerable<(T item, int index)>{private readonly T[] _a;private readonly int _startIndex;public IndexedEnumerable(T[] a, int startIndex = 0){_a = a;_startIndex = startIndex;}public readonly IndexedEnumerator<T> GetEnumerator() => new IndexedEnumerator<T>(_a, _startIndex);IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();IEnumerator<(T item, int index)> IEnumerable<(T item, int index)>.GetEnumerator() => GetEnumerator();}public struct IndexedEnumerator<T> : IEnumerator<(T item, int index)>{public readonly (T item, int index) Current => (_a[_index], _index + _startIndex);private int _index;private int _startIndex;private T[] _a;public IndexedEnumerator(T[] a, int startIndex){_index = -1;_a = a;_startIndex = startIndex;}public bool MoveNext() => ++_index < _a.Length;readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public void Reset() => _index = -1;}/// <returns>(T value, int index)</returns>public static IndexedEnumerable<T> Enumerate<T>(this T[] arr, int startIndex = 0) => new IndexedEnumerable<T>(arr, startIndex);}public static class IEnumerableExtensions{public static IEnumerable<TSource> Log<TSource>(this IEnumerable<TSource> source){Console.WriteLine(string.Join(' ', source));return source;}public static ScanEnumerable<TSource, TAccumulate> Scan<TSource, TAccumulate>(this IEnumerable<TSource> source,TAccumulate seed,Func<TAccumulate, TSource, TAccumulate> accumulator) where TSource : struct where TAccumulate : struct{return new ScanEnumerable<TSource, TAccumulate>(source, accumulator, seed);}public static IEnumerable<TAccumulate> ScanExSeed<TSource, TAccumulate>(this IEnumerable<TSource> source,TAccumulate seed,Func<TAccumulate, TSource, TAccumulate> accumulator){var accumulation = new List<TAccumulate>();var current = seed;foreach (var item in source){current = accumulator(current, item);accumulation.Add(current);}return accumulation;}public readonly struct ScanEnumerable<TSource, TAccumulate> : IEnumerable<TAccumulate> where TSource : struct where TAccumulate : struct{private readonly IEnumerable<TSource> _source;private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;private readonly TAccumulate _seed;public ScanEnumerable(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed){_source = source;_accumulator = accumulator;_seed = seed;}public readonly ScanEnumerator<TSource, TAccumulate> GetEnumerator() => new(_source, _accumulator, _seed);readonly IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();readonly IEnumerator<TAccumulate> IEnumerable<TAccumulate>.GetEnumerator() => GetEnumerator();}public struct ScanEnumerator<TSource, TAccumulate> : IEnumerator<TAccumulate> where TSource : struct where TAccumulate : struct{private readonly Func<TAccumulate, TSource, TAccumulate> _accumulator;private readonly IEnumerator<TSource> _enumerator;private TAccumulate _current;private bool _secondOrLaterElement = false;public ScanEnumerator(IEnumerable<TSource> source, Func<TAccumulate, TSource, TAccumulate> accumulator, TAccumulate seed){_enumerator = source.GetEnumerator();_accumulator = accumulator;_current = seed;}public readonly TAccumulate Current => _current;readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public bool MoveNext(){if (_secondOrLaterElement){if (_enumerator.MoveNext()){_current = _accumulator(_current, _enumerator.Current);return true;}return false;}else{_secondOrLaterElement = true;return true;}}public void Reset(){throw new NotSupportedException();}}public static IEnumerable<TSource> Scan<TSource>(this IEnumerable<TSource> source,Func<TSource, TSource, TSource> accumulator){if (source is null)throw new ArgumentNullException(paramName: nameof(source));if (accumulator is null)throw new ArgumentNullException(paramName: nameof(accumulator));var accumulation = new List<TSource>();if (source.Any() is false){return accumulation;}var current = source.First();accumulation.Add(current);foreach (var item in source.Skip(1)){current = accumulator(current, item);accumulation.Add(current);}return accumulation;}}public class MyMath{public static long Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(1L, (acc, x) => acc * x);public static long Pow10(int y) => Pow(10, y);public static long Pow2(int y) => Pow(2, y);}public class MyMathBigInteger{public static BigInteger Pow(long x, int y) => Enumerable.Repeat(x, y).Aggregate(new BigInteger(1), (acc, x) => acc * x);public static BigInteger Pow10(int y) => Pow(10, y);public static BigInteger Pow2(int y) => Pow(2, y);}