Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class E {
- static class Item implements Comparable<Item> {
- int pos, val;
- public Item(int pos, int val) {
- this.pos = pos;
- this.val = val;
- }
- public int compareTo(Item o) {
- if (pos != o.pos) {
- return Integer.compare(pos, o.pos);
- }
- return Integer.compare(val, o.val);
- }
- }
- static class FenwickTree {
- int n;
- int[] a;
- public FenwickTree(int n) {
- this.n = n;
- a = new int[n];
- }
- private int sum(int r) {
- int res = 0;
- for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
- res += a[i];
- }
- return res;
- }
- private int sum(int l, int r) {
- return sum(r) - sum(l - 1);
- }
- private void inc(int i) {
- for (; i < n; i |= i + 1) {
- a[i]++;
- }
- }
- }
- public void solve(int testNumber, InputReader in, OutputWriter out) {
- int q = in.readInt();
- TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
- for (int i = 0; i < q; i++) {
- int pos1 = in.readInt() - 1;
- int pos2 = in.readInt() - 1;
- int num1 = map.containsKey(pos1) ? map.get(pos1) : pos1;
- int num2 = map.containsKey(pos2) ? map.get(pos2) : pos2;
- map.put(pos1, num2);
- map.put(pos2, num1);
- }
- Item[] a = new Item[map.size()];
- int n = 0;
- for (Map.Entry<Integer, Integer> e : map.entrySet()) {
- a[n++] = new Item(e.getKey(), e.getValue());
- }
- int[] b = new int[n];
- for (int i = 0; i < n; i++) {
- b[i] = a[i].val;
- }
- compress(b);
- long ans = 0;
- FenwickTree tree = new FenwickTree(n);
- for (int i = 0; i < n; i++) {
- ans += tree.sum(b[i], n - 1);
- tree.inc(b[i]);
- }
- for (int idxAfter = 0; idxAfter < n; idxAfter++) {
- int idxBefore = ~Arrays.binarySearch(a, new Item(a[idxAfter].val, -1));
- ans += Math.abs(a[idxAfter].pos - a[idxBefore].pos);
- ans -= Math.abs(idxAfter - idxBefore);
- }
- out.printLine(ans);
- }
- private void compress(int[] a) {
- TreeSet<Integer> set = new TreeSet<Integer>();
- for (int x : a) {
- set.add(x);
- }
- TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
- for (int x : set) {
- int id = map.size();
- map.put(x, id);
- }
- for (int i = 0; i < a.length; i++) {
- a[i] = map.get(a[i]);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement