Submission #1267481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267481		vukhacminh	Mountains (NOI20_mountains)	C++20	100 / 100	120 ms	9948 KiB

Mountains

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 1e9+7;
ll n,pre[maxn],suf[maxn],a[maxn],res,bit[maxn];
vector<ll> ctz;
void add(int u,int v)
{
    for(;u<=n;u+=u&-u) bit[u]+=v;
}
ll get(int u)
{
    ll sum = 0;
    for(;u;u-=u&-u) sum+= bit[u];
    return sum;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        ctz.push_back(a[i]);
    }
    sort(ctz.begin(),ctz.end());
    ctz.erase(unique(ctz.begin(),ctz.end()));
    for(int i = 1;i<=n;i++)
    {
        a[i] = lower_bound(ctz.begin(),ctz.end(),a[i]) - ctz.begin()+1;
        pre[i] = get(a[i]-1);
        add(a[i],1);
    }
    memset(bit,0,sizeof bit);
    add(a[n],1);
    for(int i = n-1;i>=2;i--)
    {
        res+= pre[i]* get(a[i]-1);
       // cout<<i<<" "<<pre[i-1]<<" "<< get(a[i]-1)<<'\n';;
        add(a[i],1);
    }
    cout<<res;
    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