Submission #335602

#	Time	Username	Problem	Language	Result	Execution time	Memory
335602		beepbeepsheep	Mountains (NOI20_mountains)	C++17	0 / 100	43 ms	25580 KiB

Mountains

#include <bits/stdc++.h>

using namespace std;
#define ll long long
vector<int> tree[400020];
const int inf=2e9;
int arr[100005];
void build(int node,int s,int e){
    if (s==e){
        tree[node].emplace_back(arr[s]);
        return;
    }
    int m=(s+e)/2;
    int left=node<<1;
    int 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]));
}
int query(int node,int l,int r,int i,int j,int 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();
    int mid=(l+r)/2;
    int left=node<<1;
    int 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);
	int n;
    cin>>n;
    pair<int,int> num[n];
    for (int i=0;i<n;i++){
        cin>>num[i].first;
        arr[i]=num[i].first;
        num[i].second=i;
    }
    int a,b;
    ll ans=0;
    build(1,0,n-1);
    for (int 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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12