Emiliatan

a457

Feb 23rd, 2019
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. /* a457             */
  2. /* AC (38ms, 1.2MB) */
  3. #include <cstdio>
  4. #include <algorithm>
  5. #define S first
  6. #define R second
  7. using namespace std;
  8. const int MAXN = 100001;
  9. typedef long long int64;
  10. pair <int, int> obj[MAXN];
  11. int b[MAXN];
  12. int k, m;
  13. int64 merge_sort(int l, int r)
  14. {
  15.     int64 res = 0;
  16.     if(l < r)
  17.     {
  18.         int mid = (l + r) >> 1;
  19.         res = merge_sort(l, mid) + merge_sort(mid + 1, r);
  20.         for(int i = l, j = mid + 1, k = l; i <= mid || j <= r; k++)
  21.             if(j == r + 1 || i <= mid && obj[i].R <= obj[j].R) b[k] = obj[i++].R;
  22.             else
  23.             {
  24.                 b[k] = obj[j++].R;
  25.                 res += mid - i + 1;
  26.             }
  27.         for(int i = l; i <= r; i++) obj[i].R = b[i];
  28.     }
  29.     return res;
  30. }
  31. int main()
  32. {
  33.     scanf("%d %d", &k, &m);
  34.     for(int i = 0; i < k; i++) scanf("%d", &obj[i].S);
  35.     for(int i = 0; i < k; i++) scanf("%d", &obj[i].R);
  36.     sort(obj, obj + k);
  37.     printf("%lld", merge_sort(0, k - 1));
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment