結果

問題 No.694 square1001 and Permutation 3
ユーザー tenten
提出日時 2021-03-10 13:59:47
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,656 ms / 3,000 ms
コード長 1,910 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 78,652 KB
実行使用メモリ 127,344 KB
最終ジャッジ日時 2024-10-12 04:31:58
合計ジャッジ時間 14,970 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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

import java.util.*;
import java.io.*;
public class Main {
public static void main (String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
long ans = 0;
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
map.put(arr[i], 0);
}
int idx = 1;
for (int x : map.keySet()) {
map.put(x, idx);
idx++;
}
BinaryIndexedTree bit = new BinaryIndexedTree(idx);
long total = 0;
for (int i = 0; i < n; i++) {
total += bit.getSum(idx - 1) - bit.getSum(map.get(arr[i]));
bit.add(map.get(arr[i]), 1);
}
StringBuilder sb = new StringBuilder();
int[] counts = new int[idx];
for (int i = 0; i < idx; i++) {
counts[i] = bit.getSum(i);
}
sb.append(total).append("\n");
for (int i = 0; i < n - 1; i++) {
total -= counts[map.get(arr[i]) - 1];
total += counts[idx - 1] - counts[map.get(arr[i])];
sb.append(total).append("\n");
}
System.out.print(sb);
}
}
class BinaryIndexedTree {
int size;
int[] tree;
public BinaryIndexedTree(int size) {
this.size = size;
tree = new int[size];
}
public void add(int idx, int value) {
int mask = 1;
while (idx < size) {
if ((idx & mask) != 0) {
tree[idx] += value;
idx += mask;
}
mask <<= 1;
}
}
public int getSum(int from, int to) {
return getSum(to) - getSum(from - 1);
}
public int getSum(int x) {
int mask = 1;
int ans = 0;
while (x > 0) {
if ((x & mask) != 0) {
ans += tree[x];
x -= mask;
}
mask <<= 1;
}
return ans;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0