結果

問題 No.694 square1001 and Permutation 3
ユーザー 37zigen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0