Submission #887042

#	Time	Username	Problem	Language	Result	Execution time	Memory
887042		vjudge1	Mountains (NOI20_mountains)	C++14	100 / 100	352 ms	43600 KiB

Mountains

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
   int get(int l, int r){
      return get(r)-get(l-1);
   }
} bit;

const int N=3e5+1;
int n, a[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   map<int, vector<int>> mp;
   for (int i=1; i<=n; ++i) cin >> a[i], mp[a[i]].push_back(i);
   bit.init(n);
   int ans=0;
   for (auto &i:mp){
      for (int j:i.second){
         ans+=bit.get(j-1)*bit.get(j+1, n);
      }
      for (int j:i.second) bit.update(j, 1);
   }
   cout << ans;
   return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12