Submission #851428

#	Time	Username	Problem	Language	Result	Execution time	Memory
851428		NamPE	Mountains (NOI20_mountains)	C++17	100 / 100	695 ms	27288 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    
    ll n;
    cin >> n;

    vector<ll> h(n);

    for (ll& i : h) {
        cin >> i;
    }

    indexed_set<pair<ll, ll>> l, r;
    ll id = 0;

    for (ll i : h) {
        r.insert({i, id});
        id++;
    }

    ll ans = 0;

    for (ll i : h) {
        r.erase(r.lower_bound({i, 0}));

        ll a = l.order_of_key({i - 1, INT_MAX});
        ll b = r.order_of_key({i - 1, INT_MAX});

        ans += a * b;

        l.insert({i, id});
        id++;
    }

    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