Submission #2634795
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 += (long)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 | 100 |
Code Size | 4103 Byte |
Status | AC |
Exec Time | 497 ms |
Memory | 45788 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 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 | 74 ms | 21076 KB |
subtask0_sample_02.txt | AC | 69 ms | 20820 KB |
subtask1_01.txt | AC | 88 ms | 19284 KB |
subtask1_02.txt | AC | 85 ms | 21588 KB |
subtask1_03.txt | AC | 85 ms | 18900 KB |
subtask1_04.txt | AC | 75 ms | 21460 KB |
subtask1_05.txt | AC | 74 ms | 19156 KB |
subtask1_06.txt | AC | 72 ms | 16084 KB |
subtask1_07.txt | AC | 73 ms | 18772 KB |
subtask1_08.txt | AC | 90 ms | 19668 KB |
subtask1_09.txt | AC | 80 ms | 20180 KB |
subtask1_10.txt | AC | 88 ms | 18132 KB |
subtask1_11.txt | AC | 80 ms | 21076 KB |
subtask1_12.txt | AC | 88 ms | 18772 KB |
subtask1_13.txt | AC | 86 ms | 21716 KB |
subtask1_14.txt | AC | 90 ms | 21716 KB |
subtask1_15.txt | AC | 93 ms | 18772 KB |
subtask1_16.txt | AC | 89 ms | 19540 KB |
subtask1_17.txt | AC | 88 ms | 19540 KB |
subtask1_18.txt | AC | 88 ms | 18644 KB |
subtask1_19.txt | AC | 89 ms | 20180 KB |
subtask1_20.txt | AC | 85 ms | 21588 KB |
subtask1_21.txt | AC | 87 ms | 19668 KB |
subtask1_22.txt | AC | 88 ms | 20180 KB |
subtask1_23.txt | AC | 90 ms | 19028 KB |
subtask2_01.txt | AC | 211 ms | 41816 KB |
subtask2_02.txt | AC | 271 ms | 41428 KB |
subtask2_03.txt | AC | 280 ms | 42764 KB |
subtask2_04.txt | AC | 163 ms | 30188 KB |
subtask2_05.txt | AC | 200 ms | 45148 KB |
subtask2_06.txt | AC | 218 ms | 44840 KB |
subtask2_07.txt | AC | 217 ms | 40816 KB |
subtask2_08.txt | AC | 207 ms | 43928 KB |
subtask2_09.txt | AC | 199 ms | 40288 KB |
subtask2_10.txt | AC | 213 ms | 40844 KB |
subtask2_11.txt | AC | 475 ms | 42028 KB |
subtask2_12.txt | AC | 491 ms | 45788 KB |
subtask2_13.txt | AC | 417 ms | 41180 KB |
subtask2_14.txt | AC | 422 ms | 42844 KB |
subtask2_15.txt | AC | 420 ms | 41100 KB |
subtask2_16.txt | AC | 496 ms | 40040 KB |
subtask2_17.txt | AC | 492 ms | 41940 KB |
subtask2_18.txt | AC | 497 ms | 41996 KB |
subtask2_19.txt | AC | 421 ms | 43256 KB |
subtask2_20.txt | AC | 448 ms | 40912 KB |