Facebook
From Gruff Panda, 7 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 315
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. int *tab, *tab2, K = 0;
  5.  
  6. long long int merge(int start_1, int koniec_1, int start_2, int koniec_2){
  7.       long long int inwersje = 0;
  8.  
  9.       for(int i = start_1; i <= koniec_2; i++){
  10.               tab2[i] = tab[i];
  11.       }
  12.  
  13.       int i = start_1;
  14.       int j = start_2;
  15.       int k = start_1;
  16.       int l = start_1;
  17.  
  18.       while(i <= koniec_1 && j <= koniec_2){
  19.               while(tab2[l] + K >= tab2[j] && l <= koniec_1){
  20.                       l++;
  21.               }
  22.               if(tab2[i] <= tab2[j]){
  23.                       tab[k++] = tab2[j++];
  24.                       inwersje += (koniec_1 - l + 1);
  25.  
  26.               }else{
  27.                       tab[k++] = tab2[i++];
  28.               }
  29.       }
  30.  
  31.       while(i <= koniec_1){
  32.               tab[k++] = tab2[i++];
  33.       }
  34.  
  35.       while(j <= koniec_2){
  36.               tab[k++] = tab2[j++];
  37.       }
  38.  
  39.       return inwersje;
  40. }
  41.  
  42. long long int merge_sort(int start, int koniec){
  43.       if(start < koniec){
  44.               int m = (start + koniec) / 2;
  45.  
  46.               long long int a = merge_sort(start, m);
  47.               long long int b = merge_sort(m + 1, koniec);
  48.  
  49.               long long int c = merge(start, m, m + 1, koniec);
  50.  
  51.               return a + b + c;
  52.       }
  53.       return (long long int)(0);
  54. }
  55.  
  56. int main(){
  57.       ios_base::sync_with_stdio(false);
  58.       int z;
  59.       cin >> z;
  60.  
  61.       while(z--){
  62.               int n;
  63.               cin >> n >> K;
  64.  
  65.               tab = new int[n + 1];
  66.               tab2 = new int[n + 1];
  67.  
  68.               for(int i = 1; i <= n; i++){
  69.                       cin >> tab[i];
  70.               }
  71.  
  72.               cout << merge_sort(1, n) << endl;
  73.  
  74.               delete [] tab;
  75.               delete [] tab2;
  76.       }
  77.       return 0;
  78. }