nicuvlad76

Untitled

Nov 26th, 2020 (edited)
412
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define N 70005
  3. using namespace std;
  4. ifstream fin("ijk.in");
  5. ofstream fout("ijk.out");
  6. int n,m=1,aib[N],a[N],v[N],st[N],dr[N];
  7. long long sol;
  8. unordered_map<int , int >M;
  9. int lowestBit(int x){return (x&-x);}
  10. void Update(int poz, int add)
  11. {
  12.     for(int i=poz;i<=m;i+=lowestBit(i))
  13.         aib[i]+=add;
  14. }
  15. int Query(int poz)
  16. {
  17.     int sum=0;
  18.     for(int i=poz;i>=1;i-=lowestBit(i))
  19.         sum+=aib[i];
  20.     return sum;
  21. }
  22. int main()
  23. {
  24.    fin>>n;
  25.    for(int i=1;i<=n;i++)fin>>a[i],v[i]=a[i];
  26.    sort(v+1,v+n+1);
  27.    for(int i=1;i<=n;i++)
  28.    {
  29.        M[v[i]]=m;
  30.        if(v[i]!=v[i+1])m++;
  31.    }
  32.    m--;
  33.    for(int i=1;i<=n;i++)a[i]=M[a[i]];
  34.    for(int i=n;i>=1;i--)
  35.    {
  36.        Update(a[i],1);
  37.        dr[i]=Query(m)-Query(a[i]);
  38.    }
  39.  
  40.    for(int i=1;i<=n;i++) aib[i]=0;
  41.    for(int i=1;i<=n;i++)
  42.    {
  43.        Update(a[i],1);
  44.        st[i]=Query(m)-Query(a[i]);
  45.    }
  46.    for(int i=1;i<=n;i++)sol+=(dr[i]*st[i]);
  47.    fout<<sol;
  48.  
  49.     return 0;
  50. }
  51.  
RAW Paste Data