結果
| 問題 | No.2650 [Cherry 6th Tune *] セイジャク |
| ユーザー |
 crimsontea
|
| 提出日時 | 2024-02-23 22:08:47 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,350 ms / 2,500 ms |
| コード長 | 25,562 bytes |
| コンパイル時間 | 7,349 ms |
| コンパイル使用メモリ | 170,412 KB |
| 実行使用メモリ | 217,992 KB |
| 最終ジャッジ日時 | 2024-09-29 06:51:11 |
| 合計ジャッジ時間 | 26,007 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (80 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(343,32): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(344,30): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(118,39): 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 A;using AtCoder.Extension;using System;using System.Buffers;using System.Collections;using System.Collections.Generic;using System.Diagnostics;using System.Numerics;using System.Runtime.CompilerServices;using static A.InputUtility;class Program{static void Main(){using Output output = new(false);InputNewLine();var (n, a) = (NextInt32, NextInt32);InputNewLine();var x = GetInt32Array();InputNewLine();var t = NextInt32;var query = new (int l, int r)[t];for (int i = 0; i < query.Length; i++){InputNewLine();query[i] = (NextInt32, NextInt32);}SortedMultiset<Data> set = new();for (int i = 0; i < x.Length; i++){set.Add(new Data(x[i], i));}int[] res = Enumerable.Repeat(-1, n).ToArray();for (int i = query.Length - 1; i >= 0; i--){var (l, r) = query[i];var first = set.IndexOf(new Data(l, 0));var last = set.LastIndexOf(new Data(r, 0));if(first == last){continue;}List<Data> list = new();for (int k = first; k < last; k++){var (p, index) = set[k];res[index] = i + 1;list.Add(new Data(p, index));}foreach (var item in list){set.Discard(item);}}Console.WriteLine(string.Join('\n', res));}public record struct Data(int X, int Index) : IComparable<Data>{int IComparable<Data>.CompareTo(Data other) => X.CompareTo(other.X);}}public class SortedMultiset<T> where T : struct, IComparable<T>{private const int BUCKET_RATIO = 16;private const int SPLIT_RATIO = 24;private List<List<T>> _a;private int _size;public SortedMultiset(){_a = new List<List<T>>(0);}public SortedMultiset(IEnumerable<T> enumerable){// Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)var a = enumerable.ToArray();_size = a.Length;for (int i = 1; i < a.Length; i++){if (a[i - 1].CompareTo(a[i]) > 0){Array.Sort(a);break;}}int bucketSize = (int)Math.Ceiling(Math.Sqrt(_size / (double)BUCKET_RATIO));_a = a.Chunk(bucketSize).Select(x => x.ToList()).ToList();}public IEnumerable<T> AsEnumerable(){foreach (var i in _a)foreach (var j in i) yield return j;}public IEnumerable<T> AsReversedEnumerable(){foreach (IEnumerable<T> i in ((IEnumerable<List<T>>)_a).Reverse())foreach (var j in i.Reverse()) yield return j;}public override bool Equals(object? obj){if (obj is SortedMultiset<T> set){return AsEnumerable().SequenceEqual(set.AsEnumerable());}return false;}public override int GetHashCode(){return HashCode.Combine(AsEnumerable());}public int Count => _size;public override string ToString(){return string.Join(", ", AsEnumerable());}private (List<T>, int, int) Position(T x){// return the bucket, index of the bucket and position in which x should be. this must not be empty.for (int i = 0; i < _a.Count; i++){var bucket = _a[i];if (x.CompareTo(bucket[bucket.Count - 1]) <= 0){return (bucket, i, bucket.BinarySearch(x));}}return (_a[^1], _a.Count - 1, _a[^1].Count);}public bool Contains(T x){if (_size == 0) return false;var (_, _, index) = Position(x);return index >= 0;}public int CountOf(T x){// Count the number of x.return LastIndexOf(x) - IndexOf(x);}public void Add(T x){// Add an element. / O(√N)if (_size == 0){_a = new List<List<T>>() { new() { x } };_size = 1;return;}var (bucket, bucketIndex, index) = Position(x);if (index < 0) index = ~index;bucket.Insert(index, x);_size++;if (bucket.Count > _a.Count * SPLIT_RATIO){int mid = bucket.Count / 2;_a[bucketIndex] = bucket.GetRange(0, mid);_a.Insert(bucketIndex + 1, bucket.GetRange(mid, bucket.Count - mid));}}private T Pop(List<T> bucket, int bucketIndex, int index){var ans = bucket[index];bucket.RemoveAt(index);_size--;if (bucket.Count == 0) _a.RemoveAt(bucketIndex);return ans;}public bool Discard(T x){// Remove an element and return True if removed. / O(√N)if (_size == 0) return false;var (bucket, bucketIndex, index) = Position(x);if (index < 0) return false;Pop(bucket, bucketIndex, index);return true;}public T Lt(T x){// Find the largest element < x, or default(T) if it doesn't exist.foreach (var bucket in ((IEnumerable<List<T>>)_a).Reverse()){if (bucket[0].CompareTo(x) < 0){return bucket[bucket.BinarySearch(x) - 1];}}return default;}public T Le(T x){// Find the largest element <= x, or default(T) if it doesn't exist.foreach (var bucket in ((IEnumerable<List<T>>)_a).Reverse()){if (bucket[0].CompareTo(x) <= 0){var index = bucket.BinarySearch(x);if (index < 0) index = ~index;return bucket[index - 1];}}return default;}public T Gt(T x){// Find the smallest element > x, or default(T) if it doesn't exist.foreach (var bucket in _a){if (bucket[bucket.Count - 1].CompareTo(x) > 0){var index = bucket.BinarySearch(x);if (index < 0) index = ~index;return bucket[index];}}return default;}public T Ge(T x){// Find the smallest element >= x, or default(T) if it doesn't exist.foreach (var bucket in _a){if (bucket[bucket.Count - 1].CompareTo(x) >= 0){var index = bucket.BinarySearch(x);if (index < 0) index = ~index;return bucket[index];}}return default;}public T this[int i]{// Return the i-th element.get{if (i < 0)throw new IndexOutOfRangeException();foreach (var bucket in _a){if (i < bucket.Count) return bucket[i];i -= bucket.Count;}throw new IndexOutOfRangeException();}}public T Pop(int i){// Pop and return the i-th element.if (i < 0)throw new IndexOutOfRangeException();for (int b = 0; b < _a.Count; b++){var bucket = _a[b];if (i < bucket.Count) return Pop(bucket, b, i);i -= bucket.Count;}throw new IndexOutOfRangeException();}public T Pop() => Pop(_size - 1);public T Pop(Index index) => Pop(index.GetOffset(_size));public int IndexOf(T x){// Count the number of elements < x.int ans = 0;foreach (var bucket in _a){if (bucket[^1].CompareTo(x) >= 0){var index = bucket.LowerBound(x);//if (index < 0) index = ~index;return ans + index;}ans += bucket.Count;}return ans;}public int LastIndexOf(T x){// Count the number of elements <= x.int ans = 0;foreach (var bucket in _a){if (bucket[^1].CompareTo(x) > 0){var index = bucket.UpperBound(x);//if (index < 0) index = ~index;return ans + index;}ans += bucket.Count;}return ans;}}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 ulong NextUInt64 => ulong.Parse(s_inputs![s_index++]!);public static string NextString => s_inputs![s_index++];public static char NextChar => s_inputs![s_index++][0];public static decimal NextDecimal => decimal.Parse(s_inputs![s_index++]!);public static BigInteger NextBigInteger => BigInteger.Parse(s_inputs![s_index++]!);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 static class CombinationFunction{public static void PartedRotate<T>(T[] a, int first1, int last1, int first2, int last2){if (first1 == last1 || first2 == last2) return;int next = first2;while (first1 != next){Swap(a, first1++, next++);if (first1 == last1) first1 = first2;if (next == last2){next = first2;}else if (first1 == first2){first2 = next;}}}public static bool NextCombinationImp<T>(T[] a, int first1, int last1, int first2, int last2) where T : IComparable<T>{if (first1 == last1 || first2 == last2) return false;int target = last1 - 1;int lastElem = last2 - 1;while (target != first1 && !(a[target].CompareTo(a[lastElem]) < 0)) target--;if (target == first1 && !(a[target].CompareTo(a[lastElem]) < 0)){PartedRotate(a, first1, last1, first2, last2);return false;}int next = first2;while (!(a[target].CompareTo(a[next]) < 0)) next++;Swap(a, target++, next++);PartedRotate(a, target, last1, next, last2);return true;}public static bool NextCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>=> NextCombinationImp(a, first, mid, mid, last);public static bool PrevCombination<T>(T[] a, int first, int mid, int last) where T : IComparable<T>=> NextCombinationImp(a, mid, last, first, mid);public static void Swap<T>(T[] a, int i, int j) => (a[i], a[j]) = (a[j], a[i]);}public static class PermutationFunction{public static bool NextPermutation<T>(T[] a) where T : IComparable<T>{int n = a.Length;int i = n - 2;while (i >= 0 && a[i].CompareTo(a[i + 1]) >= 0) { i--; }if (i < 0) { return false; }int j = n - 1;while (a[j].CompareTo(a[i]) <= 0) { j--; }(a[i], a[j]) = (a[j], a[i]);Array.Reverse(a, i + 1, n - i - 1);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 static CombinationEnumerable<T> Combination<T>(this T[] a, int k) where T : IComparable<T>=> new(a, k);public readonly struct CombinationEnumerable<T> where T : IComparable<T>{private readonly T[] _a;private readonly int _k;public CombinationEnumerable(T[] a, int k){_a = a;_k = k;}public readonly CombinationEnumerator<T> GetEnumerator() => new(_a, _k);}public struct CombinationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>{private readonly int _k;private readonly T[] _a;private readonly int _n;private bool _secondOrLaterElement = false;public CombinationEnumerator(T[] a, int k){_a = a;_n = a.Length;_k = k;}public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[.._k];readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public bool MoveNext(){if (_secondOrLaterElement){return CombinationFunction.NextCombination(_a, 0, _k, _n);}else{_secondOrLaterElement = true;return true;}}public void Reset(){throw new NotSupportedException();}}public static PermutationEnumerable<T> Permutation<T>(this T[] a) where T : IComparable<T> => new(a);public readonly struct PermutationEnumerable<T> where T : IComparable<T>{private readonly T[] _a;public PermutationEnumerable(T[] a) => _a = a;public readonly PermutationEnumerator<T> GetEnumerator() => new(_a);}public struct PermutationEnumerator<T> : IEnumerator<ReadOnlyMemory<T>> where T : IComparable<T>{private readonly T[] _a;private readonly int _n;private bool _secondOrLaterElement = false;public PermutationEnumerator(T[] a){_a = a;_n = a.Length;}public readonly ReadOnlyMemory<T> Current => _a.AsMemory()[..];readonly object IEnumerator.Current => Current;public readonly void Dispose() { }public bool MoveNext(){if (_secondOrLaterElement){return PermutationFunction.NextPermutation(_a);}else{_secondOrLaterElement = true;return true;}}public void Reset() => throw new NotSupportedException();}}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);}}#region Expanded by https://github.com/kzrnm/SourceExpandernamespace AtCoder.Extension{public static class BinarySearchListExtension{[MethodImpl(256)]public static int LowerBound<T,TOp>(this IList<T>a,T v,TOpcmp)where TOp:IComparer<T> =>LowerBound(a,new CmpWrapper<T,TOp>(v,cmp));[MethodImpl(256)]public static int LowerBound<T,TCv>(this IList<T>a,TCv v)where TCv:IComparable<T> =>BinarySearch<T,TCv,L>(a,v);[MethodImpl(256)]public static int UpperBound<T,TOp>(this IList<T>a,T v,TOp cmp)where TOp:IComparer<T> =>UpperBound(a,new CmpWrapper<T,TOp>(v,cmp));[MethodImpl(256)]public static int UpperBound<T,TCv>(this IList<T>a,TCv v)where TCv:IComparable<T> =>BinarySearch<T,TCv,U>(a,v);private readonly struct CmpWrapper<T,TCmp>:IComparable<T>where TCmp:IComparer<T>{readonly T v;readonly TCmp cmp;public CmpWrapper(T v,TCmp cmp){this.v=v;this.cmp=cmp;}[MethodImpl(256)]public int CompareTo(T other)=>cmp.Compare(v,other);}private interface IOk{bool Ok(int c);}private struct L:IOk{[MethodImpl(256)]public bool Ok(int c)=>c<=0;}private struct U:IOk{[MethodImpl(256)]public bool Ok(int c)=>c<0;}[MethodImpl(256)]private static int BinarySearch<T,TCv,TOk>(this IList<T>a,TCv v)where TCv:IComparable<T>where TOk:IOk{int ok=a.Count;int ng=-1;while(ok-ng>1){var m=(ok+ng)>>1;var c=v.CompareTo(a[m]);if(default(TOk).Ok(c))ok=m;else ng=m;}return ok;}}}namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}#endregion Expanded by https://github.com/kzrnm/SourceExpander