Submission #285477

#	Time	Username	Problem	Language	Result	Execution time	Memory
285477		wildturtle	Mountains (NOI20_mountains)	C++14	100 / 100	548 ms	10744 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[300005],BITree[400005],ans;
pair <long long,long long> B[300005];
long long getSum(long long index) {
    long long sum = 0;
    index = index + 1; 
    while (index>0) { 
        sum += BITree[index]; 
        index -= index & (-index); 
    } 
    return sum; 
} 
void updateBIT(long long index, long long val) { 
    index = index + 1; 
    while (index <= 300005) { 
        BITree[index] += val; 
        index += index & (-index); 
    } 
} 
int main() {
    cin>>n;
    for(long long i=1;i<=n;i++) {
        cin>>A[i];
        B[i].first=A[i]; B[i].second=i;
    }
    sort(B+1,B+1+n);
    k=1;
    A[B[1].second]=k;
    for(long long i=2;i<=n;i++) {
        if(B[i].first!=B[i-1].first) k++;
        A[B[i].second]=k;
    }
    for(long long i=1;i<=n;i++) {
        B[i].first=getSum(A[i]-1);
        updateBIT(A[i],1);
    }
    for(long long i=1;i<=300005;i++)
    BITree[i]=0;
    for(long long i=n;i>=1;i--) {
        B[i].second=getSum(A[i]-1);
        updateBIT(A[i],1);
    }
    for(long long i=1;i<=n;i++) {
        //cout<<B[i].first<<" "<<B[i].second<<endl;
        ans+=(B[i].first*B[i].second);
    }
    cout<<ans;
}

• 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