PROBLEM LINK :
Author : Vibhor Gupta
Tester : Vibhor Gupta
Editorialist : Vibhor Gupta
DIFFICULTY :
Hard
PREREQUISITES :
stock span algorithm, Sub-array
PROBLEM :
Rahul has another problem to solve, he is given an array A now he has to increase its every element by its own index(1 - based).
Then he has to find the sum of the maximum elements of the resultant array in every possible sub-array.
As the answer can be large, output it modulo 10^9 + 7.
Flawed Code :
#define Ull long long
using namespace std;
Ull mod=1e9+7;
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
Ull ar[n],x,ans;
int b[n],a[n];
stack s;
for(int i=0;n>i;i++){cin>>ar[i];ar[i] = (ar[i] + i + 1)%mod;}
a[0]=0;
s.push(0);
for(int i=1;n>i;i++){
while(!s.empty() && ar[i] > ar[s.top()]){
b[s.top()] = i-s.top();
s.pop();}
a[i] = (s.empty())? i : i-s.top();
s.push(i);}
while(!s.empty()){
b[s.top()] = n-s.top();
s.pop();}
ans=1;
for(int i=0;n>i;i++){
x = (a[i] + b[i] + 1)%mod;
x = (x * ar[i])%mod;
ans = (ans + x)%mod;}
printf("%lld\n",ans);
}}
EXPLANATION :
In this question, our main objective is to find the range in which a[i] is maximum.
We use the stock span algorithm to calculate the range in which a[i] is maximum. L[i] = represents the length of sub-array, with elements smaller than a[i] to its left. Similarly to the right.
The main error in the code, was in the calculation of the sub arrays, L and R.The corrected code can be view at, Corrected Solution.