SHARE
TWEET

Untitled

darrenyao Dec 11th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. /*
  5. ID: darrenyao
  6. LANG: JAVA
  7. TASK: circlecross
  8. */
  9. public class circlecross {
  10.  
  11.     static class InputReader {
  12.         BufferedReader reader;
  13.         StringTokenizer tokenizer;
  14.  
  15.         public InputReader() throws FileNotFoundException {
  16.             reader = new BufferedReader(new FileReader("circlecross.in"));
  17.             tokenizer = null;
  18.         }
  19.  
  20.         String next() {
  21.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  22.                 try {
  23.                     tokenizer = new StringTokenizer(reader.readLine());
  24.                 } catch (IOException e) {
  25.                     throw new RuntimeException(e);
  26.                 }
  27.             }
  28.             return tokenizer.nextToken();
  29.         }
  30.  
  31.         public int nextInt() {
  32.             return Integer.parseInt(next());
  33.         }
  34.  
  35.         public long nextLong() {
  36.             return Long.parseLong(next());
  37.         }
  38.  
  39.         public double nextDouble() {
  40.             return Double.parseDouble(next());
  41.         }
  42.     }
  43.  
  44.     public static void main(String[] args) throws FileNotFoundException, IOException {
  45.  
  46.         InputReader r = new InputReader();
  47.         PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("circlecross.out")));
  48.         long ans = 0;
  49.         int n = r.nextInt();
  50.         int[] arr = new int[2 * n + 1];
  51.         for (int i = 1; i <= 2 * n; i++) {
  52.             arr[i] = r.nextInt();
  53.         }
  54.         int[] f = new int[2 * n + 1];
  55.         int[] startPos = new int[n+1];
  56.         int[] endPos = new int[n+1];
  57.         boolean[] seen = new boolean[n+1];
  58.         Fenwick fenwick = new Fenwick(f);
  59.         for(int i = 1; i <= 2 * n; i++){
  60.             if(startPos[arr[i]] != 0){
  61.                 endPos[arr[i]] = i;
  62.             } else {
  63.                 startPos[arr[i]] = i;
  64.             }
  65.         }
  66.         for(int i = 1; i <= 2 * n; i++){
  67.             if(!seen[arr[i]]){
  68.                 fenwick.update(i, 1);
  69.                 seen[arr[i]] = true;
  70.             } else {
  71.                 ans += (fenwick.rangeSum(startPos[arr[i]], endPos[arr[i]]));
  72.                 fenwick.update(i, -1);
  73.             }
  74.  
  75.         }
  76.         pw.println(ans);
  77.         pw.close();
  78.     }
  79.  
  80.     static class Fenwick {
  81.         public int[] arr; // 1-indexed array. index 0 is a dummy index and should always be 0.
  82.         public int[] tree; // BIT array
  83.         public int n;
  84.  
  85.         public Fenwick(int[] arr) {
  86.             n = arr.length - 1;
  87.             tree = new int[n + 1];
  88.             this.arr = new int[n + 1];
  89.             for (int i = 1; i <= n; i++) {
  90.                 update(i, arr[i]);
  91.             }
  92.         }
  93.  
  94.         /**
  95.          * Returns prefix sum up to index, inclusive
  96.          */
  97.         public int prefixSum(int index) {
  98.             int sum = 0;
  99.             while (index > 0) {
  100.                 sum += tree[index];
  101.                 index -= index & (-index);
  102.             }
  103.             return sum;
  104.         }
  105.  
  106.         /**
  107.          * Returns range sum from arr[a ... b] inclusive
  108.          */
  109.         public int rangeSum(int l, int r) {
  110.             return prefixSum(r) - prefixSum(l - 1);
  111.         }
  112.  
  113.         public int valueAt(int index) {
  114.             return rangeSum(index, index);
  115.         }
  116.  
  117.         /**
  118.          * Increments the value at index by value
  119.          */
  120.         public void update(int index, int value) {
  121.             while (index <= n) {
  122.                 tree[index] += value;
  123.                 index += index & (-index);
  124.             }
  125.         }
  126.     }
  127. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top