Submission #1193452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193452		zyntherix	Mountains (NOI20_mountains)	C++20	0 / 100	228 ms	32096 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordst = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;
const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    int pref[n], suff[n];
    pref[0] = 0;
    ordst ms, sm;
    ms.insert(arr[0]);
    for (int i = 1; i < n; i++)
    {
        pref[i] = ms.order_of_key(arr[i]);
        ms.insert(arr[i]);
    }
    suff[n - 1] = 0;
    sm.insert(arr[n - 1]);
    for (int i = n - 2; i >= 0; i--)
    {
        suff[i] = sm.order_of_key(arr[i]);
        sm.insert(arr[i]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += (pref[i] * suff[i]);
    }
    cout << ans << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12