PROBLEM LINK : Author : Vibhor Gupta Tester : Vibhor Gupta Editorialist : Vibhor Gupta DIFFICULTY : Hard PREREQUISITES : stock span algorithm, Subarray 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 subarray. 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()] = is.top(); s.pop();} a[i] = (s.empty())? i : is.top(); s.push(i);} while(!s.empty()){ b[s.top()] = ns.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 subarray, 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.
This question is marked "community wiki".
asked 30 Mar '16, 22:19

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. answered 08 Apr '16, 17:10
