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
AC × 2
AC × 25
AC × 45
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