Untitled

 avatar
unknown
c_cpp
17 days ago
1.6 kB
5
Indexable
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define int long long

// Function to calculate S(k) = k * (k + 1) / 2 % MOD
int summation(int k) {
    return (k * (k + 1) / 2);
}

int calculateSum(vector<int>& arr) {
    int n = arr.size();
    vector<int> right(n), left(n);
    stack<int> st;

    // Compute Next Greater or Equal (Right Array)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        right[i] = (st.empty()) ? i : st.top();
        st.push(i);
    }

    // Clear stack for next calculation
    while (!st.empty()) st.pop();

    // Compute Next Strictly Greater (Left Array)
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] <= arr[i])
            st.pop();
        left[i] = (st.empty()) ? i : st.top();
        st.push(i);
    }

    // Compute the total sum
    int result = 0;
    for (int i = 0; i < n; i++) {
        // Right Contribution
        if (arr[right[i]] == arr[i]) {
            result = (result + arr[i] * summation(right[i] - i + 1)) % MOD;
        } else {
            result = (result + arr[i] * summation(right[i] - 1 - i + 1)) % MOD;
        }

        // Left Contribution
        int leftContributionRange = i - (left[i] + 1) + 1;
        if (leftContributionRange > 0) {
            result = (result + arr[i] * summation(leftContributionRange)) % MOD;
        }
    }

    return result;
}

int32_t main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << calculateSum(arr) << endl;
    return 0;
}
Editor is loading...
Leave a Comment