# Untitled

unknown
plain_text
11 days ago
1.3 kB
1
Indexable
Never
```int n = power.size();
vector<long long> contributions(n, 0);
stack<int> st;

// Calculate Previous Greater Element (PGE)
vector<int> left(n);
for (int i = 0; i < n; ++i) {
while (!st.empty() && power[st.top()] <= power[i]) {
st.pop();
}
left[i] = (st.empty()) ? -1 : st.top();
st.push(i);
}

// Clear the stack to reuse it for the next greater element
while (!st.empty()) st.pop();

// Calculate Next Greater Element (NGE)
vector<int> right(n);
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && power[st.top()] < power[i]) {
st.pop();
}
right[i] = (st.empty()) ? n : st.top();
st.push(i);
}

// Calculate the contributions for each element
for (int i = 0; i < n; ++i) {
long long left_count = i - left[i];
long long right_count = right[i] - i;
contributions[i] = left_count * right_count * power[i];
}

// Sort contributions in descending order to sum the top `k`
sort(contributions.rbegin(), contributions.rend());

// Sum the top `k` contributions
long long result = 0;
for (long i = 0; i < k && i < contributions.size(); ++i) {
result = (result + contributions[i]) % MOD;
}

return static_cast<int>(result);
}```