Submission #223869

#	Time	Username	Problem	Language	Result	Execution time	Memory
223869		maximath_1	Mountains (NOI20_mountains)	C++11	100 / 100	581 ms	36228 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=300005;
int n;
ll fwt[mxn], h[mxn], tmp[mxn], lf[mxn], rg[mxn];
map<ll, ll>mp;
void upd(int x, int v){for(; x<mxn; x+=x&-x) fwt[x]+=v;}
int que(int x){ll ans=0; for(; x>0; x-=x&-x) ans+=fwt[x]; return ans;}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=0; i<n; i++){cin>>h[i]; tmp[i]=h[i];}
	sort(tmp, tmp+n); int cnt=1;
	for(int i=0; i<n; i++){
		if(i==0) mp[tmp[i]]=cnt;
		else if(tmp[i]>tmp[i-1]) {mp[tmp[i]]=cnt+1; cnt++;}
		else mp[tmp[i]]=cnt;
	}
	for(int i=0; i<n; i++) h[i]=mp[h[i]]; //coordinate compression
//	for(int i=0; i<n; i++) cout<<h[i]<<" "; cout<<endl;
	memset(fwt, 0, sizeof(fwt));
	for(int i=0; i<n; i++){
		lf[i]=que(h[i]-1);
		upd(h[i], 1);
	}
	for(int i=0; i<n; i++) rg[i]=que(h[i]-1)-lf[i];
	ll ans=0ll;
	for(int i=0; i<n; i++) ans+=lf[i]*rg[i];
	cout<<ans<<endl;
	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