warriorscats

kjkjdf

Apr 22nd, 2020
354
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.54 KB | None | 0 0
  1. import java.lang.*;
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. @SuppressWarnings("unused")
  6. public class permutariab {
  7.     public static class FastScanner {
  8.         private static BufferedReader br;
  9.         private static StringTokenizer st;
  10.        
  11.         public FastScanner (String s) {
  12.             try {
  13.                 br = new BufferedReader (new FileReader (s));
  14.             } catch (IOException e) {
  15.                 e.printStackTrace ();
  16.             }
  17.         }
  18.        
  19.         public FastScanner () {
  20.             br = new BufferedReader (new InputStreamReader (System.in));
  21.         }
  22.        
  23.         private String nextToken () {
  24.             while (st ==  null || !st.hasMoreElements ())
  25.                 try {
  26.                     st = new StringTokenizer (br.readLine ());
  27.                 } catch (IOException | NullPointerException e) {
  28.                     e.printStackTrace ();
  29.                 }
  30.             return st.nextToken ();
  31.         }
  32.        
  33.         public int nextInt () {
  34.             return Integer.parseInt (nextToken ());
  35.         }
  36.        
  37.         public long nextLong () {
  38.             return Long.parseLong (nextToken ());
  39.         }
  40.        
  41.         public double nextDouble () {
  42.             return Double.parseDouble (nextToken ());
  43.         }
  44.        
  45.         public void close () throws IOException {
  46.             br.close ();
  47.         }
  48.     }
  49.     public static class FastPrinter {
  50.         private static PrintWriter pw;
  51.        
  52.         public FastPrinter (String s) {
  53.             try {
  54.                 pw = new PrintWriter (new FileWriter (s));
  55.             } catch (IOException e) {
  56.                 e.printStackTrace ();
  57.             }
  58.         }
  59.        
  60.         public FastPrinter () {
  61.             pw = new PrintWriter (new OutputStreamWriter (System.out));
  62.         }
  63.        
  64.         public void println (int i) {
  65.             pw.println (i);
  66.         }
  67.        
  68.         public void println (long l) {
  69.             pw.println (l);
  70.         }
  71.        
  72.         public void println (double d) {
  73.             pw.println (d);
  74.         }
  75.        
  76.         public void println (String s) {
  77.             pw.println (s);
  78.         }
  79.        
  80.         public void println (String format, Object... args) {
  81.             println (String.format (format, args));
  82.         }
  83.        
  84.         public void close () throws IOException {
  85.             pw.close ();
  86.         }
  87.     }
  88.     public static class BinaryIndexedTree {
  89.         final static int NMAX = 1000001;
  90.         static int[] BITtree = new int[NMAX];
  91.        
  92.         public BinaryIndexedTree (int[] arr, int n) {
  93.             for (int i = 1; i <= n; ++ i)
  94.                 BITtree[i] = 0;
  95.         }
  96.        
  97.         private int nextIndex (int index) {
  98.             return index & (- index);
  99.         }
  100.        
  101.         public void updateBITtree (int n, int index, int val) {
  102.             while (index <= n) {
  103.                 BITtree[index] += val;
  104.                 index += nextIndex (index);
  105.             }
  106.         }
  107.        
  108.         public int getSum (int index) {
  109.             int sum = 0;
  110.             while (index > 0) {
  111.                 sum += BITtree[index];
  112.                 index -= nextIndex (index);
  113.             }
  114.             return sum;
  115.         }
  116.     }
  117.     private static int n, Arr[];
  118.     private static long ans = 0;
  119.     private static FastScanner Reader = new FastScanner ("permutariab.in");
  120.     private static FastPrinter Printer = new FastPrinter ("permutariab.out");
  121.     private static BinaryIndexedTree BIT;
  122.     private static HashMap <Integer, Integer> Hash = new HashMap <Integer, Integer> ();
  123.    
  124.     public static void main (String[] args) throws IOException {
  125.         n = Reader.nextInt ();
  126.         Arr = new int[n + 1];
  127.         try {
  128.             for (int i = 1, value; i <= n; ++ i) {
  129.                 Hash.put (value = Reader.nextInt (), i);
  130.                 //System.out.println (value + " ");
  131.             }
  132.             //System.out.println ("\n");
  133.             for (int i = 1, value; i <= n; ++ i) {
  134.                 Arr[i] = Hash.get (value = Reader.nextInt ());
  135.                 //System.out.println (value + " ");
  136.             }
  137.             Reader.close ();
  138.         } catch (NullPointerException e) {
  139.             e.printStackTrace ();
  140.         }
  141.         BIT = new BinaryIndexedTree (Arr, n);
  142.         for (int i = n; i >= 1; -- i) {
  143.             ans += Long.valueOf (BIT.getSum (Arr[i]));
  144.             BIT.updateBITtree (n, Arr[i], 1);
  145.         }
  146.         Printer.println (ans);
  147.         //System.out.println (ans);
  148.    
  149.         Printer.close ();
  150.     }
  151. }
Add Comment
Please, Sign In to add comment