×

# CHKAR - Editorial

 0 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. This question is marked "community wiki". asked 30 Mar '16, 22:19 11●1 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,343
×847
×17
×6
×1

question asked: 30 Mar '16, 22:19

question was seen: 851 times

last updated: 08 Apr '16, 17:14