Submission #224847

#	Time	Username	Problem	Language	Result	Execution time	Memory
224847		nabilervatra	Mountains (NOI20_mountains)	C++14	100 / 100	342 ms	24824 KiB

Mountains

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set s;
long long n,ans;
pair<long long, long long > arr[300005];
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i =1;i<=n;i++){
        cin>>arr[i].fi;
        arr[i].se=i;
    }
    sort(arr+1,arr+n+1);
    long long bef=1;
    for(int i =2;i<=n;i++){
        if(arr[i].fi>arr[bef].fi){
            for(int j =bef;j<=i-1;j++)s.insert(arr[j].se);
            bef=i;
        }
        long long jwb1 = s.order_of_key(arr[i].se);
        long long jwb2 = s.size()-jwb1;
        ans += jwb1*jwb2;
    }
    cout<<ans<<endl;
}

• 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