fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9.  
  10. const int MAXN = 1e6+5;
  11.  
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
  13.  
  14. typedef long long ll;
  15.  
  16. int n, cnt = 1, tr[MAXN*64][2], suf[MAXN], a[MAXN];
  17.  
  18. ll st[MAXN*64];
  19.  
  20. ost s;
  21.  
  22. //intended is to coord compress but 🐒
  23.  
  24. void update(int node, ll l, ll r, ll i, ll x){
  25.     if(l == r){
  26.         st[node] = x;
  27.         return;
  28.     }
  29.  
  30.     ll mid = (l+r)>>1;
  31.  
  32.     if(i <= mid){
  33.         if(!tr[node][0]) tr[node][0] = ++cnt;
  34.         update(tr[node][0], l,mid,i,x);
  35.     }
  36.     else{
  37.         if(!tr[node][1]) tr[node][1] = ++cnt;
  38.         update(tr[node][1],mid+1,r,i,x);
  39.     }
  40.  
  41.     st[node] = st[tr[node][0]] + st[tr[node][1]];
  42.  
  43. }
  44.  
  45. ll query(int node, ll l, ll r, ll x, ll y){
  46.     if(x > r || y < l) return 0;
  47.  
  48.     if(x <= l && y >= r) return st[node];
  49.     ll mid = (l+r)>>1;
  50.     return query(tr[node][0],l,mid,x,y) + query(tr[node][1], mid+1,r,x,y);
  51. }
  52.  
  53. int main(){
  54.     cin >> n;
  55.  
  56.     for(int i = 1; i <= n; i++) cin >> a[i];
  57.  
  58.     s.insert(a[n]);
  59.  
  60.     for(int i = n-1; i >= 1; i--){
  61.         suf[i] = s.order_of_key(a[i]);
  62.         s.insert(a[i]);
  63.     }
  64.  
  65.     for(int i = 1; i <= n; i++) cout << suf[i] << "\n";
  66.  
  67.  
  68.     long long ans = 0;
  69.     for(int i = n; i >= 1; i--){
  70.         ans += query(1,1,1e9, a[i], 1e9);
  71.         update(1,1,1e9, a[i], suf[i]);
  72.     }
  73.  
  74.     cout << ans << "\n";
  75.  
  76.  
  77.  
  78.  
  79. }
Success #stdin #stdout 0.01s 7732KB
comments (?)
stdin
copy 
3
3 2 1
stdout
copy 
2
1
0
0
https://ideone.com/piBYt5
language:
C++14 (clang 8.0)
created:
17 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!