Submission #285594

#	Time	Username	Problem	Language	Result	Execution time	Memory
285594		Ronin13	Mountains (NOI20_mountains)	C++14	100 / 100	1228 ms	111352 KiB

Mountains

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
 
using namespace std;

int n;
ll a[300001];
vector<ll>t[2000001];

void build(int v,int l,int r){
	if(l==r){
		t[v].pb(a[l]);
		return;
	}
	int m=(l+r)/2;
	build(2*v,l,m);
	build(2*v+1,m+1,r);
	t[v].resize((int)t[2*v].size()+(int)t[2*v+1].size());
	merge(t[2*v].begin(),t[2*v].end(),t[2*v+1].begin(),t[2*v+1].end(),t[v].begin());
}

ll get(int v,int l,int r,int tl,int tr,ll val){
	if(l==tl&&r==tr){
		ll k=lower_bound(t[v].begin(),t[v].end(),val)-t[v].begin();
		return k;
	}
	int tm=(tl+tr)/2;
	if(r<=tm)return get(2*v,l,r,tl,tm,val);
	if(l>tm)return get(2*v+1,l,r,tm+1,tr,val);
	return get(2*v,l,tm,tl,tm,val)+get(2*v+1,tm+1,r,tm+1,tr,val);
}

ll ans=0;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=2;i<n;i++){
		ans+=get(1,1,i-1,1,n,a[i])*get(1,i+1,n,1,n,a[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