結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
|
提出日時 | 2018-05-24 01:08:49 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,605 ms / 3,000 ms |
コード長 | 1,719 bytes |
コンパイル時間 | 2,460 ms |
コンパイル使用メモリ | 80,020 KB |
実行使用メモリ | 100,200 KB |
最終ジャッジ日時 | 2024-06-28 16:41:31 |
合計ジャッジ時間 | 19,109 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;public class Main {class BIT {int n;int[] a;public BIT(int n_) {n = n_;a = new int[n + 1];}void add(int k, int add) {++k;while (k < a.length) {a[k] += add;k += k & -k;}}int sum(int k) {++k;int ret = 0;while (k > 0) {ret += a[k];k -= k & -k;}return ret;}int sum(int a, int b) {return sum(b - 1) - sum(a - 1);}}void run() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();long[] A = new long[N];for (int i = 0; i < N; ++i) {A[i] = sc.nextLong();}A = shrink(A);long sum = 0;BIT bit = new BIT(A.length);for (int i = 0; i < N; ++i) {sum += bit.sum((int) A[i] + 1, N);bit.add((int) A[i], 1);}PrintWriter pw = new PrintWriter(System.out);pw.println(sum);for (int i = 0; i < N - 1; i++) {sum -= bit.sum(0, (int) A[i]);sum += bit.sum((int) A[i] + 1, N);pw.println(sum);}pw.close();}long[] shrink(long[] A) {int N = A.length;long[] ret = new long[N];long[][] B = new long[N][2];for (int i = 0; i < N; ++i) {B[i][0] = i;B[i][1] = A[i];}Arrays.sort(B, new Comparator<long[]>() {@Overridepublic int compare(long[] o1, long[] o2) {return Long.compare(o1[1], o2[1]);}});int p = 0;for (int i = 0; i < N; ++i) {ret[(int) B[i][0]] = p;if (i + 1 < N && B[i][1] == B[i + 1][1]) {continue;}++p;}return ret;}public static void main(String[] args) {new Main().run();}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}