fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FASTIO          ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  4.  
  5. #define ftmx            100005
  6.  
  7. int ft[ftmx];
  8. void update(int i, int add)
  9. {
  10.     while(i>0 && i<ftmx){
  11.         ft[i] += add;
  12.         i += (i&(-i));
  13.     }
  14. }
  15.  
  16. int sum(int i)
  17. {
  18.     int s = 0;
  19.     while(i>0){
  20.         s += ft[i];
  21.         i -= (i&(-i));
  22.     }
  23.     return s;
  24. }
  25.  
  26. int sumlr(int l, int r){
  27.     return sum(r) - sum(l-1);
  28. }
  29.  
  30.  
  31. signed main()
  32. {
  33.     FASTIO
  34.  
  35.     int n;
  36.     cin>>n;
  37.  
  38.     int a[n+1];
  39.     for(int i=1; i<=n; i++){
  40.         cin>>a[i];
  41.     }
  42.  
  43.     long long ans = 0, mx = 1e5 + 1;
  44.     for(int i=1; i<=n; i++){
  45.         ans += sumlr(a[i]+1, mx);
  46.         update(a[i], 1);
  47.     }
  48.  
  49.     cout<<ans<<endl;
  50. }
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
Success #stdin #stdout 0s 5640KB
comments (?)
stdin
copy 
5
2 3 6 5 4
stdout
copy 
3
https://ideone.com/KG82oX
language:
C++14 (gcc 8.3)
created:
2 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!