fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define maxn 100010
  5. #define ena long long
  6.  
  7. ena n;
  8. ena a[maxn], cnt[maxn], st[4*maxn], ans[maxn];
  9.  
  10. vector <ena> vitri[maxn];
  11.  
  12. void update(ena node, ena l, ena r, ena id, ena val)
  13. {
  14.     if(id < l || id > r) return;
  15.     if(l == r)
  16.     {
  17.         st[node] += val;
  18.         return;
  19.     }
  20.     ena mid = (l + r)/2;
  21.     update(2*node, l, mid, id, val);
  22.     update(2*node+1, mid+1, r, id, val);
  23.  
  24.     st[node] = st[2*node] + st[2*node+1];
  25. }
  26.  
  27. ena get(ena node, ena l, ena r, ena u, ena v)
  28. {
  29.     if(v < l || r < u) return 0;
  30.     if(u <= l && r <= v) return st[node];
  31.  
  32.     ena mid = (l + r)/2;
  33.     ena L = get(2*node, l, mid, u, v);
  34.     ena R = get(2*node+1, mid+1, r, u, v);
  35.  
  36.     return (L + R);
  37. }
  38.  
  39. int main()
  40. {
  41.     freopen("daonguoc.inp","r",stdin);
  42.     freopen("daonguoc.out","w",stdout);
  43.     cin >> n;
  44.     for(ena i=1; i<=n; i++)
  45.     {   
  46.         cin >> a[i];
  47.         cnt[i] = get(1, 0, n, a[i] + 1, n);
  48.         update(1, 0, n, a[i], 1);
  49.         vitri[a[i]].push_back(i);
  50.  
  51.         ans[n] += cnt[i];
  52.     }
  53.  
  54.     for(ena i=n-1; i>=0; i--)
  55.     {
  56.         ans[i] = ans[i+1];
  57.         for(ena id:vitri[i])
  58.         {
  59.             ans[i] -= cnt[id];
  60.         }
  61.     }
  62.  
  63.     for(ena i=0; i<=n-1; i++)
  64.         cout << ans[i] << "\n";
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 7164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/61Z52v
daonguoc_NhutTri
language:
C++14 (gcc 8.3)
created:
2 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!