제출 #1194783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194783		zyntherix	Mountains (NOI20_mountains)	C++20	100 / 100	377 ms	47400 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;
#define int long long
#define pi pair<int, int>
using ordst = tree<pi, null_type, less<pi>, 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], 0});
    for (int i = 1; i < n; i++)
    {
        pref[i] = ms.order_of_key({arr[i], -1});
        ms.insert({arr[i], i});
    }
    suff[n - 1] = 0;
    sm.insert({arr[n - 1], n - 1});
    for (int i = n - 2; i >= 0; i--)
    {
        suff[i] = sm.order_of_key({arr[i], -1});
        sm.insert({arr[i], i});
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += (pref[i] * suff[i]);
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        cin >> n;
        vector<int> x(n);
        for (int i = 0; i < n; i++)
        {
            cin >> x[i];
        }
        int a = solve(x);
        cout << a << '\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