結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-12-02 21:08:54 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 11,875 bytes |
コンパイル時間 | 1,095 ms |
コンパイル使用メモリ | 120,848 KB |
実行使用メモリ | 47,328 KB |
最終ジャッジ日時 | 2024-09-13 10:43:48 |
合計ジャッジ時間 | 12,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
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;using System.Collections.Generic;using System.Diagnostics;using System.Globalization;using System.IO;using System.Text;using System.Linq;using E = System.Linq.Enumerable;using System.Threading;internal partial class Solver {public void Run() {var n = ni();var a = ni(n);Array.Reverse(a);var d = new IndexDictionary<int>(a);var leftNum = new BinaryIndexTree(d.Count);var rightNum = new BinaryIndexTree(d.Count);var leftSum = new BinaryIndexTree(d.Count);var rightSum = new BinaryIndexTree(d.Count);for (int i = 0; i < n; i++) {rightSum.Add(d.IndexOf(a[i]), a[i]);rightNum.Add(d.IndexOf(a[i]), 1);}ModInt.SetMod998244353();ModInt ans = 0;for (int i = 0; i < n; i++) {var index = d.IndexOf(a[i]);rightNum.Add(index, -1);rightSum.Add(index, -a[i]);ModInt leftN = leftNum.Sum(0, index);ModInt rightN = rightNum.Sum(index + 1, d.Count);ans += leftN * rightN * a[i];ans += leftSum.Sum(0, index) * rightN;ans += rightSum.Sum(index + 1, d.Count) * leftN;leftNum.Add(index, 1);leftSum.Add(index, a[i]);}cout.WriteLine(ans);}}public class IndexDictionary<T> {private readonly Dictionary<T, int> _toIndex;private readonly T[] _array;public IndexDictionary(IEnumerable<T> source) : this(source, Comparer<T>.Default.Compare) { }public IndexDictionary(IEnumerable<T> source, Comparison<T> comparison) {_array = source.Distinct().ToArray();Array.Sort(_array, comparison);_toIndex = new Dictionary<T, int>(_array.Length);int index = -1;foreach (var x in _array) {_toIndex[x] = ++index;}}public int Count { get { return _array.Length; } }public T this[int index] { get { return _array[index]; } }public int IndexOf(T value) { return _toIndex[value]; }public T[] ToArray() {return _array.ToArray();}}public class BinaryIndexTree {private readonly long[] array;public BinaryIndexTree(int size) {array = new long[size];}public long Sum(int begin, int end) {if (begin != 0) {return Sum(0, end) - Sum(0, begin);}long val = 0;end--;for (; end >= 0; end = (end & (end + 1)) - 1) {val += array[end];}return val;}public void Add(int k, long val) {for (; k < array.Length; k |= k + 1) {array[k] += val;}}/// <summary>return min pos where sum(A[0] .. A[pos]) >= w</summary>public int LowerBound(long w) {if (w <= 0) {return 0;}int x = 0, k = 1, N = array.Length;while ((k << 1) <= N) {k <<= 1;}for (; k > 0; k >>= 1) {if (x + k - 1 < N && array[x + k - 1] < w) {w -= array[x + k - 1];x += k;}}return x;}}public partial struct ModInt : IEquatable<ModInt> {private static int mod = 0;private long _value;public ModInt(long x) {_value = x;Normalize();}private static long RegularMod(long x, int mod) {if (x >= mod) {if (x < 2 * mod) {return x - mod;}return x % mod;}if (x >= 0) {return x;}x = mod - RegularMod(-x, mod);return x == mod ? 0 : x;}public static int SetModValue(int m) {return mod = m;}public static int SetMod998244353() { return SetModValue(998244353); }public static int SetMod1000000007() { return SetModValue(1000000007); }private void Normalize() {_value = RegularMod(_value, mod);}public override string ToString() {return _value.ToString(CultureInfo.InvariantCulture);}public int ToInt() {return (int)_value;}public static bool operator ==(ModInt c1, ModInt c2) {return c1._value == c2._value;}public static bool operator !=(ModInt c1, ModInt c2) {return !(c1 == c2);}public static ModInt operator +(ModInt x, ModInt y) {return new ModInt(x._value + y._value);}public static ModInt operator -(ModInt x, ModInt y) {return new ModInt(x._value - y._value);}public static ModInt operator -(ModInt x) {return new ModInt(-x._value);}public static ModInt operator *(ModInt x, ModInt y) {return new ModInt(x._value * y._value);}public static ModInt operator /(ModInt x, ModInt y) {return new ModInt(x._value * Inverse(y._value, mod));}public static ModInt operator ++(ModInt x) {return x + 1;}public static ModInt operator --(ModInt x) {return x - 1;}public static ModInt Pow(ModInt x, long n) {ModInt r = 1;while (n > 0) {if ((n & 1) != 0) {r *= x;}x *= x;n >>= 1;}return r;}private static long ExtendedGcd(long a, long b, out long x, out long y) {if (b == 0) {x = 1; y = 0;return a;} else {var d = ExtendedGcd(b, a % b, out y, out x);y -= a / b * x;return d;}}private static long Inverse(long a, long mod) {long x = 0, y = 0;if (ExtendedGcd(a, mod, out x, out y) == 1) {return (x + mod) % mod;} else {throw new Exception("Invalid inverse " + a + " " + mod);}}public static implicit operator ModInt(long x) {return new ModInt(x);}public override bool Equals(object obj) {if (obj == null) {return false;}return _value.Equals(((ModInt)obj)._value);}public override int GetHashCode() {return _value.GetHashCode();}public bool Equals(ModInt other) {return _value.Equals(other._value);}object ToDump() { return _value; }}// PREWRITEN CODE BEGINS FROM HEREstatic public class StringExtensions {static public string JoinToString<T>(this IEnumerable<T> source, string separator = " ") {return string.Join(separator, source);}}internal partial class Solver : Scanner {static readonly int? StackSizeInMebiByte = null; //50;public static void StartAndJoin(Action action, int maxStackSize) {var thread = new Thread(new ThreadStart(action), maxStackSize);thread.Start();thread.Join();}public static void Main() {#if LOCALbyte[] inputBuffer = new byte[1000000];var inputStream = Console.OpenStandardInput(inputBuffer.Length);using (var reader = new StreamReader(inputStream, Console.InputEncoding, false, inputBuffer.Length)) {Console.SetIn(reader);new Solver(Console.In, Console.Out).Run();}#elseConsole.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });if (StackSizeInMebiByte.HasValue) {StartAndJoin(() => new Solver(Console.In, Console.Out).Run(), StackSizeInMebiByte.Value * 1024 * 1024);} else {new Solver(Console.In, Console.Out).Run();}Console.Out.Flush();#endif}#pragma warning disable IDE0052private readonly TextReader cin;private readonly TextWriter cout;private readonly TextWriter cerr;#pragma warning restore IDE0052public Solver(TextReader reader, TextWriter writer): base(reader) {cin = reader;cout = writer;cerr = Console.Error;}public Solver(string input, TextWriter writer): this(new StringReader(input), writer) {}#pragma warning disable IDE1006#pragma warning disable IDE0051private int ni() { return NextInt(); }private int[] ni(int n) { return NextIntArray(n); }private long nl() { return NextLong(); }private long[] nl(int n) { return NextLongArray(n); }private double nd() { return NextDouble(); }private double[] nd(int n) { return NextDoubleArray(n); }private string ns() { return Next(); }private string[] ns(int n) { return NextArray(n); }#pragma warning restore IDE1006#pragma warning restore IDE0051}#if DEBUGinternal static class LinqPadExtension {public static string TextDump<T>(this T obj) {if (obj is IEnumerable) return (obj as IEnumerable).Cast<object>().JoinToString().Dump();else return obj.ToString().Dump();}public static T Dump<T>(this T obj) {return LINQPad.Extensions.Dump(obj);}}#endifpublic class Scanner {private readonly TextReader Reader;private readonly CultureInfo ci = CultureInfo.InvariantCulture;private readonly char[] buffer = new char[2 * 1024];private int cursor = 0, length = 0;private string Token;private readonly StringBuilder sb = new StringBuilder(1024);public Scanner(): this(Console.In) {}public Scanner(TextReader reader) {Reader = reader;}public int NextInt() { return checked((int)NextLong()); }public long NextLong() {var s = Next();long r = 0;int i = 0;bool negative = false;if (s[i] == '-') {negative = true;i++;}for (; i < s.Length; i++) {r = r * 10 + (s[i] - '0');#if DEBUGif (!char.IsDigit(s[i])) throw new FormatException();#endif}return negative ? -r : r;}public double NextDouble() { return double.Parse(Next(), ci); }public string[] NextArray(int size) {string[] array = new string[size];for (int i = 0; i < size; i++) {array[i] = Next();}return array;}public int[] NextIntArray(int size) {int[] array = new int[size];for (int i = 0; i < size; i++) {array[i] = NextInt();}return array;}public long[] NextLongArray(int size) {long[] array = new long[size];for (int i = 0; i < size; i++) {array[i] = NextLong();}return array;}public double[] NextDoubleArray(int size) {double[] array = new double[size];for (int i = 0; i < size; i++) {array[i] = NextDouble();}return array;}public string Next() {if (Token == null) {if (!StockToken()) {throw new Exception();}}var token = Token;Token = null;return token;}public bool HasNext() {if (Token != null) {return true;}return StockToken();}private bool StockToken() {while (true) {sb.Clear();while (true) {if (cursor >= length) {cursor = 0;if ((length = Reader.Read(buffer, 0, buffer.Length)) <= 0) {break;}}var c = buffer[cursor++];if (33 <= c && c <= 126) {sb.Append(c);} else {if (sb.Length > 0) break;}}if (sb.Length > 0) {Token = sb.ToString();return true;}return false;}}}