結果
問題 | No.404 部分門松列 |
ユーザー | eitaho |
提出日時 | 2016-07-27 13:24:30 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,048 ms / 2,000 ms |
コード長 | 5,153 bytes |
コンパイル時間 | 2,449 ms |
コンパイル使用メモリ | 110,640 KB |
実行使用メモリ | 54,136 KB |
最終ジャッジ日時 | 2023-09-11 02:32:45 |
合計ジャッジ時間 | 18,736 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
23,148 KB |
testcase_01 | AC | 74 ms
25,272 KB |
testcase_02 | AC | 75 ms
23,160 KB |
testcase_03 | AC | 74 ms
23,212 KB |
testcase_04 | AC | 84 ms
23,420 KB |
testcase_05 | AC | 84 ms
23,332 KB |
testcase_06 | AC | 85 ms
25,352 KB |
testcase_07 | AC | 85 ms
23,480 KB |
testcase_08 | AC | 85 ms
23,344 KB |
testcase_09 | AC | 85 ms
23,420 KB |
testcase_10 | AC | 84 ms
23,396 KB |
testcase_11 | AC | 85 ms
23,380 KB |
testcase_12 | AC | 83 ms
23,384 KB |
testcase_13 | AC | 455 ms
43,396 KB |
testcase_14 | AC | 394 ms
41,636 KB |
testcase_15 | AC | 363 ms
41,324 KB |
testcase_16 | AC | 499 ms
44,764 KB |
testcase_17 | AC | 674 ms
52,032 KB |
testcase_18 | AC | 342 ms
37,736 KB |
testcase_19 | AC | 288 ms
43,124 KB |
testcase_20 | AC | 433 ms
46,864 KB |
testcase_21 | AC | 611 ms
43,796 KB |
testcase_22 | AC | 407 ms
37,196 KB |
testcase_23 | AC | 502 ms
47,932 KB |
testcase_24 | AC | 603 ms
47,992 KB |
testcase_25 | AC | 1,048 ms
54,136 KB |
testcase_26 | AC | 877 ms
50,992 KB |
testcase_27 | AC | 260 ms
37,316 KB |
testcase_28 | AC | 553 ms
48,124 KB |
testcase_29 | AC | 717 ms
50,956 KB |
testcase_30 | AC | 444 ms
44,080 KB |
testcase_31 | AC | 182 ms
33,032 KB |
testcase_32 | AC | 674 ms
51,780 KB |
testcase_33 | AC | 647 ms
51,532 KB |
testcase_34 | AC | 519 ms
43,548 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.Linq; using System.Text; using System.Text.RegularExpressions; using System.Collections.Generic; using System.Diagnostics; using System.Numerics; using Enu = System.Linq.Enumerable; public class Program { public void Solve() { int N = Reader.Int(); var A = Reader.IntArray(N); int Q = Reader.Int(); var table = Reader.IntTable(Q); var dic = Compress(A); var sorted = dic.Keys.OrderBy(a => a).ToArray(); int M = dic.Count; var L = new BinaryIndexedTree(M); var R = new BinaryIndexedTree(M); var same = new BinaryIndexedTree(M); var Lcount = new long[M]; var Rcount = new long[M]; foreach (var a in A) { R.Add(dic[a], 1); Rcount[dic[a]]++; } var ans = new long[M + 1]; foreach (int a in A.Select(a => dic[a])) { R.Add(a, -1); Rcount[a]--; same.Add(a, -Lcount[a]); ans[a + 1] += L.Sum(a - 1) * R.Sum(a - 1) + L.Sum(a + 1, M) * R.Sum(a + 1, M); ans[a + 1] -= same.Sum(a - 1) + same.Sum(a + 1, M); L.Add(a, 1); Lcount[a]++; same.Add(a, Rcount[a]); } for (int i = 1; i < ans.Length; i++) ans[i] += ans[i - 1]; Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var q in table) { int a = LowerBound(sorted, q[0]); int b = UpperBound(sorted, q[1]); Console.WriteLine(ans[b] - ans[a]); } Console.Out.Flush(); } static int LowerBound(int[] A, int val, int L = 0, int R = -1) { if (R == -1) R = A.Length; while (R - L >= 1) { int mid = (L + R) / 2; if (A[mid] >= val) R = mid; else L = mid + 1; } return R; } static int UpperBound(int[] A, int val, int L = 0, int R = -1) { if (R == -1) R = A.Length; while (R - L >= 1) { int mid = (L + R) / 2; if (A[mid] > val) R = mid; else L = mid + 1; } return R; } Dictionary<T, int> Compress<T>(IEnumerable<T> A) { var sortedSet = new SortedSet<T>(); foreach (var a in A) sortedSet.Add(a); var sorted = sortedSet.ToArray(); var res = new Dictionary<T, int>(); foreach (var a in A) if (!res.ContainsKey(a)) res[a] = Array.BinarySearch(sorted, a); return res; } class BinaryIndexedTree { private readonly int N; private readonly long[] A; public BinaryIndexedTree(int N) { this.N = N + 1; A = new long[N + 2]; } public void Add(int i, long val) { if (i < 0) return; for (++i; i <= N; i += i & -i) A[i] += val; } public void Update(int i, long val) { Add(i, val - (Sum(i) - Sum(i - 1))); } public long Sum(int i) // [0, i] { if (i < 0) return 0; long sum = 0; for (++i; i > 0; i &= i - 1) sum += A[i]; return sum; } public long Sum(int L, int R) // [L, R) { return Sum(R - 1) - Sum(L - 1); } } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { A = new string[0]; } public static void Set(TextReader r) { reader = r; Init(); } public static void Set(string file) { reader = new StreamReader(file); Init(); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } static string[] Split(string s) { return s.Split(separator, op); } static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }