fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=6e4+5;
  4. int A[N],sum[N];
  5. int binary(int l,int r,int a,int n)
  6. {
  7.     if(a>A[n-1]) return n;
  8.     if(l==r) return l;
  9.     int mid=(l+r)/2;
  10.     if(a>A[mid]) return binary(mid+1,r,a,n);
  11.     return binary(l,mid,a,n);
  12. }
  13. int cnt(int l,int r)
  14. {
  15.     if(l==r) return 0;
  16.     int pro=0;
  17.     int mid=(l+r)/2;
  18.     for(int a=mid+1;a<=r;a++){
  19.         A[a-mid-1]=sum[a];
  20.     }
  21.     sort(A,A+r-mid);
  22.     for(int a=l;a<=mid;a++){
  23.         pro+=binary(0,r-mid-1,sum[a],r-mid);
  24.     }
  25.     for(int a=0;a<r-mid;a++){
  26.         A[a]=0;
  27.     }
  28.     return pro+cnt(l,mid)+cnt(mid+1,r);
  29. }
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(0);
  34.     cout.tie(0);
  35.     int n;
  36.     cin>>n;
  37.     for(int a=0;a<n;a++){
  38.         cin>>sum[a];
  39.     }
  40.     cout<<cnt(0,n-1);
  41. }
  42.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/L9pFvj
language:
C++14 (gcc 8.3)
created:
3 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!