CHKAR - Editorial

PROBLEM LINK :

contest

practice

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 :

#include

#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.

3
3 3 1
for the above input your code in giving output 23
but it should be 28.
pls explain if I am wrong.

//