fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //ntm
  5.  
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define umap unordered_map
  10. #define prq priority_queue
  11.  
  12. #define yeu_bong ios_base::sync_with_stdio(false);cin.tie(NULL);
  13.  
  14. #define vect vector
  15. #define bend(v) v.begin(),v.end()
  16. #define pob pop_back
  17. #define lwb lower_bound
  18. #define upb upper_bound
  19. #define pii pair<int,int>
  20. #define int long long
  21. #define dbl long double
  22. typedef pair<double, double> pdd;
  23.  
  24. const int INF=1e18;
  25. const int MaxN=3e5;
  26. const int MOD1=1e9+7;
  27. const int MOD2=1e9+9;
  28. const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
  29. const int base=311;
  30. const int OFFSET=1e9;
  31.  
  32.  
  33. int n;
  34. int a[MaxN+1];
  35. vect<int>v;
  36. int st[4*MaxN+1];
  37.  
  38. int lLess[MaxN+1],lGreater[MaxN+1],lEqual[MaxN+1];
  39. int rLess[MaxN+1],rGreater[MaxN+1],rEqual[MaxN+1];
  40.  
  41. void update(int id,int l,int r,int pos){
  42.     if(l==r){
  43.         st[id]++;
  44.         return;
  45.     }
  46.     int m=l+(r-l)/2;
  47.     if(pos<=m)update(2*id,l,m,pos);
  48.     else update(2*id+1,m+1,r,pos);
  49.     st[id]=st[2*id]+st[2*id+1];
  50. }
  51.  
  52. int query(int id,int tl,int tr,int l,int r){
  53.     if(tl>r||tr<l)return 0;
  54.     if(l<=tl&&tr<=r)return st[id];
  55.     int m=tl+(tr-tl)/2;
  56.     return query(2*id,tl,m,l,r)+query(2*id+1,m+1,tr,l,r);
  57. }
  58.  
  59. void optimize(){
  60.     sort(bend(v));
  61.     v.resize(unique(bend(v))-v.begin());
  62.     for(int i=1;i<=n;i++)a[i]=lwb(bend(v),a[i])-v.begin()+1;
  63. }
  64.  
  65. void reset(){
  66.     memset(st,0,sizeof st);
  67. }
  68.  
  69. void sol(){
  70.     cin>>n;
  71.     for(int i=1;i<=n;i++){
  72.         cin>>a[i];
  73.         v.pb(a[i]);
  74.     }
  75.     optimize();
  76.     int m=v.size();
  77.     reset();
  78.     for(int i=1;i<=n;i++){
  79.         lLess[i]=query(1,1,m,1,a[i]-1);
  80.         lGreater[i]=query(1,1,m,a[i]+1,m);
  81.         lEqual[i]=i-1-lLess[i]-lGreater[i];
  82.         update(1,1,m,a[i]);
  83.     }
  84.     reset();
  85.     for(int i=n;i>=1;i--){
  86.         rLess[i]=query(1,1,m,1,a[i]-1);
  87.         rGreater[i]=query(1,1,m,a[i]+1,m);
  88.         rEqual[i]=n-i-rLess[i]-rGreater[i];
  89.         update(1,1,m,a[i]);
  90.     }
  91.     int res=0;
  92.     for(int i=1;i<=n;i++){
  93.         res+=lLess[i]*rLess[i];
  94.         res+=lLess[i]*rEqual[i];
  95.         res+=lEqual[i]*rLess[i];
  96.         res+=lEqual[i]*rEqual[i];
  97.         res+=lGreater[i]*rGreater[i];
  98.         res+=lEqual[i]*rGreater[i];
  99.         res+=lGreater[i]*rEqual[i];
  100.     }
  101.     cout<<res<<'\n';
  102. }
  103.  
  104.  
  105. void ffopen(const string& file){
  106.     if(file.empty()) return;
  107.     freopen((file+".inp").c_str(),"r",stdin);
  108.     freopen((file+".out").c_str(),"w",stdout);
  109. }
  110.  
  111. signed main(){
  112.     yeu_bong;
  113.     ffopen("");
  114.     int t=1;
  115.     while(t--) sol();
  116. }
  117.  
Success #stdin #stdout 0.01s 15840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/SM6dnd
language:
C++14 (gcc 8.3)
created:
5 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!