In the speedbreaker question, why do we need to do: mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);. I (mostly) get everything besides that. Thanks in advance!
Full submission by Zqr123456 on Div 2 contest:
include<bits/stdc++.h>
using namespace std; int T,n,a[200005],mn[200005],mx[200005],l,r; void solve(){ cin>>n; for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0; for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i); for(int i=1;i<=n;i++){ mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]); if(mx[i]-mn[i]>=i){cout<<"0\n";return;} } l=1,r=n; for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1); cout<<r-l+1<<'\n'; } signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>T; while(T--)solve(); return 0; }
Also, I get why the first condition is necessary for there to be a solutions and I get why the second part of the code finds that good interval, but I'm having a little trouble piecing together the sufficiency of the two to guarantee the right answer. Perhaps this is also why I font understand why you have to do the operations on the mins and maxes too.
Auto comment: topic has been updated by Negationist (previous revision, new revision, compare).
First of all, learn how to write a blog properly. Click
What is this absolute mess of a code that you just posted. No indentations or newlines. Writing the code in the way same as other part of the text. Also no pop-down menu to where code is written. A stupidly big bold header as if it was the main heading/point of the blog. Code readability $$$-\infty.$$$
Suggestion:
Instead of writing the code like this. Write is as: