Speedbreaker - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

In the speedbreaker question, why do we need to do: c++ 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:

“Code"

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

Rev.	By	When	Δ	Comment
en9	Negationist	2024-09-28 21:06:53	857
en8	Negationist	2024-09-28 21:05:33	148
en7	Negationist	2024-09-28 21:04:57	5
en6	Negationist	2024-09-28 21:01:38	16
en5	Negationist	2024-09-28 21:00:18	27
en4	Negationist	2024-09-28 19:53:20	13
en3	Negationist	2024-09-28 19:51:35	40
en2	Negationist	2024-09-28 10:39:09	30	Tiny change: 'submission: \n#inclu' -> 'submission by Zqr123456 on Div 2 contest: \n#inclu'
en1	Negationist	2024-09-28 10:38:14	1139	Initial revision (published)

Rev.

Lang.

When

Comment

en9