fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int , int> pi;
  6. typedef pair<double , int > dpi;
  7. typedef pair<long long , long long> pll;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef vector<pi> vpi;
  11. typedef unsigned long long ull;
  12. #define MP  make_pair
  13. #define mem(a , v)  memset(a , v , sizeof(a))
  14. #define all(v)	((v).begin()), ((v).end())
  15. #define sc(a) scanf("%d",&a)
  16. #define scl(a) scanf("%lld",&a)
  17. #define scd(a) scanf("%lf" , &a)
  18. #define sch(a) scanf("%c" , &a)
  19. #define blank printf("\n")
  20. #define pla printf("plapla\n")
  21. #define pb push_back
  22. #define INF 1e9
  23. #define EPS 1e-9
  24. vector<int> months = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  25. const int MAX = 1e6+55;
  26. const int inf = 1e9+77;
  27. const int MOD = 1e9+7;
  28. const double PI = acos(-1.0);
  29. const double eps = 1e-7;
  30.  
  31. int n;
  32. pi a[MAX];
  33. int tree[4*MAX];
  34. int _left[MAX] , _right[MAX];
  35.  
  36. void update(int p , int st , int en , int loc){
  37.     if(st > loc || en < loc)
  38.         return;
  39.     if(st == en){
  40.         tree[p] = 1;
  41.         return;
  42.     }
  43.     int md = (st+en)>>1;
  44.     update(p * 2  ,st , md , loc);
  45.     update(p * 2 + 1 , md + 1 ,en , loc);
  46.     tree[p] = tree[p*2] + tree[p*2+1];
  47. }
  48.  
  49. int qwr(int p , int st , int en , int l , int r){
  50.     if(st > r || en < l)
  51.         return 0;
  52.     if(st >= l && en <= r)
  53.         return tree[p];
  54.     int md = (st+en)>>1;
  55.     return qwr(p * 2 , st , md , l , r) + qwr(p * 2 + 1 , md + 1 , en , l , r);
  56. }
  57.  
  58. int main(){
  59. //freopen("output.txt" , "w" , stdout);
  60. //freopen("input.txt" , "r" , stdin);
  61.  
  62.     sc(n);
  63.     for(int i = 0 ; i < n ; ++i){
  64.         sc(a[i].first);
  65.         a[i].second = i;
  66.     }
  67.     sort(a , a + n);
  68.     _right[0] = 0;
  69.     update(1 , 0 , n - 1 , a[0].second);
  70.     for(int i = 1 ; i < n ; ++i){
  71.         if(a[i].second < n - 1)
  72.             _right[i] = qwr(1 , 0 , n - 1 , a[i].second + 1 , n - 1);
  73.         else
  74.             _right[i] = 0;
  75.         update(1 , 0 , n - 1 , a[i].second);
  76.     }
  77.  
  78.     mem(tree , 0);
  79.     reverse(a , a + n);
  80.     _left[0] = 0;
  81.     update(1 , 0 , n - 1 , a[0].second);
  82.     for(int i = 1 ; i < n ; ++i){
  83.         if(a[i].second){
  84.             _left[i] = qwr(1 , 0 , n - 1 , 0 , a[i].second - 1);
  85.         }
  86.         else
  87.             _left[i] = 0;
  88.         update(1 , 0 , n - 1 , a[i].second);
  89.     }
  90.     reverse(_left , _left + n);
  91.  
  92.     ll res = 0;
  93.     for(int i = 1 ; i < n ; ++i){
  94.         res += (ll)_left[i] * (ll)_right[i];
  95.     }
  96.     printf("%I64d" , res);
  97.  
  98.  
  99.  
  100. return 0;
  101. }
  102.  
Success #stdin #stdout 0s 46488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
                                                               0
https://ideone.com/sG31aS
language:
C++14 (gcc 8.3)
created:
4 years 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!