結果
問題 | No.1300 Sum of Inversions |
ユーザー |
|
提出日時 | 2024-09-24 23:49:37 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 509 ms / 2,000 ms |
コード長 | 3,436 bytes |
コンパイル時間 | 14,482 ms |
コンパイル使用メモリ | 172,324 KB |
実行使用メモリ | 236,096 KB |
最終ジャッジ日時 | 2024-09-24 23:50:08 |
合計ジャッジ時間 | 24,759 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (100 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();public static void Main(){Solve();}static void Solve(){var n = NN;var a = NList;var set = new HashSet<int>(a);var list = new List<int>(set);list.Sort();var dic = new Dictionary<int, int>();for (var i = 0; i < list.Count; ++i) dic[list[i]] = i;var mod = 998_244_353;var lst = new FenwickTree(list.Count);var lct = new FenwickTree(list.Count);var ls = new long[n];var lc = new long[n];for (var i = 0; i < n; ++i){ls[i] = (lst.Sum(list.Count - 1) - lst.Sum(dic[a[i]])) % mod;lc[i] = lct.Sum(list.Count - 1) - lct.Sum(dic[a[i]]);lst.Add(dic[a[i]], a[i]);lct.Add(dic[a[i]], 1);}var rst = new FenwickTree(n);var rct = new FenwickTree(n);var rs = new long[n];var rc = new long[n];for (var i = n - 1; i >= 0; --i){if (dic[a[i]] > 0){rs[i] = rst.Sum(dic[a[i]] - 1) % mod;rc[i] = rct.Sum(dic[a[i]] - 1);}rst.Add(dic[a[i]], a[i]);rct.Add(dic[a[i]], 1);}var ans = 0L;for (var i = 0; i < n; ++i){ans = (ans + lc[i] * rc[i] % mod * a[i] % mod + lc[i] * rs[i] % mod + ls[i] * rc[i] % mod) % mod;}WriteLine(ans);}class FenwickTree{int size;long[] tree;public FenwickTree(int size){this.size = size;tree = new long[size + 2];}public void Add(int index, int value){++index;for (var x = index; x <= size; x += (x & -x)) tree[x] += value;}/// <summary>先頭からindexまでの和(include index)</summary>public long Sum(int index){if (index < 0) return 0;++index;var sum = 0L;for (var x = index; x > 0; x -= (x & -x)) sum += tree[x];return sum;}public long Get(int index){if (index == 0) return Sum(0);return Sum(index) - Sum(index - 1);}/// <summary>Sum(x) >= value となる最小のxを求める</summary>// 各要素は非負であることpublic int LowerBound(long value){if (value < 0) return -1;var x = 0;var b = 1;while (b * 2 <= size) b <<= 1;for (var k = b; k > 0; k >>= 1){if (x + k <= size && tree[x + k] < value){value -= tree[x + k];x += k;}}return x;}}}