Submission #439659

#	Time	Username	Problem	Language	Result	Execution time	Memory
439659		MohamedAhmed04	Mountains (NOI20_mountains)	C++14	100 / 100	978 ms	31796 KiB

Mountains

#include <bits/stdc++.h>

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 3e5 + 10 ;

long long arr[MAX] , pref[MAX] , suff[MAX] ;
int n ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	ordered_set< pair<long long , int> >s ;
	for(int i = 0 ; i < n ; ++i)
	{
		pref[i] = s.order_of_key({arr[i]-1 , 1e9}) ;
		s.insert({arr[i] , i}) ;
	}
	s.clear() ;
	for(int i = n-1 ; i >= 0 ; --i)
	{
		suff[i] = s.order_of_key({arr[i]-1 , 1e9}) ;
		s.insert({arr[i] , i}) ;
	}
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
		ans += pref[i] * suff[i] ;
	return cout<<ans<<"\n" , 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