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