Submission #1136978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136978		TheInvadr	Mountains (NOI20_mountains)	C++20	79 / 100	271 ms	7480 KiB

Mountains

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
    long long int n;
    cin>>n;
    long long int arr[n];
    for(int i =0;i<n;i++)cin>>arr[i];
    if(n<=500){
            long long int cnt = 0;
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            for(int k = j+1;k<n;k++){
                if(arr[i]<arr[j]&&arr[j]>arr[k])cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
    }
    if(n<=10000){
        int pre[n];
        pre[n-1]=0;
        for(int i=n-2;i>=0;i--){
            pre[i]=0;
            for(int j = i+1;j<n;j++)if(arr[j]<arr[i])pre[i]++;
        }
        long long int ans = 0;
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++)if(arr[j]>arr[i])ans+=pre[j];
        }
        cout<<ans<<endl;
        return 0;
    }
    bool can = false;
    for(int i = 0;i<n-1;i++)if(arr[i]>arr[i+1])can=true;
    if(!can){
        cout<<0<<endl;
        return 0;
    }
	long long int ans = 0;
    for(int c = 0;c<100;c++){
        long long int pre[n];
        long long int suf[n];
        pre[0]=suf[n-1]=0;
        if(arr[0]<c)pre[0]++;
        if(arr[n-1]<c)suf[n-1]++;
        for(int i = 1;i<n;i++){
            pre[i]=pre[i-1];
            if(arr[i]<c)pre[i]++;
        }
        for(int i = n-2;i>=0;i--){
            suf[i]=suf[i+1];
            if(arr[i]<c)suf[i]++;
        }
        for(int i = 1;i<n-1;i++)if(arr[i]==c)ans+=(pre[i-1]*suf[i+1]);
    }
	cout<<ans<<endl;
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12