Submission #1075989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075989		ivaziva	Mountains (NOI20_mountains)	C++14	100 / 100	446 ms	31896 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

#define MAXN 300001

long long n;
long long h[MAXN];
map<long long,long long> kompresija;
long long fenw[MAXN];
long long sol[MAXN];

void update(long long pos)
{
    for (long long i=pos;i<=n;i+=(i&(-i))) fenw[i]++;
}

long long query(long long pos)
{
    long long sum=0;
    for (long long i=pos;i>=1;i-=(i&(-i))) sum+=fenw[i];
    return sum;
}

int main()
{
    cin>>n;
    for (long long i=1;i<=n;i++) cin>>h[i];
    for (long long i=1;i<=n;i++) kompresija[h[i]]=1;
    long long idx=0;
    for (auto&p:kompresija) {idx++;p.second=idx;}
    for (long long i=1;i<=n;i++) h[i]=kompresija[h[i]];
    for (long long i=1;i<=n;i++) {sol[i]=query(h[i]-1);update(h[i]);}
    for (long long i=0;i<MAXN;i++) fenw[i]=0;
    for (long long i=n;i>=1;i--) {sol[i]*=query(h[i]-1);update(h[i]);}
    long long ans=0;
    for (long long i=1;i<=n;i++) ans+=sol[i];
    cout<<ans<<endl;
}

• 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