fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define deb(x) cout<<#x<<" "<<x<"\n"
  5. #define mod 1000000007
  6.  
  7. ll mergeArray(ll *a, int low, int high)
  8. {
  9.     int mid=(low+high);
  10.     int i=low,k=low;
  11.     int j=mid+1;
  12.  
  13.     ll temp[100005];
  14.     ll alphaScore=0;
  15.     while((i<=mid) && (j<=high))
  16.     {
  17.         if(a[i]<a[j])
  18.         {
  19.             alphaScore=(alphaScore%mod+((high-j+1)*a[i])%mod)%mod;
  20.             temp[k++]=a[i++];
  21.         }
  22.         else
  23.         {
  24.             temp[k++]=a[j++];
  25.         }
  26.     }
  27.  
  28.     while(i<=mid)
  29.         temp[k++]=a[i++];
  30.     while(j<=high)
  31.         temp[k++]=a[j++];
  32.     for(int i=low;i<=high;i++)
  33.         a[i]=temp[i];
  34.     return alphaScore;
  35. }
  36.  
  37.  
  38. ll mergeSort(ll *a, int low, int high)
  39. {
  40.     ll alphaScore=0;
  41.     if(high>low)
  42.     {
  43.         int mid=(low+high)/2;
  44.         alphaScore=mergeSort(a,0,mid);
  45.         alphaScore=(alphaScore+ mergeSort(a,mid+1,high))%mod;
  46.         alphaScore=(alphaScore+mergeArray(a,low,high))%mod;
  47.  
  48.     }
  49.     else
  50.         return alphaScore;
  51. }
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(false);
  55.     cin.tie(NULL);
  56.     int n,i;
  57.     cin>>n;
  58.     ll a[n];
  59.     for(i=0;i<n;i++)
  60.         cin>>a[i];
  61.     cout<<mergeSort(a,0,n-1);
  62.     return 0;
  63. }
  64.  
Runtime error #stdin #stdout 0s 4428KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/onaNpd
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!