Submission #2634788
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { int n; int[] hs; public static void main(String args[]) { new Main().run(); } void run() { FastReader sc = new FastReader(); n = sc.nextInt(); hs = new int[n]; for (int i = 0; i < n ; i++) { hs[i] = sc.nextInt(); } solve(); } void solve() { Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(hs[i]); } if (set.size() < n) { System.out.println(-1); return; } // coordinate compression Person[] persons = new Person[n]; for (int i = 0; i < n; i++) { persons[i] = new Person(i, hs[i]); } Arrays.sort(persons, new Comparator<Person>() { @Override public int compare(Person o1, Person o2) { return o1.height - o2.height; } }); for (int i = 0; i < n; i++) { persons[i].compHeight = i + 1; } Arrays.sort(persons, new Comparator<Person>() { @Override public int compare(Person o1, Person o2) { return o1.index - o2.index; } }); System.out.println(getInversionCost(persons)); } long getInversionCost(Person[] persons) { long ret = 0; FenwickTree ft = new FenwickTree(n); for (int i = 0; i < n; i++) { ret += persons[i].height * (ft.rangeSum(n) - ft.rangeSum(persons[i].compHeight)); ft.update(persons[i].compHeight, 1); } return ret; } class Person { int index; int height; int compHeight; public Person(int index, int height) { this.index = index; this.height = height; compHeight = -1; } } class FenwickTree { private final int[] tree; private final int N; FenwickTree(int N){ this.tree = new int[N + 1]; this.N = N; } private int lsb(int x){ return x & (-x); } void update(int position, int key){ while (position <= N){ tree[position] += key; position += lsb(position); } } int rangeSum(int position){ int sum = 0; while (position >= 1){ sum += tree[position]; position -= lsb(position); } return sum; } int rangeSum(int x, int y){ return rangeSum(y) - rangeSum(x - 1); } } static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }
Submission Info
Submission Time | |
---|---|
Task | E - Line up! |
User | ynish |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 4097 Byte |
Status | WA |
Exec Time | 531 ms |
Memory | 45916 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 70 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask0_sample_01.txt, subtask0_sample_02.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 71 ms | 21460 KB |
subtask0_sample_02.txt | AC | 69 ms | 19540 KB |
subtask1_01.txt | WA | 85 ms | 19924 KB |
subtask1_02.txt | WA | 85 ms | 21460 KB |
subtask1_03.txt | AC | 87 ms | 20564 KB |
subtask1_04.txt | AC | 87 ms | 17492 KB |
subtask1_05.txt | AC | 71 ms | 17748 KB |
subtask1_06.txt | AC | 71 ms | 18516 KB |
subtask1_07.txt | AC | 74 ms | 18900 KB |
subtask1_08.txt | AC | 83 ms | 18644 KB |
subtask1_09.txt | AC | 87 ms | 19796 KB |
subtask1_10.txt | AC | 81 ms | 19924 KB |
subtask1_11.txt | AC | 87 ms | 19668 KB |
subtask1_12.txt | AC | 87 ms | 18644 KB |
subtask1_13.txt | AC | 87 ms | 17876 KB |
subtask1_14.txt | WA | 90 ms | 21844 KB |
subtask1_15.txt | WA | 89 ms | 21844 KB |
subtask1_16.txt | WA | 99 ms | 21204 KB |
subtask1_17.txt | WA | 90 ms | 21332 KB |
subtask1_18.txt | WA | 87 ms | 18644 KB |
subtask1_19.txt | WA | 89 ms | 19924 KB |
subtask1_20.txt | WA | 86 ms | 18388 KB |
subtask1_21.txt | WA | 90 ms | 19028 KB |
subtask1_22.txt | WA | 87 ms | 18516 KB |
subtask1_23.txt | WA | 90 ms | 19412 KB |
subtask2_01.txt | AC | 207 ms | 41504 KB |
subtask2_02.txt | WA | 293 ms | 41844 KB |
subtask2_03.txt | AC | 275 ms | 40332 KB |
subtask2_04.txt | AC | 147 ms | 30304 KB |
subtask2_05.txt | AC | 208 ms | 45472 KB |
subtask2_06.txt | AC | 201 ms | 40688 KB |
subtask2_07.txt | AC | 205 ms | 41820 KB |
subtask2_08.txt | AC | 210 ms | 40032 KB |
subtask2_09.txt | AC | 224 ms | 43140 KB |
subtask2_10.txt | AC | 200 ms | 45460 KB |
subtask2_11.txt | WA | 498 ms | 43880 KB |
subtask2_12.txt | WA | 505 ms | 43532 KB |
subtask2_13.txt | WA | 407 ms | 45916 KB |
subtask2_14.txt | WA | 469 ms | 40020 KB |
subtask2_15.txt | WA | 455 ms | 41868 KB |
subtask2_16.txt | WA | 531 ms | 41228 KB |
subtask2_17.txt | WA | 525 ms | 42040 KB |
subtask2_18.txt | WA | 452 ms | 44300 KB |
subtask2_19.txt | WA | 485 ms | 43536 KB |
subtask2_20.txt | WA | 523 ms | 43812 KB |