ivane_shubham's blog

By ivane_shubham, history, 3 years ago, In English

While solving this problem I am getting the runtime error and on sample test cases it is running fine. Thanks in advance java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:899) at java.util.TimSort.mergeAt(TimSort.java:516) at java.util.TimSort.mergeCollapse(TimSort.java:441) at java.util.TimSort.sort(TimSort.java:245) at java.util.Arrays.sort(Arrays.java:1512) at java.util.ArrayList.sort(ArrayList.java:1462) at java.util.Collections.sort(Collections.java:177) at P1132C.testCases(P1132C.java:29) at P1132C.main(P1132C.java:12)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import javafx.util.Pair;

public class P1132C {

    private static int mod = 1;

    public static void main (String[] args) {
        testCases();
    }

    public static void testCases () {
        FastScanner fs = new FastScanner();
        int T = true ? 1 : fs.nextInt();
        for (int tt = 0 ; tt < T ; tt++) {
            int n = fs.nextInt(), p = fs.nextInt();
            int[] wall = new int[n];
            Arrays.fill(wall, 0);
            int[][] sections = new int[p][2];
            for(int i = 0 ; i < p ; i++) sections[i] = fs.readArray(2);
            List<Pair<Integer, Integer>> list = new ArrayList<>();
            for(int i = 0 ; i < p ; i++) {
                Pair<Integer,Integer> pair = new Pair<>(sections[i][1] - sections[i][0] + 1, i);
                list.add(pair);
            }
            Collections.sort(list, (a, b) -> {
                if(a.getKey() >= b.getKey()) return -1;
                else if(a.getKey() == b.getKey()) return a.getValue() < b.getValue() ? -1 : 1;
                else return 1;
            });
            int cnt = 0;
            Integer[] ans = new Integer[p];
            for(Pair<Integer,Integer> pair: list) {
                int start = sections[pair.getValue()][0];
                int end = sections[pair.getValue()][1];
                int area = 0;
                for(int i = start ; i <= end ; i++) {
                    if(wall[i-1] == 1) continue;
                    area++;
                    wall[i-1] = 1;
                }
                ans[pair.getValue()] = area;
            }
            int ta = 0;
            Arrays.sort(ans, Collections.reverseOrder());
            for(int i = 0 ; i < p-2 ; i++) {
                ta += ans[i];
            }
            print(ta);
        }
    }

    private static long binPower (int n, int p) {
        long ans = 1;
        while (p > 0) {
            if (( p & 1 ) == 1) {
                ans = ans * n;
            }
            n = n * n;
            p = p >> 1;
        }
        return ans;
    }

    private static long mulUnderMod (int m, int n) {
        return ( ( m % mod ) * ( n % mod ) ) % mod;
    }

    private static int gcd (int a, int b) {
        int temp;
        if (a < b) {
            temp = a;
            a = b;
            b = temp;
        }
        while (b > 0) {
            a = a % b;
            temp = a;
            a = b;
            b = temp;
        }
        return a;
    }


    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next () {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt () {
            return Integer.parseInt(next());
        }

        int[] readArray (int n) {
            int[] a = new int[n];
            for (int i = 0 ; i < n ; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong () {
            return Long.parseLong(next());
        }

        char nextChar () {
            return next().charAt(0);
        }

        char[] readArray () {
            return next().toCharArray();
        }

        long[] readLongArray (int n) {
            long[] a = new long[n];
            for (int i = 0 ; i < n ; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static void print (int n) {
        System.out.println(n);
    }

    static void print (long n) {
        System.out.println(n);
    }

    static void print (double n) {
        System.out.println(n);
    }

    static void print (float n) {
        System.out.println(n);
    }

    static void print (String n) {
        System.out.println(n);
    }

    static void print (Collection<?> c) {
        System.out.println(c.toString());
    }

    static void print (int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    static void print (float[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    static void print (long[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    static void print (double[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    static void print (boolean bool) {
        System.out.print(String.valueOf(bool));
    }

    static void print (int[][] arr) {
        for (int i = 0 ; i < arr.length ; i++) {
            print(arr[i]);
        }
    }
}

  • Vote: I like it
  • -21
  • Vote: I do not like it