Submission #478190

#	Time	Username	Problem	Language	Result	Execution time	Memory
478190		blue	Mountains (NOI20_mountains)	C++17	100 / 100	156 ms	16476 KiB

Mountains

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 300'000;
long long H[1+maxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for(int i = 1; i <= N; i++) cin >> H[i];

    vector<int> ind(N);
    for(int i = 1; i <= N; i++) ind[i-1] = i;

    sort(ind.begin(), ind.end(), [] (int p, int q)
    {
        if(H[p] == H[q]) return p > q;
        return H[p] < H[q];
    });

    vector<long long> lft(1+N, 0), rgt(1+N, 0);

    vector<int> BIT(1+N, 0);
    for(int i: ind)
    {
        for(int j = i; j <= N; j += j&-j)
            BIT[j]++;

        for(int j = i-1; j >= 1; j -= j&-j)
            lft[i] += BIT[j];
    }
    // cerr << "check\n";

    BIT = vector<int>(1+N, 0);
    sort(ind.begin(), ind.end(), [] (int p, int q)
    {
        if(H[p] == H[q]) return p < q;
        return H[p] < H[q];
    });

    // cerr << "check\n";

    for(int i: ind)
    {
        for(int j = i; j <= N; j += j&-j)
            BIT[j]++;

        for(int j = N; j >= 1; j -= j&-j)
            rgt[i] += BIT[j];

        for(int j = i; j >= 1; j -= j&-j)
            rgt[i] -= BIT[j];
    }

    // for(int i = 1; i <= N; i++) cerr << lft[i] << ' ';
    // cerr << '\n';

    long long ans = 0;
    for(int i = 1; i <= N; i++) ans += lft[i] * rgt[i];

    cout << ans << '\n';
}

• 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