SHARE
TWEET

Untitled

a guest Feb 14th, 2017 237 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 2e5+5;
  5.  
  6. const int size = (1<<24); // ~190mb
  7. long long a[size];
  8. int b[size];
  9. int n;
  10.  
  11. inline long long h(int x, int y){ return (1ll*maxn*x+y)*7; }
  12.  
  13. void h_inc(int x, int y){
  14.     long long t = h(x, y);
  15.     int k = t % size;
  16.     while(a[k] != -1 && a[k] != t) k = (k+1) % size;
  17.     a[k] = t, b[k]++;
  18. }
  19.  
  20. int h_get(int x, int y){
  21.     long long t = h(x, y);
  22.     int k = t % size;
  23.     while(a[k] != -1){
  24.         if(a[k] == t) return b[k];
  25.         k = (k+1) % size;
  26.     }
  27.     return 0;
  28. }
  29.  
  30. int sum(int r1, int r2){
  31.     int ans = 0;
  32.     for(int i = r1; i >= 0; i = (i&(i+1))-1)
  33.         for(int j = r2; j >= 0; j = (j&(j+1))-1)
  34.             ans += h_get(i, j);
  35.     return ans;
  36. }
  37.  
  38. int sum(int l1, int r1, int l2, int r2){
  39.     l2 = min(l2, n-1);
  40.     r2 = min(r2, n-1);
  41.     if(l1 > l2 || r1 > r2) return 0;
  42.     return sum(l2, r2) - sum(l1-1, r2) - sum(l2, r1-1) + sum(l1-1, r1-1);
  43. }
  44.  
  45. void add(int k1, int k2){
  46.     for(int i = k1; i < n; i = (i|(i+1)))
  47.         for(int j = k2; j < n; j = (j|(j+1)))
  48.             h_inc(i, j);
  49. }
  50.  
  51. int a_[maxn], b_[maxn], _a[maxn], _b[maxn];
  52.  
  53. int main(){
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.  
  57.     memset(a, -1, sizeof(a));
  58.  
  59.     freopen("friendcross.in", "r", stdin);
  60.     freopen("friendcross.out", "w", stdout);
  61.  
  62.     int k;
  63.     cin >> n >> k;
  64.  
  65.     for(int i = 0; i < n; i++){
  66.         cin >> a_[i];
  67.         a_[i]--;
  68.         _a[a_[i]] = i;
  69.     }
  70.  
  71.     for(int i = 0; i < n; i++){
  72.         cin >> b_[i];
  73.         b_[i]--;
  74.         _b[b_[i]] = i;
  75.     }
  76.  
  77.     long long ans = 0;
  78.  
  79.     for(int i = 0; i < n; i++){
  80.         int t = a_[i];
  81.         int x = _b[t];
  82.         ans += sum(0, x+1, t-k-1, n-1) + sum(t+k+1, x+1, n-1, n-1);
  83.         add(t, x);
  84.     }
  85.  
  86.     cout << ans;
  87.  
  88.     return 0;
  89. }
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