結果
問題 | 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[]>() { @Override public 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)); } }