Advertisement
Guest User

Untitled

a guest
Mar 24th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll  _mergeSort(ll arr[], ll temp[], ll left, ll right);
  5. ll merge(ll arr[], ll temp[], ll left, ll mid, ll right);
  6. ll mergeSort(ll arr[], ll array_size)
  7. {
  8.     ll *temp = (ll *)malloc(sizeof(ll)*array_size);
  9.     return _mergeSort(arr, temp, 0, array_size - 1);
  10. }
  11. ll _mergeSort(ll arr[], ll temp[], ll left, ll right)
  12. {
  13.   ll mid, inv_count = 0;
  14.   if (right > left)
  15.   {
  16.     mid = (right + left)/2;
  17.     inv_count  = _mergeSort(arr, temp, left, mid);
  18.     inv_count += _mergeSort(arr, temp, mid+1, right);
  19.     inv_count += merge(arr, temp, left, mid+1, right);
  20.   }
  21.   return inv_count;
  22. }
  23. ll merge(ll arr[], ll temp[], ll left, ll mid, ll right)
  24. {
  25.   ll i, j, k;
  26.   ll inv_count = 0;
  27.   i = left;
  28.   j = mid;
  29.   k = left;
  30.   while ((i <= mid - 1) && (j <= right))
  31.   {
  32.     if (arr[i] <= arr[j])
  33.     {
  34.       temp[k++] = arr[i++];
  35.     }
  36.     else
  37.     {
  38.       temp[k++] = arr[j++];
  39.       inv_count = inv_count + (mid - i);
  40.     }
  41.   }
  42.   while (i <= mid - 1)
  43.     temp[k++] = arr[i++];
  44.   while (j <= right)
  45.     temp[k++] = arr[j++];
  46.   for (i=left; i <= right; i++)
  47.     arr[i] = temp[i];
  48.  
  49.   return inv_count;
  50. }
  51. ll x[100009],V[100009];
  52. ll F[100009];
  53. main(){
  54.     ll n, w;
  55.     cin >> n >> w;
  56.     vector<pair<double,double> > v;
  57.     for(ll i = 0; i < n; i++){
  58.         cin >> x[i] >> V[i];
  59.         double L = 1.0* (-w)/x[i] + 1.0*V[i]/x[i];
  60.         double R = 1.0* w/x[i] + 1.0*V[i]/x[i];
  61.         v.push_back({L,-R});
  62.     }
  63.     sort(v.begin(),v.end());
  64.     vector<pair<double,ll> > R;
  65.     for (ll i = 0; i < v.size(); i++)
  66.        {
  67.         R.push_back({-v[i].second,-i});
  68.         //cout <<v[i].first <<" "<<-v[i].second<<endl;
  69.         }
  70.     sort(R.begin(),R.end());
  71.     ll cnt = 0;
  72.     for (ll i = 0; i < R.size(); i++)
  73.     {
  74.  
  75.          cnt++;
  76.         // cout << R[i].first<<"    "<<R[i].second<<" "<<cnt<<endl;
  77.         F[-R[i].second] = cnt;
  78.  
  79.     }
  80.    // for (ll i =0 ; i < n; i++)
  81.    // cout <<F[i]<<" ";
  82.     cout << mergeSort(F,n) << endl;
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement