Submission #285485

#	Time	Username	Problem	Language	Result	Execution time	Memory
285485		akobi	Mountains (NOI20_mountains)	C++98	100 / 100	141 ms	16524 KiB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define F first
#define S second
using namespace std;
ll n,a[300005],id[300005],ans,f1[300005],f2[300005],x;
pair<ll,ll> b[300005];
void upd1(ll u,ll x)
{
    u++;
    while (u<=n)
    {
        f1[u]+=x;
        u+=(u&(-u));
    }
    return;
}
ll get1(ll u)
{
    u++;
    ll res=0;
    u--;
    while (u>0)
    {
        res+=f1[u];
        u-=(u&(-u));
    }
    return res;
}
void upd2(ll u,ll x)
{
    u++;
    while (u<=n)
    {
        f2[u]+=x;
        u+=(u&(-u));
    }
    return;
}
ll get2(ll u)
{
    u++;
    ll res=0;
    u--;
    while (u>0)
    {
        res+=f2[u];
        u-=(u&(-u));
    }
    return res;
}
int main() 
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n; i++)
    {
        cin>>a[i];
        b[i]=mp(a[i],i);
    }
    sort(b,b+n);
    x=0;
    id[b[0].S]=x;
    for (int i=1; i<n; i++)
    {
        if (b[i].F>b[i-1].F)
            x++;
        id[b[i].S]=x;
    }
    for (int i=2; i<n; i++)
        upd2(id[i],1);
    upd1(id[0],1);
    for (int i=1; i<=n-2; i++)
    {
        ans+=get1(id[i])*get2(id[i]);
        upd1(id[i],1);
        upd2(id[i+1],-1);
    }
    cout<<ans<<endl;
    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