SHARE
TWEET

ddd

a guest Feb 14th, 2017 150 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.io.OutputStream;
  3. import java.io.IOException;
  4. import java.io.InputStream;
  5. import java.io.OutputStream;
  6. import java.io.PrintWriter;
  7. import java.io.BufferedWriter;
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10. import java.util.ArrayList;
  11. import java.util.StringTokenizer;
  12. import java.io.Writer;
  13. import java.io.OutputStreamWriter;
  14. import java.io.BufferedReader;
  15. import java.io.InputStream;
  16.  
  17. /**
  18.  * Built using CHelper plug-in
  19.  * Actual solution is at the top
  20.  */
  21. public class Main {
  22.     public static void main(String[] args) {
  23.         InputStream inputStream = System.in;
  24.         OutputStream outputStream = System.out;
  25.         InputReader in = new InputReader(inputStream);
  26.         OutputWriter out = new OutputWriter(outputStream);
  27.         friendcross solver = new friendcross();
  28.         solver.solve(1, in, out);
  29.         out.close();
  30.     }
  31.  
  32.     static class friendcross {
  33.         public int[] arr;
  34.         public int[] brr;
  35.         public static int[] seq;
  36.  
  37.         public void solve(int testNumber, InputReader in, OutputWriter out) {
  38.             int n = in.nextInt(), k = in.nextInt();
  39.             arr = in.readIntArray(n);
  40.             brr = in.readIntArray(n);
  41.             int[] ra = new int[n + 1];
  42.             int[] rb = new int[n + 1];
  43.             for (int i = 0; i < n; i++) {
  44.                 ra[arr[i]] = i + 1;
  45.                 rb[brr[i]] = i + 1;
  46.             }
  47.  
  48.             seq = new int[n + 1];
  49.             for (int i = 1; i <= n; i++) {
  50.                 seq[ra[i]] = rb[i];
  51.             }
  52.             friendcross.SegmentTree root = new friendcross.SegmentTree(1, n);
  53.             ArrayList<friendcross.Event>[] events = new ArrayList[n + 1];
  54.             for (int i = 0; i <= n; i++) events[i] = new ArrayList<>();
  55.             for (int i = 1; i <= n; i++) {
  56.                 int up = Math.min(n, i + k);
  57.                 int down = Math.max(0, i - k - 1);
  58.                 events[up].add(new friendcross.Event(i, +1));
  59.                 events[down].add(new friendcross.Event(i, -1));
  60.             }
  61.             long tinv = 0;
  62.             BIT x = new BIT(n);
  63.             for (int i = 1; i <= n; i++) {
  64.                 x.update(seq[i], +1);
  65.                 tinv += i - x.query(seq[i]);
  66.             }
  67.             long res = 0;
  68.             for (int cow = 1; cow <= n; cow++) {
  69.                 root.update(ra[cow], +1);
  70.                 for (friendcross.Event e : events[cow])
  71.                     res += e.sign * root.query(1, ra[e.cow], rb[e.cow]);
  72.             }
  73.             out.println(tinv - res);
  74.         }
  75.  
  76.         static class Event {
  77.             public int cow;
  78.             public int sign;
  79.  
  80.             public Event(int cow, int sign) {
  81.                 this.cow = cow;
  82.                 this.sign = sign;
  83.             }
  84.  
  85.         }
  86.  
  87.         static class SegmentTree {
  88.             public int[] arr;
  89.             public int[] pl;
  90.             public int[] pr;
  91.             public BIT bit;
  92.             public int start;
  93.             public int end;
  94.             public friendcross.SegmentTree lchild;
  95.             public friendcross.SegmentTree rchild;
  96.  
  97.             public SegmentTree(int start, int end) {
  98.                 this.start = start;
  99.                 this.end = end;
  100.                 arr = new int[end - start + 2];
  101.                 if (start == end) {
  102.                     arr[1] = seq[start];
  103.                 } else {
  104.                     int mid = (start + end) >> 1;
  105.                     lchild = new friendcross.SegmentTree(start, mid);
  106.                     rchild = new friendcross.SegmentTree(mid + 1, end);
  107.                     pl = new int[lchild.arr.length];
  108.                     pr = new int[rchild.arr.length];
  109.                     int lidx = 1, ridx = 1;
  110.  
  111.                     int idx = 1;
  112.                     int[] larr = lchild.arr, rarr = rchild.arr;
  113.                     while (lidx < larr.length && ridx < rarr.length) {
  114.                         if (larr[lidx] < rarr[ridx]) {
  115.                             pl[lidx] = idx;
  116.                             arr[idx++] = larr[lidx++];
  117.                         } else {
  118.                             pr[ridx] = idx;
  119.                             arr[idx++] = rarr[ridx++];
  120.                         }
  121.                     }
  122.                     while (lidx < larr.length) {
  123.                         pl[lidx] = idx;
  124.                         arr[idx++] = larr[lidx++];
  125.                     }
  126.                     while (ridx < rarr.length) {
  127.                         pr[ridx] = idx;
  128.                         arr[idx++] = rarr[ridx++];
  129.                     }
  130.                 }
  131.                 bit = new BIT(end - start + 2);
  132.             }
  133.  
  134.             public int query(int s, int e, int k) {
  135.                 if (start == s && end == e) {
  136.                     if (k < arr[1]) return bit.count;
  137.                     int lo = 1, hi = arr.length - 1;
  138.                     while (lo < hi) {
  139.                         int mid = (lo + hi + 1) / 2;
  140.                         if (arr[mid] > k) hi = mid - 1;
  141.                         else lo = mid;
  142.                     }
  143.                     return bit.count - bit.query(lo);
  144.                 }
  145.                 int mid = (start + end) >> 1;
  146.                 if (mid >= e) return lchild.query(s, e, k);
  147.                 else if (mid < s) return rchild.query(s, e, k);
  148.                 else return lchild.query(s, mid, k) + rchild.query(mid + 1, e, k);
  149.             }
  150.  
  151.             public int update(int p, int val) {
  152.                 if (start == p && end == p) {
  153.                     bit.update(1, +1);
  154.                     return 1;
  155.                 }
  156.                 int mid = (start + end) >> 1;
  157.                 int apos = -1;
  158.                 if (mid >= p) apos = pl[lchild.update(p, val)];
  159.                 else apos = pr[rchild.update(p, val)];
  160.                 bit.update(apos, +1);
  161.                 return apos;
  162.             }
  163.  
  164.         }
  165.  
  166.     }
  167.  
  168.     static class InputReader {
  169.         public BufferedReader reader;
  170.         public StringTokenizer tokenizer;
  171.  
  172.         public InputReader(InputStream stream) {
  173.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  174.             tokenizer = null;
  175.         }
  176.  
  177.         public String next() {
  178.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  179.                 try {
  180.                     tokenizer = new StringTokenizer(reader.readLine());
  181.                 } catch (IOException e) {
  182.                     throw new RuntimeException(e);
  183.                 }
  184.             }
  185.             return tokenizer.nextToken();
  186.         }
  187.  
  188.         public int[] readIntArray(int tokens) {
  189.             int[] ret = new int[tokens];
  190.             for (int i = 0; i < tokens; i++) {
  191.                 ret[i] = nextInt();
  192.             }
  193.             return ret;
  194.         }
  195.  
  196.         public int nextInt() {
  197.             return Integer.parseInt(next());
  198.         }
  199.  
  200.     }
  201.  
  202.     static class BIT {
  203.         private int[] tree;
  204.         private int N;
  205.         public int count;
  206.  
  207.         public BIT(int N) {
  208.             this.N = N;
  209.             this.tree = new int[N + 1];
  210.             this.count = 0;
  211.         }
  212.  
  213.         public int query(int K) {
  214.             int sum = 0;
  215.             for (int i = K; i > 0; i -= (i & -i))
  216.                 sum += tree[i];
  217.             return sum;
  218.         }
  219.  
  220.         public void update(int K, int val) {
  221.             this.count += val;
  222.             for (int i = K; i <= N; i += (i & -i))
  223.                 tree[i] += val;
  224.         }
  225.  
  226.     }
  227.  
  228.     static class OutputWriter {
  229.         private final PrintWriter writer;
  230.  
  231.         public OutputWriter(OutputStream outputStream) {
  232.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  233.         }
  234.  
  235.         public OutputWriter(Writer writer) {
  236.             this.writer = new PrintWriter(writer);
  237.         }
  238.  
  239.         public void close() {
  240.             writer.close();
  241.         }
  242.  
  243.         public void println(long i) {
  244.             writer.println(i);
  245.         }
  246.  
  247.     }
  248. }
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