Submission #1091569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091569		_rain_	Mountains (NOI20_mountains)	C++14	100 / 100	123 ms	14352 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fixbug true

const int maxn = 3e5;
int BIT[maxn+2],ans[maxn+2],n;
ll h[maxn+2];
int Right[maxn+2],Left[maxn+2];
void add(int p , int val){
	for (; p <= n; p += p&-p)
		BIT[p] += val;
	return;
}
int Get(int p){
	int sum = 0;
	for (; p; p -= p&-p)
		sum += BIT[p];
	return sum;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	vector<ll>v;
	for (int i = 1; i <= n; ++i){
		cin >> h[i];
		v.push_back(h[i]);
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for (int i = 1; i <= n; ++i)
		h[i] = upper_bound(v.begin(),v.end(),h[i])-v.begin();
	for (int i = 1; i <= n; ++i){
		add(h[i],1);
		Left[i] += Get(h[i]-1);
	}
	memset(BIT,0,sizeof BIT);
	for (int i = n; i >= 1; --i){
		add(h[i],1);
		Right[i] += Get(h[i]-1);
	}
	ll ans = 0;
	for (int i = 1; i <= n; ++i){
		ans += (ll)Left[i]*Right[i];
	}
	cout << ans;
}

• 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