結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:40:46 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 23,596 bytes |
コンパイル時間 | 1,323 ms |
コンパイル使用メモリ | 120,960 KB |
実行使用メモリ | 37,888 KB |
最終ジャッジ日時 | 2024-11-30 01:38:29 |
合計ジャッジ時間 | 5,638 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
コンパイルメッセージ
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.Generic;using System.IO;using System.Linq;using System.Text;using System.Runtime.CompilerServices;using System.Runtime.InteropServices;using YukicoderContest257.Extensions;using YukicoderContest257.Numerics;using YukicoderContest257.Questions;namespace YukicoderContest257.Questions{public class QuestionC : AtCoderQuestionBase{public override IEnumerable<object> Solve(TextReader inputStream){var n = inputStream.ReadInt();var a = new Queue<int>(inputStream.ReadIntArray().Select(i => i - 1));var b = inputStream.ReadIntArray().Select(i => i - 1).ToArray();var bit = new BinaryIndexedTree(n);var indexOfB = new int[n];for (int i = 0; i < b.Length; i++){indexOfB[b[i]] = i;}long count = 0;foreach (var ai in a){var index = indexOfB[ai];count += bit.Sum((index + 1)..);bit[index]++;}yield return count;}public class BinaryIndexedTree{long[] _data;public int Length { get; }public BinaryIndexedTree(int length){_data = new long[length + 1]; // 内部的には1-indexedにするLength = length;}public BinaryIndexedTree(IEnumerable<long> data, int length) : this(length){var count = 0;foreach (var n in data){AddAt(count++, n);}}public BinaryIndexedTree(ICollection<long> collection) : this(collection, collection.Count) { }public long this[Index index]{get => Sum(index..(index.GetOffset(Length) + 1));set{if (value < 0){throw new ArgumentOutOfRangeException(nameof(value), $"{nameof(value)}は0以上の値である必要があります。");}AddAt(index, value - this[index]);}}/// <summary>/// BITの<c>index</c>番目の要素に<c>n</c>を加算します。/// </summary>/// <param name="index">加算するインデックス(0-indexed)</param>/// <param name="value">加算する数</param>public void AddAt(Index index, long value){var i = index.GetOffset(Length);unchecked{if ((uint)i >= (uint)Length){throw new ArgumentOutOfRangeException(nameof(index));}}i++; // 1-indexedにするwhile (i <= Length){_data[i] += value;i += i & -i; // LSBの加算}}/// <summary>/// [0, <c>end</c>)の部分和を返します。/// </summary>/// <param name="end">部分和を求める半開区間の終了インデックス</param>/// <returns>区間の部分和</returns>public long Sum(Index end){var i = end.GetOffset(Length); // 0-indexedの半開区間=1-indexedの閉区間なので+1は不要unchecked{if ((uint)i >= (uint)_data.Length){throw new ArgumentOutOfRangeException(nameof(end));}}long sum = 0;while (i > 0){sum += _data[i];i -= i & -i; // LSBの減算}return sum;}/// <summary>/// <c>range</c>の部分和を返します。/// </summary>/// <param name="range">部分和を求める半開区間</param>/// <returns>区間の部分和</returns>public long Sum(Range range) => Sum(range.End) - Sum(range.Start);/// <summary>/// [<c>start</c>, <c>end</c>)の部分和を返します。/// </summary>/// <param name="start">部分和を求める半開区間の開始インデックス</param>/// <param name="end">部分和を求める半開区間の終了インデックス</param>/// <returns>区間の部分和</returns>public long Sum(int start, int end) => Sum(end) - Sum(start);/// <summary>/// [0, <c>index</c>)の部分和が<c>sum</c>未満になる最大の<c>index</c>を返します。/// BIT上の各要素は0以上の数である必要があります。/// </summary>/// <param name="sum"></param>/// <returns></returns>public int GetLowerBound(long sum){int index = 0;for (int offset = GetMostSignificantBitOf(Length); offset > 0; offset >>= 1){if (index + offset < _data.Length && _data[index + offset] < sum){index += offset;sum -= _data[index];}}return index;int GetMostSignificantBitOf(int n){int k = 1;while ((k << 1) <= n){k <<= 1;};return k;}}}}}namespace YukicoderContest257{class Program{static void Main(string[] args){IAtCoderQuestion question = new QuestionC();var answers = question.Solve(Console.In);var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(writer);foreach (var answer in answers){Console.WriteLine(answer);}Console.Out.Flush();}}}#region Base Classnamespace YukicoderContest257.Questions{public interface IAtCoderQuestion{IEnumerable<object> Solve(string input);IEnumerable<object> Solve(TextReader inputStream);}public abstract class AtCoderQuestionBase : IAtCoderQuestion{public IEnumerable<object> Solve(string input){var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));var reader = new StreamReader(stream, Encoding.Unicode);return Solve(reader);}public abstract IEnumerable<object> Solve(TextReader inputStream);}}#endregion#region Algorithmnamespace YukicoderContest257.Numerics{public static class NumericalAlgorithms{public static long Gcd(long a, long b){if (a < b){(a, b) = (b, a);}var result = b switch{0 => a,long n when n > 0 => Gcd(b, a % b),_ => throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。")};return result;}public static long Lcm(long a, long b){if (a < 0 || b < 0){throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。");}return a / Gcd(a, b) * b;}public static long Factorial(int n){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{n}は0以上の整数でなければなりません。");}long result = 1;for (int i = 2; i <= n; i++){result *= i;}return result;}public static long Permutation(int n, int r){CheckNR(n, r);long result = 1;for (int i = 0; i < r; i++){result *= n - i;}return result;}public static long Combination(int n, int r){CheckNR(n, r);r = Math.Min(r, n - r);// See https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinationslong result = 1;for (int i = 1; i <= r; i++){result *= n--;result /= i;}return result;}public static long CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);public static IEnumerable<(int prime, int count)> PrimeFactorization(int n){if (n <= 1){throw new ArgumentOutOfRangeException(nameof(n), $"{n}は2以上の整数でなければなりません。");}var dictionary = new Dictionary<int, int>();for (int i = 2; i * i <= n; i++){while (n % i == 0){if (dictionary.ContainsKey(i)){dictionary[i]++;}else{dictionary[i] = 1;}n /= i;}}if (n > 1){dictionary[n] = 1;}return dictionary.Select(p => (p.Key, p.Value));}private static void CheckNR(int n, int r){if (n <= 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は正の整数でなければなりません。");}if (r < 0){throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");}if (n < r){throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");}}}public readonly struct Modular : IEquatable<Modular>, IComparable<Modular>{private const int DefaultMod = 1000000007;public int Value { get; }public static int Mod { get; set; } = DefaultMod;[MethodImpl(MethodImplOptions.AggressiveInlining)]public Modular(long value){if (unchecked((ulong)value) < unchecked((ulong)Mod)){Value = (int)value;}else{Value = (int)(value % Mod);if (Value < 0){Value += Mod;}}}private Modular(int value) => Value = value;public static Modular Zero => new Modular(0);public static Modular One => new Modular(1);[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator +(Modular a, Modular b){var result = a.Value + b.Value;if (result >= Mod){result -= Mod; // 剰余演算を避ける}return new Modular(result);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator -(Modular a, Modular b){var result = a.Value - b.Value;if (result < 0){result += Mod; // 剰余演算を避ける}return new Modular(result);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator *(Modular a, Modular b) => new Modular((long)a.Value * b.Value);[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator /(Modular a, Modular b) => a * Pow(b.Value, Mod - 2);// 需要は不明だけど一応public static bool operator ==(Modular left, Modular right) => left.Equals(right);public static bool operator !=(Modular left, Modular right) => !(left == right);public static bool operator <(Modular left, Modular right) => left.CompareTo(right) < 0;public static bool operator <=(Modular left, Modular right) => left.CompareTo(right) <= 0;public static bool operator >(Modular left, Modular right) => left.CompareTo(right) > 0;public static bool operator >=(Modular left, Modular right) => left.CompareTo(right) >= 0;public static implicit operator Modular(long a) => new Modular(a);public static explicit operator int(Modular a) => a.Value;public static explicit operator long(Modular a) => a.Value;public static Modular Pow(int a, int n){switch (n){case 0:return Modular.One;case 1:return a;case int m when m >= 0: // ジャンプテーブル化はできなくなるvar p = Pow(a, m >> 1); // m / 2return p * p * Pow(a, m & 0x01); // m % 2default:throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。");}}private static List<int> _factorialCache;private static List<int> FactorialCache => _factorialCache ??= new List<int>() { 1 };private static int[] FactorialInverseCache { get; set; }const int defaultMaxFactorial = 1000000;public static Modular Factorial(int n){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");}for (int i = FactorialCache.Count; i <= n; i++) // Countが1(0!までキャッシュ済み)のとき1!~n!まで計算{FactorialCache.Add((int)((long)FactorialCache[i - 1] * i % Mod));}return new Modular(FactorialCache[n]);}public static Modular Permutation(int n, int r){CheckNR(n, r);return Factorial(n) / Factorial(n - r);}public static Modular Combination(int n, int r){CheckNR(n, r);r = Math.Min(r, n - r);try{return new Modular(FactorialCache[n]) * new Modular(FactorialInverseCache[r]) * new Modular(FactorialInverseCache[n - r]);}catch (Exception ex) when (ex is NullReferenceException || ex is ArgumentOutOfRangeException){throw new InvalidOperationException($"{nameof(Combination)}を呼び出す前に{nameof(InitializeCombinationTable)}により前計算を行う必要があります。", ex);}}public static void InitializeCombinationTable(int max = defaultMaxFactorial){Factorial(max);FactorialInverseCache = new int[max + 1];var fInv = (Modular.One / Factorial(max)).Value;FactorialInverseCache[max] = fInv;for (int i = max - 1; i >= 0; i--){fInv = (int)((long)fInv * (i + 1) % Mod);FactorialInverseCache[i] = fInv;}}public static Modular CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);private static void CheckNR(int n, int r){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");}if (r < 0){throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");}if (n < r){throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");}}public override string ToString() => Value.ToString();public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false;public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value;public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value.CompareTo(other.Value);public override int GetHashCode() => Value.GetHashCode();}public interface ISemigroup<TSet> where TSet : ISemigroup<TSet>{public TSet Multiply(TSet other);public static TSet operator *(ISemigroup<TSet> a, TSet b) => a.Multiply(b);}public interface IMonoid<TSet> : ISemigroup<TSet> where TSet : IMonoid<TSet>, new(){public TSet Identity { get; }}public interface IGroup<TSet> : IMonoid<TSet> where TSet : IGroup<TSet>, new(){public TSet Invert();public static TSet operator ~(IGroup<TSet> a) => a.Invert();}}#endregion#region Extensionsnamespace YukicoderContest257.Extensions{public static class StringExtensions{public static string Join<T>(this IEnumerable<T> source) => string.Concat(source);public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source);public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);}public static class TextReaderExtensions{public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));public static string ReadString(this TextReader reader) => reader.ReadLine();public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);// Supports primitive type only.public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));return (v1, v2);}public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));return (v1, v2, v3);}public static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));return (v1, v2, v3, v4);}public static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));return (v1, v2, v3, v4, v5);}public static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));return (v1, v2, v3, v4, v5, v6);}public static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));return (v1, v2, v3, v4, v5, v6, v7);}public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));return (v1, v2, v3, v4, v5, v6, v7, v8);}}}#endregion