Submission #230992

#	Time	Username	Problem	Language	Result	Execution time	Memory
230992		keta_tsimakuridze	Mountains (NOI20_mountains)	C++14	100 / 100	1047 ms	34296 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
long long n,a[300005],b[300005],tree_bef[600005],tree_aft[600005],i,k,ans;
map<long long,int>ind;
void update(int idx,int val,int w){
	for(int x=idx;x<=n;x+=x&(-x)){
		if(w==1){
		tree_aft[x]+=val; } 
		else tree_bef[x]+=val;
	}
}

long long getans(int idx,int w){
	long long pas=0;
	for(int x=idx;x>=1;x-=x&(-x)){
	  if(w==1)	pas+=tree_aft[x];
	  else pas+=tree_bef[x];
	}
	return pas;
}

int main(){
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k];
		b[k]=a[k];
	}
	sort(b+1,b+n+1);
	for(k=1;k<=n;k++){
		if(!ind[b[k]]){
			i++;
			ind[b[k]]=i; 
		}
		
		update(ind[b[k]],1,1);
	} 
	for(k=1;k<=n;k++){
		update(ind[a[k]],-1,1);
		update(ind[a[k]],1,2);
		ans+=getans(ind[a[k]]-1,1)*getans(ind[a[k]]-1,2);
		//cout<<ans<<endl;
	}
	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