fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long MOD = 1e9 + 7;
  21. const int N = 5e5 + 7;
  22. int a[N] , n , BIT_n[N] , L[N] , R[N];
  23. long long BIT[N];
  24.  
  25. void inp(){
  26.     cin >> n;
  27.     for (int i = 1 ; i <= n ; ++i){
  28.         cin >> a[i];
  29.     }
  30. }
  31.  
  32. void update(int x , long long val){
  33.     while (x <= n){
  34.         BIT[x] += val;
  35.         x += x & -x;
  36.     }
  37. }
  38.  
  39. long long get(int x){
  40.     long long res = 0;
  41.     while (x > 0){
  42.         res += BIT[x];
  43.         x -= x & -x;
  44.     }
  45.  
  46.     return res;
  47. }
  48.  
  49. void update_n(int x , int val){
  50.     while (x > 0){
  51.         BIT_n[x] += val;
  52.         x -= x & -x;
  53.     }
  54. }
  55.  
  56. int get_n(int x){
  57.     int res = 0;
  58.     while (x <= n){
  59.         res += BIT_n[x];
  60.         x += x & -x;
  61.     }
  62.  
  63.     return res;
  64. }
  65.  
  66. void ktao(){
  67.     for (int i = 1 ; i <= n ; ++i){
  68.         L[i] = get(a[i]);
  69.         update(a[i] , 1);
  70.     }
  71.  
  72.     for (int i = n ; i >= 1 ; --i){
  73.         R[i] = get_n(a[i]);
  74.         update_n(a[i] , 1);
  75.     }
  76. }
  77.  
  78. void solve(){
  79.     ktao();
  80.     memset(BIT , 0 , sizeof BIT);
  81.  
  82.     long long res = 0;
  83.     for (int i = 1 ; i <= n ; ++i){
  84.         long long tmp = ((1LL * L[i]) * (1LL * L[i] - 1LL)) / 2;
  85.         tmp -= get(a[i]);
  86.         update(a[i] , L[i]);
  87.  
  88.         res += tmp * (1LL * R[i]);
  89.         res %= MOD;
  90.     }
  91.     cout << res;
  92. }
  93.  
  94. int main(){
  95. //    freopen("difmax.inp" , "r" , stdin);
  96. //    freopen("difmax.out" , "w" , stdout);
  97.     faster;
  98.     inp();
  99.     solve();
  100.     return 0;
  101. }
  102.  
  103.  
Success #stdin #stdout 0.01s 7840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/meE7Nv
language:
C++14 (gcc 8.3)
created:
7 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!