Submission #209766

#	Time	Username	Problem	Language	Result	Execution time	Memory
209766		Alexa2001	Mountains (NOI20_mountains)	C++17	100 / 100	140 ms	8728 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 3e5 + 5;

ll ans[Nmax], h[Nmax];
int a[Nmax];
int n;

class AIB
{
    int ub(int x)
    {
        return (x&(-x));
    }
    int a[Nmax];

public:
    void update(int x)
    {
        for(; x<=n; x+=ub(x)) a[x]++;
    }
    int query(int x)
    {
        int ans = 0;
        for(; x; x-=ub(x)) ans += a[x];
        return ans;
    }
    void clear()
    {
        memset(a, 0, sizeof(a));
    }
} aib;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n;

    int i;
    vector<int> ord;

    for(i=1; i<=n; ++i)
    {
        cin >> h[i];
        ord.push_back(i);
    }

    sort(ord.begin(), ord.end(), [](int x, int y) { return h[x] < h[y]; });

    int nr = 0;
    for(i=0; i<n; ++i)
    {
        if(!i || h[ord[i]] != h[ord[i-1]]) ++nr;
        a[ord[i]] = nr;
    }

    for(i=1; i<=n; ++i)
    {
        ans[i] = aib.query(a[i]-1);
        aib.update(a[i]);
    }

    aib.clear();
    for(i=n; i; --i)
    {
        ans[i] *= aib.query(a[i]-1);
        aib.update(a[i]);
    }

    ll sum = 0;
    for(i=1; i<=n; ++i) sum += ans[i];
    cout << sum << '\n';

    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