Submission #677293

#	Time	Username	Problem	Language	Result	Execution time	Memory
677293		dsyz	Mountains (NOI20_mountains)	C++17	100 / 100	145 ms	16704 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
struct plot {
  ll fw[MAXN];
  plot() {
    memset(fw,0,sizeof fw);
  }
  void update(int x,ll nval) {
    for(;x<MAXN;x+=x&(-x)) fw[x]+=nval;
  }
  ll aaa(int x) {
    ll res = 0;
    for(;x;x-=x&(-x)) res += fw[x];
    return res;
  }
  ll sum(int a,int b) {
    return aaa(b) - aaa(a-1);
  }
} before, after;
ll N;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin>>N;
  ll arr[N];
  ll ans = 0;
  vector<ll> d;
  for(ll i = 0;i < N;i++){
    cin>>arr[i];
    d.push_back(arr[i]);
  }
  sort(d.begin(),d.end());
  d.resize(unique(d.begin(),d.end()) - d.begin());
  for(ll i = 0;i < N;i++) arr[i] = (lower_bound(d.begin(), d.end(), arr[i]) - d.begin() + 1);
  for(ll i = 0;i < N;i++){
    before.update(arr[i],1);
  }
  for(ll i = N - 1;i >= 0;i--){
    ans += (before.sum(1,arr[i] - 1) * after.sum(1,arr[i] - 1));
    before.update(arr[i],-1);
    after.update(arr[i],1);
  }
  cout<<ans<<'\n';
}

• 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