Submission #876708

#	Time	Username	Problem	Language	Result	Execution time	Memory
876708		imarn	Mountains (NOI20_mountains)	C++14	100 / 100	189 ms	15868 KiB

Mountains

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define sz(x) (int)x.size()
#define pii pair<ll,ll>
using namespace std;
const int N=3e5+5;
int fw[N]{0};
void add(int i){
    for(;i<N;i+=i&-i)fw[i]++;
}
int qr(int i,int res=0){
    for(;i;i-=i&-i)res+=fw[i];
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;cin>>n;vector<ll>b;
    ll a[n+1];for(int i=1;i<=n;i++)cin>>a[i],b.pb(a[i]);
    sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());
    ll tt[n+1];
    for(int i=1;i<=n;i++){
        int idx=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        tt[i] = qr(idx);add(idx+1);
    }ll ans=0;
    for(int i=1;i<=n;i++)fw[i]=0;
    for(int i=n;i>=1;i--){
        int idx=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        tt[i] *= qr(idx);add(idx+1);ans+=tt[i];
    }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