Submission #1193108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193108		loom	Mountains (NOI20_mountains)	C++20	100 / 100	369 ms	26264 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 ordered_set tree<pair<long long,long long>, null_type,less<pair<long long,long long> >, rb_tree_tag,tree_order_statistics_node_update>

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);

    int n;
    cin>>n;
    long long h[n];
    for(int i=0; i<n; i++){
        cin>>h[i];
    }

    long long ans = 0;
    ordered_set set;
    long long low[n], high[n];
    for(int i=0; i<n; i++){
        set.insert({h[i],i});
        low[i] = set.order_of_key({h[i],-1});
    }

    set.clear();
    for(int i=n-1; i>=0; i--){
        set.insert({h[i],i});
        high[i] = set.order_of_key({h[i], -1});
    }

    for(int i=0; i<n; i++) ans += low[i]*high[i];
    cout<<ans;
    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