結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー | AreTrash |
提出日時 | 2018-06-09 00:46:52 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,902 ms / 3,000 ms |
コード長 | 3,458 bytes |
コンパイル時間 | 2,932 ms |
コンパイル使用メモリ | 116,680 KB |
実行使用メモリ | 82,216 KB |
最終ジャッジ日時 | 2024-06-30 12:09:20 |
合計ジャッジ時間 | 11,944 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
25,864 KB |
testcase_01 | AC | 47 ms
25,744 KB |
testcase_02 | AC | 47 ms
27,660 KB |
testcase_03 | AC | 48 ms
25,988 KB |
testcase_04 | AC | 49 ms
25,904 KB |
testcase_05 | AC | 48 ms
27,652 KB |
testcase_06 | AC | 48 ms
25,868 KB |
testcase_07 | AC | 797 ms
39,040 KB |
testcase_08 | AC | 1,114 ms
49,500 KB |
testcase_09 | AC | 1,902 ms
80,952 KB |
testcase_10 | AC | 697 ms
39,060 KB |
testcase_11 | AC | 1,901 ms
82,216 KB |
testcase_12 | AC | 1,887 ms
81,396 KB |
testcase_13 | AC | 47 ms
27,784 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; using System.Linq; namespace No694_1 { public class Program { void Solve(StreamScanner ss, StreamWriter sw) { //--------------------------------- var N = ss.Next(int.Parse); var A = Compress(ss.Next(long.Parse, N)); var cs = new Dictionary<int, int>(); foreach (var tup in A.OrderBy(x => x).Select((a, i) => (a, i))) { var (a, i) = (tup.Item1, tup.Item2); if (cs.ContainsKey(a)) cs[a]--; else cs.Add(a, N - 2 * i - 1); } var bit = new BinaryIndexedTree(N); var cross = 0L; foreach (var tup in A.Select((a, i) => (a, i))) { var (a, i) = (tup.Item1, tup.Item2); cross += i - bit.Sum(a); bit.Add(a, 1); } sw.WriteLine(cross); foreach (var a in A.Take(N - 1)) { cross += cs[a]; sw.WriteLine(cross); } //--------------------------------- } IEnumerable<int> Compress(IEnumerable<long> source) { var comp = source .Distinct() .OrderBy(x => x) .Select((k, v) => new {k, v}) .ToDictionary(kvp => kvp.k, kvp => kvp.v); return source.Select(x => comp[x] + 1); } static void Main() { var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput())); var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; new Program().Solve(ss, sw); sw.Flush(); } static readonly Func<string, string> String = s => s; } public class BinaryIndexedTree { readonly int _size; readonly long[] _bit; public BinaryIndexedTree(int size) { _size = size; _bit = new long[_size + 1]; } public void Add(int x, int w) { for (var i = x; i <= _size; i += i & -i) _bit[i] += w; } public long Sum(int x) { var ret = 0L; for (var i = x; i >= 1; i -= i & -i) ret += _bit[i]; return ret; } } public class StreamScanner { static readonly char[] Sep = { ' ' }; readonly Queue<string> buffer = new Queue<string>(); readonly TextReader textReader; public StreamScanner(TextReader textReader) { this.textReader = textReader; } public T Next<T>(Func<string, T> parser) { if (buffer.Count != 0) return parser(buffer.Dequeue()); var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries); foreach (var nextString in nextStrings) buffer.Enqueue(nextString); return Next(parser); } public T[] Next<T>(Func<string, T> parser, int x) { var ret = new T[x]; for (var i = 0; i < x; ++i) ret[i] = Next(parser); return ret; } public T[][] Next<T>(Func<string, T> parser, int x, int y) { var ret = new T[y][]; for (var i = 0; i < y; ++i) ret[i] = Next(parser, x); return ret; } } }