fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.lang.Math;
  4.  
  5. class Solution {
  6.     static class Fenwick {
  7.         int n;
  8.         int[] bit;
  9.         Fenwick(int n) {
  10.             this.n = n;
  11.             bit = new int[n+1];
  12.         }
  13.         void add(int idx, int delta) {
  14.             for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
  15.         }
  16.         int sum(int idx) {
  17.             int s = 0;
  18.             for (; idx > 0; idx -= idx & -idx) s += bit[idx];
  19.             return s;
  20.         }
  21.         int rangeSum(int l, int r) {
  22.             if (r < l) return 0;
  23.             return sum(r) - sum(l-1);
  24.         }
  25.     }
  26.  
  27.     public static int permInv(int n, List<Integer> A, int k) {
  28.         int[] arr = new int[n];
  29.         for (int i = 0; i < n; ++i) arr[i] = A.get(i);
  30.  
  31.         Fenwick fwAll = new Fenwick(n);
  32.         long initialInv = 0;
  33.         for (int i = 0; i < n; ++i) {
  34.             int v = arr[i];
  35.             int leq = fwAll.sum(v);
  36.             int greaterBefore = i - leq;
  37.             initialInv += greaterBefore;
  38.             fwAll.add(v, 1);
  39.         }
  40.  
  41.         if (k <= 1) return (int) initialInv;
  42.  
  43.         long pairsInside = (long)k * (k - 1) / 2;
  44.  
  45.         Fenwick fwWindow = new Fenwick(n);
  46.         long windowInv = 0;
  47.         int currentWindowSize = 0;
  48.         for (int j = 0; j < k; ++j) {
  49.             int v = arr[j];
  50.             int leq = fwWindow.sum(v);
  51.             int greater = currentWindowSize - leq;
  52.             windowInv += greater;
  53.             fwWindow.add(v, 1);
  54.             currentWindowSize++;
  55.         }
  56.  
  57.         long best = Math.min(initialInv, initialInv + pairsInside - 2 * windowInv);
  58.  
  59.         for (int i = 1; i <= n - k; ++i) {
  60.             int leftVal = arr[i-1];
  61.             int lessThanLeft = fwWindow.sum(leftVal - 1);
  62.             windowInv -= lessThanLeft;
  63.             fwWindow.add(leftVal, -1);
  64.             currentWindowSize--;
  65.  
  66.             int newVal = arr[i + k - 1];
  67.             int leqNew = fwWindow.sum(newVal);
  68.             int greaterNew = currentWindowSize - leqNew;
  69.             windowInv += greaterNew;
  70.             fwWindow.add(newVal, 1);
  71.             currentWindowSize++;
  72.  
  73.             long newTotal = initialInv + pairsInside - 2 * windowInv;
  74.             if (newTotal < best) best = newTotal;
  75.         }
  76.  
  77.         return (int) best;
  78.     }
  79.  
  80.     public static void main(String[] args) {
  81.         Scanner scan = new Scanner(System.in);
  82.         int n = Integer.parseInt(scan.nextLine().trim());
  83.         List<Integer> A = new ArrayList<>(n);
  84.         for (int j = 0; j < n; j++) {
  85.             A.add(Integer.parseInt(scan.nextLine().trim()));
  86.         }
  87.         int k = Integer.parseInt(scan.nextLine().trim());
  88.         int result = permInv(n, A, k);
  89.         System.out.println(result);
  90.     }
  91. }
  92.  
Success #stdin #stdout 0.14s 54648KB
comments (?)
stdin
copy 
5
1
4
2
3
5
3
stdout
copy 
1
https://ideone.com/QlL4Ke
language:
Java (HotSpot 12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!