Submission #936541

#	Time	Username	Problem	Language	Result	Execution time	Memory
936541		Warinchai	Mountains (NOI20_mountains)	C++14	100 / 100	251 ms	23988 KiB

Mountains

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ar[300005];
int id[300005];
int l[300005];
int r[300005];
vector<int>v;
struct fenwick{
    int info[300005];
    void upd(int x,int val){
        for(int i=x;i<=300000;i+=i&-i){
            info[i]+=val;
        }
    }
    int fsum(int x){
        int sum=0;
        for(int i=x;i>0;i-=i&-i){
            sum+=info[i];
        }
        return sum;
    }
}fwl,fwr;
int32_t main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>ar[i];
        v.push_back(ar[i]);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        id[i]=lower_bound(v.begin(),v.end(),ar[i])-v.begin()+1;
    }
    for(int i=0;i<n;i++){
        l[i]=fwl.fsum(id[i]-1);
        fwl.upd(id[i],1);
    }
    for(int i=n-1;i>0;i--){
        r[i]=fwr.fsum(id[i]-1);
        fwr.upd(id[i],1);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=l[i]*r[i];
    }
    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