Submission #405610

#	Time	Username	Problem	Language	Result	Execution time	Memory
405610		rqi	Mountains (NOI20_mountains)	C++14	100 / 100	622 ms	55280 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second
#define ins insert

#define sz(x) (int)(x).size()

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

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

#define fbo find_by_order
#define ook order_of_key

const int mx = 300005;
ll H[mx];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> H[i];
	}
	map<ll, vi> vals;
	for(int i = 1; i <= n; i++){
		vals[H[i]].pb(i);
	}

	Tree<int> t;

	ll ans = 0;
	for(auto& u: vals){
		for(auto& pos: u.s){
			int ind = t.order_of_key(pos);
			ans+=ll(ind)*ll(sz(t)-ind);
		}
		for(auto& pos: u.s){
			t.ins(pos);
		}
	}
	cout << ans << "\n";
}

• 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