Advertisement
Guest User

Untitled

a guest
Apr 30th, 2015
1,946
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.74 KB | None | 0 0
  1. class E {
  2.     static class Item implements Comparable<Item> {
  3.         int pos, val;
  4.  
  5.         public Item(int pos, int val) {
  6.             this.pos = pos;
  7.             this.val = val;
  8.         }
  9.  
  10.         public int compareTo(Item o) {
  11.             if (pos != o.pos) {
  12.                 return Integer.compare(pos, o.pos);
  13.             }
  14.             return Integer.compare(val, o.val);
  15.         }
  16.     }
  17.  
  18.     static class FenwickTree {
  19.         int n;
  20.         int[] a;
  21.  
  22.         public FenwickTree(int n) {
  23.             this.n = n;
  24.             a = new int[n];
  25.         }
  26.  
  27.         private int sum(int r) {
  28.             int res = 0;
  29.             for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
  30.                 res += a[i];
  31.             }
  32.             return res;
  33.         }
  34.  
  35.         private int sum(int l, int r) {
  36.             return sum(r) - sum(l - 1);
  37.         }
  38.  
  39.         private void inc(int i) {
  40.             for (; i < n; i |= i + 1) {
  41.                 a[i]++;
  42.             }
  43.         }
  44.     }
  45.  
  46.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  47.         int q = in.readInt();
  48.         TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
  49.         for (int i = 0; i < q; i++) {
  50.             int pos1 = in.readInt() - 1;
  51.             int pos2 = in.readInt() - 1;
  52.             int num1 = map.containsKey(pos1) ? map.get(pos1) : pos1;
  53.             int num2 = map.containsKey(pos2) ? map.get(pos2) : pos2;
  54.             map.put(pos1, num2);
  55.             map.put(pos2, num1);
  56.         }
  57.         Item[] a = new Item[map.size()];
  58.         int n = 0;
  59.         for (Map.Entry<Integer, Integer> e : map.entrySet()) {
  60.             a[n++] = new Item(e.getKey(), e.getValue());
  61.         }
  62.         int[] b = new int[n];
  63.         for (int i = 0; i < n; i++) {
  64.             b[i] = a[i].val;
  65.         }
  66.         compress(b);
  67.         long ans = 0;
  68.         FenwickTree tree = new FenwickTree(n);
  69.         for (int i = 0; i < n; i++) {
  70.             ans += tree.sum(b[i], n - 1);
  71.             tree.inc(b[i]);
  72.         }
  73.         for (int idxAfter = 0; idxAfter < n; idxAfter++) {
  74.             int idxBefore = ~Arrays.binarySearch(a, new Item(a[idxAfter].val, -1));
  75.             ans += Math.abs(a[idxAfter].pos - a[idxBefore].pos);
  76.             ans -= Math.abs(idxAfter - idxBefore);
  77.         }
  78.         out.printLine(ans);
  79.     }
  80.  
  81.     private void compress(int[] a) {
  82.         TreeSet<Integer> set = new TreeSet<Integer>();
  83.         for (int x : a) {
  84.             set.add(x);
  85.         }
  86.         TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
  87.         for (int x : set) {
  88.             int id = map.size();
  89.             map.put(x, id);
  90.         }
  91.         for (int i = 0; i < a.length; i++) {
  92.             a[i] = map.get(a[i]);
  93.         }
  94.     }
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement