Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.lang.*;
- import java.util.*;
- import java.io.*;
- @SuppressWarnings("unused")
- public class permutariab {
- public static class FastScanner {
- private static BufferedReader br;
- private static StringTokenizer st;
- public FastScanner (String s) {
- try {
- br = new BufferedReader (new FileReader (s));
- } catch (IOException e) {
- e.printStackTrace ();
- }
- }
- public FastScanner () {
- br = new BufferedReader (new InputStreamReader (System.in));
- }
- private String nextToken () {
- while (st == null || !st.hasMoreElements ())
- try {
- st = new StringTokenizer (br.readLine ());
- } catch (IOException | NullPointerException e) {
- e.printStackTrace ();
- }
- return st.nextToken ();
- }
- public int nextInt () {
- return Integer.parseInt (nextToken ());
- }
- public long nextLong () {
- return Long.parseLong (nextToken ());
- }
- public double nextDouble () {
- return Double.parseDouble (nextToken ());
- }
- public void close () throws IOException {
- br.close ();
- }
- }
- public static class FastPrinter {
- private static PrintWriter pw;
- public FastPrinter (String s) {
- try {
- pw = new PrintWriter (new FileWriter (s));
- } catch (IOException e) {
- e.printStackTrace ();
- }
- }
- public FastPrinter () {
- pw = new PrintWriter (new OutputStreamWriter (System.out));
- }
- public void println (int i) {
- pw.println (i);
- }
- public void println (long l) {
- pw.println (l);
- }
- public void println (double d) {
- pw.println (d);
- }
- public void println (String s) {
- pw.println (s);
- }
- public void println (String format, Object... args) {
- println (String.format (format, args));
- }
- public void close () throws IOException {
- pw.close ();
- }
- }
- public static class BinaryIndexedTree {
- final static int NMAX = 1000001;
- static int[] BITtree = new int[NMAX];
- public BinaryIndexedTree (int[] arr, int n) {
- for (int i = 1; i <= n; ++ i)
- BITtree[i] = 0;
- }
- private int nextIndex (int index) {
- return index & (- index);
- }
- public void updateBITtree (int n, int index, int val) {
- while (index <= n) {
- BITtree[index] += val;
- index += nextIndex (index);
- }
- }
- public int getSum (int index) {
- int sum = 0;
- while (index > 0) {
- sum += BITtree[index];
- index -= nextIndex (index);
- }
- return sum;
- }
- }
- private static int n, Arr[];
- private static long ans = 0;
- private static FastScanner Reader = new FastScanner ("permutariab.in");
- private static FastPrinter Printer = new FastPrinter ("permutariab.out");
- private static BinaryIndexedTree BIT;
- private static HashMap <Integer, Integer> Hash = new HashMap <Integer, Integer> ();
- public static void main (String[] args) throws IOException {
- n = Reader.nextInt ();
- Arr = new int[n + 1];
- try {
- for (int i = 1, value; i <= n; ++ i) {
- Hash.put (value = Reader.nextInt (), i);
- //System.out.println (value + " ");
- }
- //System.out.println ("\n");
- for (int i = 1, value; i <= n; ++ i) {
- Arr[i] = Hash.get (value = Reader.nextInt ());
- //System.out.println (value + " ");
- }
- Reader.close ();
- } catch (NullPointerException e) {
- e.printStackTrace ();
- }
- BIT = new BinaryIndexedTree (Arr, n);
- for (int i = n; i >= 1; -- i) {
- ans += Long.valueOf (BIT.getSum (Arr[i]));
- BIT.updateBITtree (n, Arr[i], 1);
- }
- Printer.println (ans);
- //System.out.println (ans);
- Printer.close ();
- }
- }
Add Comment
Please, Sign In to add comment