fork download
copy 
  1. /*author - Ashutosh Chitranshi*/
  2. #include<bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #pragma GCC push_options
  9. #pragma GCC optimize ("unroll-loops")
  10. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  11. #define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
  12. #define pow2(x) ((x)*(x))
  13. #define max3(a,b,c) max(a,max(b,c))
  14. #define min3(a,b,c) min(a,min(b,c))
  15. #define ll long long
  16. #define ld long double
  17. #define eb emplace_back
  18. #define pb push_back
  19. #define pf push_front
  20. #define mod 1000000007
  21. #define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
  22. #define mp make_pair
  23. #define ff first
  24. #define ss second
  25. #define null NULL
  26. #define all(c) (c).begin(),(c).end()
  27. #define nl "\n"
  28. typedef vector<int> vi;
  29. typedef vector<ll> vl;
  30. typedef vector< vi > vvi;
  31. typedef vector< vl > vvl;
  32. typedef pair< int,int > ii;
  33. typedef pair< ll,ll> pll;
  34. typedef map< ll,ll> mll;
  35. typedef map< int,int> mii;
  36. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     ll n;
  43.     cin >> n;
  44.     ll ar[n];
  45.     for (int i=0;i<n;i++) cin >> ar[i];
  46.     ordered_set s;
  47.     ll ans = 0ll;
  48.     for (int i=0;i<n;i++) {
  49.         ll smallerElementTillNow = s.order_of_key(ar[i]);
  50.         ll currAns = (ar[i]*(ar[i] - 1))/2 - (smallerElementTillNow*(smallerElementTillNow+1))/2;
  51.         ans += currAns;
  52.         s.insert(ar[i]);
  53.     }
  54.     cout << ans << "\n";
  55.     return 0;
  56. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
2
1 2
stdout
copy 
0
https://ideone.com/B53dpY
language:
C++14 (gcc 8.3)
created:
3 hours 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!