結果
問題 | No.404 部分門松列 |
ユーザー |
![]() |
提出日時 | 2016-07-27 13:24:30 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 830 ms / 2,000 ms |
コード長 | 5,153 bytes |
コンパイル時間 | 1,152 ms |
コンパイル使用メモリ | 110,976 KB |
実行使用メモリ | 49,948 KB |
最終ジャッジ日時 | 2024-06-28 17:02:23 |
合計ジャッジ時間 | 16,407 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
コンパイルメッセージ
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;}}