fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define iii pair<pair<int , int> , int>
  11. #define db double
  12. #define onBit(mask , i) (mask | (1 << i))
  13. #define offBit(mask , i) (mask & (~(1 << i)))
  14.  
  15. const long long MOD = 1e9 + 7;
  16. const int INF = 8e7;
  17. const int N = 3e5 + 7;
  18. int BIT_a[N] , BIT_b[N] , n;
  19.  
  20. struct gv{
  21.     int val , id;
  22. };
  23.  
  24. gv a[N] , b[N];
  25.  
  26. bool cmp(gv x , gv y){
  27.     if (x.val == y.val) return x.id < y.id;
  28.     return x.val < y.val;
  29. }
  30.  
  31. void inp(){
  32.     cin >> n;
  33.     for (int i = 1 ; i <= n ; ++i){
  34.         cin >> a[i].val;
  35.         a[i].id = i;
  36.     }
  37.     for (int i = 1 ; i <= n ; ++i){
  38.         cin >> b[i].val;
  39.         b[i].id = i;
  40.     }
  41.     sort(a + 1 , a + n + 1 , cmp);
  42.     sort(b + 1 , b + n + 1 , cmp);
  43. }
  44.  
  45. void update_a(int x , int val){
  46.     while (x <= n){
  47.         BIT_a[x] += val;
  48.         x += x & -x;
  49.     }
  50. }
  51.  
  52. int get_a(int x){
  53.     int res = 0;
  54.     while (x > 0){
  55.         res += BIT_a[x];
  56.         x -= x & -x;
  57.     }
  58.     return res;
  59. }
  60.  
  61. void update_b(int x , int val){
  62.     while (x <= n){
  63.         BIT_b[x] += val;
  64.         x += x & -x;
  65.     }
  66. }
  67.  
  68. int get_b(int x){
  69.     int res = 0;
  70.     while (x > 0){
  71.         res += BIT_b[x];
  72.         x -= x & -x;
  73.     }
  74.     return res;
  75. }
  76.  
  77. void solve(){
  78.     long long res = 0;
  79.     for (int i = 1 ; i <= n ; ++i){
  80.         int tmp1 = get_a(a[i].id) , tmp2 = get_b(b[i].id);
  81.         update_a(a[i].id ,  1);
  82.         update_b(b[i].id ,  1);
  83.         a[i].id -= tmp1;
  84.         b[i].id -= tmp2;
  85.         res += abs(a[i].id - b[i].id);
  86.     }
  87.     cout << res;
  88. }
  89.  
  90. int main(){
  91. //    freopen("xhmax.inp" , "r" , stdin);
  92. //    freopen("xhmax.out" , "w" , stdout);
  93.     faster;
  94.     inp();
  95.     solve();
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0jjGNn
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!