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