Untitled
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