fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i , l , r) for(int i = l ; i <= r ; ++i)
  3. #define FORD(i , r , l) for(int i = r ; i >= l ; --i)
  4. #define ll long long
  5. using namespace std;
  6. const int N = 1e5;
  7. int n,a[N + 3];
  8. ll ans;
  9. namespace sub1{
  10.     void solve(){
  11.         FOR(i , 1 , n)
  12.             FOR(j , i + 1 , n)
  13.                 FOR(k , j + 1 , n)
  14.                     if(a[i] < a[j] && a[j] < a[k]) ans++;
  15.         cout << ans;
  16.     }
  17. }
  18. namespace sub2{
  19.     int cnt[1003];
  20.     void solve(){
  21.         FOR(j , 1 , n)
  22.             FOR(i , 1 , j - 1)
  23.                 if(a[i] < a[j]) cnt[j]++;
  24.         FOR(j , 1 , n)
  25.             FOR(k , j + 1 , n)
  26.                 if(a[j] < a[k])
  27.                     ans += cnt[j];
  28.         cout << ans;
  29.     }
  30. }
  31. namespace sub3{
  32.     map<int,int> cnt;
  33.     ll L[N + 3],R[N + 3];
  34.     int t[N + 3],t1[N + 3];
  35.     int get(int x){
  36.         int res = 0;
  37.         for(; x ; x -= x & -x) res += t[x];
  38.         return res;
  39.     }
  40.     void upd(int x){
  41.         for(; x <= n ; x += x & -x)  t[x]++;
  42.     }
  43.     int get1(int x){
  44.         int res = 0;
  45.         for(; x <= n ; x += x & -x) res += t1[x];
  46.         return res;
  47.     }
  48.     void upd1(int x){
  49.         for(; x  ; x -= x & -x)  t1[x]++;
  50.     }
  51.     void solve(){
  52.         FOR(i , 1 , n)  cnt[a[i]] = 1;
  53.         int m = 0;
  54.         for(auto [u , v] : cnt) cnt[u] = ++m;
  55.         FOR(i , 1 , n) a[i] = cnt[a[i]];
  56.         FOR(i  ,1 , n){
  57.             L[i] = get(a[i] - 1);
  58.             upd(a[i]);
  59.         }
  60.         FORD(i , n , 1){
  61.             R[i] = get1(a[i] + 1);
  62.             upd1(a[i]);
  63.         }
  64.         FOR(i , 1 , n) ans += L[i] * R[i];
  65.         cout << ans;
  66.     }
  67. }
  68. signed main()
  69. {
  70.     ios_base::sync_with_stdio(0);
  71.     cin.tie(0);
  72.     cout.tie(0);
  73.     freopen("COUNT.inp" , "r" , stdin);
  74.     freopen("COUNT.out" , "w" , stdout);
  75.     cin >> n;
  76.     FOR(i , 1 , n) cin >> a[i];
  77.     if(n <= 100) sub1::solve();
  78.     else if(n <= 1000) sub2::solve();
  79.     else sub3::solve();
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rogDpQ
language:
C++14 (clang 8.0)
created:
121 days 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!