Submission #626181

#	Time	Username	Problem	Language	Result	Execution time	Memory
626181		PoonYaPat	Mountains (NOI20_mountains)	C++14	100 / 100	145 ms	15408 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;

int n,fen[300001],h[300001];
vector<pii> v;
ll ans,a[300001];

ll find(int x) {
    ll cnt=0;
    while (x) {
        cnt+=fen[x];
        x-=(x&-x);
    }
    return cnt;
}

void update(int x) {
    while (x<=n) {
        ++fen[x];
        x+=(x&-x);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        ll x; cin>>x;
        v.push_back(pii(x,i));
    }
    sort(v.begin(),v.end());
    int cnt=1;
    ll pre=-1;
    for (auto s : v) {
        if (s.first!=pre) {
            pre=s.first;
            h[s.second]=cnt++;
        } else h[s.second]=cnt-1;
    }

    for (int i=1; i<=n; ++i) {
        a[i]=find(h[i]-1);
        update(h[i]);
    }
    memset(fen,0,sizeof(fen));
    for (int i=n; i>=1;--i) {
        ans+=(a[i]*find(h[i]-1));
        update(h[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