Submission #1193460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193460		zyntherix	Mountains (NOI20_mountains)	C++20	2 / 100	239 ms	33288 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;
int n;

int solve(vector<int> arr)
{
    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]);
    }
    return ans;
}

// int solve2(vector<int> arr)
// {
//     int ans = 0;
//     for (int i = 0; i < n; i++)
//     {
//         for (int j = i + 1; j < n; j++)
//         {
//             for (int k = j + 1; k < n; k++)
//             {
//                 ans += (arr[j] > arr[k] && arr[j] > arr[i]);
//             }
//         }
//     }
//     // cout << ans << '\n';
//     return ans;
// }

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        // n = 25;
        cin >> n;
        vector<int> x(n);
        for (int i = 0; i < n; i++)
        {
            // x[i] = rand() % 100;
            cin >> x[i];
        }
        int a = solve(x);
        // int b = solve2(x);
        // if (a != b)
        // {
        //     cout << n << '\n';
        //     for (int i = 0; i < n; i++)
        //     {
        //         cout << x[i] << ' ';
        //     }
        //     cout << '\n'
        //          << a << ' ' << b << '\n';
        //     break;
        // }
        cout << a << '\n';
    }
    // cout << "\nDone!\n";
    return 0;
}

• Subtask 1: 2 / 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