Submission #439009

#	Time	Username	Problem	Language	Result	Execution time	Memory
439009		skyberg	Mountains (NOI20_mountains)	C++17	79 / 100	131 ms	5068 KiB

Mountains

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
long long int c[300000];
long long int mn[300000];
int t[100];
int main(){
    int n;
    cin >> n;
    long long int ans = 0;
    if(n >= 10005){
        cin >> c[0];
        if(c[0] >= 100){
            cout << 0;
            return 0;
        }
        t[c[0]]++;
        mn[0] = 0;
        for(int i = 1; i < n; i++){
            cin >> c[i];
            if(c[i] >= 100){
                cout << 0;
                return 0;
            }
            for(int j = 0; j < c[i]; j++){
                mn[i] += t[j];
            }
            t[c[i]]++;
        }
        memset(t, 0, sizeof(t[0])* 100);
        t[c[n - 1]]++;
        for(int i = n - 2; i >= 0; i--){
            long long int temp =0;
            for(int j = 0; j < c[i]; j++){
                temp += t[j];
            }
            ans += mn[i] * temp;
            t[c[i]]++;
        }
        cout << ans;
    }
    else{
        for(int i = 0; i < n; i++){
            cin >> c[i];
        }
        for(int i = 1; i < n - 1; i++){
            long long int a = 0, b = 0;
            for(int j = 0; j < i; j++){
                if(c[j] < c[i])a++;
            }
            for(int j = i + 1; j < n; j++){
                if(c[j] < c[i])b++;
            }
            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: 0 / 9
• Subtask 7: 0 / 12