#933866 (C#) No.2559 眩しい数直線

• 問題: No.2559 眩しい数直線
• ユーザー: crimsontea
• 提出日時: 2023-12-02 14:41:44
• 言語: C# (.NET 8.0.203)
• 結果: AC
• 実行時間: 59 ms / 2,000 ms
• コード長: 10,688 bytes
• コンパイル時間: 10,273 ms
• コンパイル使用メモリ: 168,116 KB
• 実行使用メモリ: 192,344 KB
• 最終ジャッジ日時: 2024-09-26 17:10:52
• 合計ジャッジ時間: 12,492 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	56 ms; 29,568 KB
testcase_01	AC	54 ms; 29,696 KB
testcase_02	AC	56 ms; 29,560 KB
testcase_03	AC	57 ms; 29,952 KB
testcase_04	AC	56 ms; 29,952 KB
testcase_05	AC	56 ms; 29,696 KB
testcase_06	AC	56 ms; 29,824 KB
testcase_07	AC	57 ms; 29,812 KB
testcase_08	AC	57 ms; 30,204 KB
testcase_09	AC	57 ms; 29,792 KB
testcase_10	AC	58 ms; 30,080 KB
testcase_11	AC	56 ms; 29,952 KB
testcase_12	AC	56 ms; 30,208 KB
testcase_13	AC	57 ms; 29,812 KB
testcase_14	AC	56 ms; 30,044 KB
testcase_15	AC	56 ms; 30,080 KB
testcase_16	AC	56 ms; 29,824 KB
testcase_17	AC	59 ms; 29,912 KB
testcase_18	AC	56 ms; 29,568 KB
testcase_19	AC	56 ms; 30,080 KB
testcase_20	AC	56 ms; 29,696 KB
testcase_21	AC	58 ms; 30,080 KB
testcase_22	AC	58 ms; 192,344 KB

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (99 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.cs(56,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(57,30): 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 A;
using static A.InputUtility;

class Program
{
    static void Main()
    {
        using Output output = new(false);

        InputNewLine();
        var (n, x) = (NextInt32, NextInt32);

        var a = new (int a, int b)[n];
        for (int i = 0; i < a.Length; i++)
        {
            InputNewLine();
            a[i] = (NextInt32 - 1, NextInt32);
        }

        int[] res = new int[x];

        foreach (var (p, b) in a)
        {
            res[p] = Math.Max(res[p], b);
        }

        for (int i = 1; i < res.Length; i++)
        {
            res[i] = Math.Max(res[i], res[i - 1] - 1);
        }

        for (int i = res.Length - 2; i >= 0; i--)
        {
            res[i] = Math.Max(res[i], res[i + 1] - 1);
        }

        Console.WriteLine(string.Join(' ', res));
    }
}

namespace A
{
    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);
    }
}