Submission #335605

#	Time	Username	Problem	Language	Result	Execution time	Memory
335605		beepbeepsheep	Mountains (NOI20_mountains)	C++17	100 / 100	887 ms	117724 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;
#define ll long long
vector<ll> tree[1200020];
const ll inf=2e9;
ll arr[300005];
void build(ll node,ll s,ll e){
    if (s==e){
        tree[node].emplace_back(arr[s]);
        return;
    }
    ll m=(s+e)/2;
    ll left=node<<1;
    ll right=left|1;
    build(left,s,m);
    build(right,m+1,e);
    merge(tree[left].begin(),tree[left].end(),tree[right].begin(),tree[right].end(),back_inserter(tree[node]));
}
ll query(ll node,ll l,ll r,ll i,ll j,ll k){
    if (i>r||j<l) return 0;
    if (i<=l && r<=j) return lower_bound(tree[node].begin(),tree[node].end(),k)-tree[node].begin();
    ll mid=(l+r)/2;
    ll left=node<<1;
    ll right=left|1;
    return query(left,l,mid,i,j,k)+query(right,mid+1,r,i,j,k);

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
    cin>>n;
    pair<ll,ll> num[n];
    for (ll i=0;i<n;i++){
        cin>>num[i].first;
        arr[i]=num[i].first;
        num[i].second=i;
    }
    ll a,b;
    ll ans=0;
    build(1,0,n-1);
    for (ll i=0;i<n;i++){
        a=query(1,0,n-1,num[i].second,n-1,num[i].first);
        b=query(1,0,n-1,0,num[i].second,num[i].first);
        ans+=a*b;
    }
    cout<<ans;
	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