結果

問題 No.2543 Many Meetings
ユーザー crimsonteacrimsontea
提出日時 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/

ソースコード

diff #
プレゼンテーションモードにする

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 DEBUG
private static TextReader? s_textReader;
public static void SetSource(string path) => s_textReader = new StringReader(File.ReadAllText(path));
#endif
public static bool InputNewLine()
{
#if DEBUG
if (s_textReader is TextReader sr)
{
Init();
s_raw = sr.ReadLine()!;
s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
return true;
}
#endif
Init();
s_raw = Console.ReadLine()!;
s_inputs = s_raw.Split(' ', StringSplitOptions.RemoveEmptyEntries);
return true;
}
}
public readonly struct Output : IDisposable
{
private readonly StreamWriter _sw;
#if DEBUG
public Output(string path)
{
var fs = new FileStream(path, FileMode.Create, FileAccess.Write);
_sw = new StreamWriter(fs);
Console.SetOut(_sw);
}
#endif
public 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0