If the operation in this question (round 1063 B) is changed as follows: Choose any two integers l and r such that 1≤l≤r≤n. If, for ALL i in range (l,r) , min(pl,pr)<pi<max(pl,pr) holds true then set si to 1 for ALL i in range (l,r)
Is there solution to this variation. I spent whole contest on this variation (misread the question). I want to know whether solution exists in O(n) or not.
My O(n*5) solution that I am not sure is correct:
my code
pll find_largest_range(vll& a,ll st,ll en, ll n){
ll minn = a[st];
ll maxx = a[st];
forl(i,st,en+1){
if(a[i]<minn)
minn = a[i];
if(a[i]>maxx)
maxx = a[i];
}
ll left = st-1;
ll right = en+1;
pll stable = make_pair(-1ll,-1ll);
while(left>=0 && right<n){
while(left>=0 && right<n){
while(left>=0 && a[left]>minn){
maxx = max(maxx,a[left]);
left--;
}
if(left<0 || a[left]>minn)
return stable;
minn = a[left];
ll next_left = left;
ll ind_left = left-1;
while(ind_left>=0 && a[ind_left+1]<max(maxx,a[right])){//bug
if(a[ind_left]<=minn){
next_left = ind_left;
minn = a[next_left];
}
ind_left--;
}
left = next_left;
while(right<n && a[right]<maxx){
minn = min(minn,a[right]);
right++;
}
if(right>=n || a[right]<maxx)
return stable;
maxx = a[right];
ll next_right = right;
ll ind_right = right+1;
while(ind_right<n && a[ind_right-1]>min(a[left],minn)){
if(a[ind_right]>=maxx){
next_right = ind_right;
maxx = a[next_right];
}
ind_right++;
}
right = next_right;
if(a[left]<=minn){
ll old_left = left;
ll old_right = right;
ll old_minn = minn;
ll old_maxx = maxx;
ll next_left = left;
ll ind_left = left-1;
while(ind_left>=0 && a[ind_left+1]<max(maxx,a[right])){//bug
if(a[ind_left]<minn){
next_left = ind_left;
minn = a[next_left];
}
ind_left--;
}
left = next_left;
if(right-left > stable.second-stable.first)
stable = make_pair(left,right);
left = old_left;
right = old_right;
minn = old_minn;
maxx = old_maxx;
ll next_right = right;
ll ind_right = right+1;
while(ind_right<n && a[ind_right-1]>min(a[left],minn)){
if(a[ind_right]>maxx){
next_right = ind_right;
maxx = a[next_right];
}
ind_right++;
}
right = next_right;
if(right-left > stable.second-stable.first)
stable = make_pair(left,right);
left = old_left;
right = old_right;
minn = old_minn;
maxx = old_maxx;
minn = a[left];
maxx = a[right];
left--;
right++;
break;
}
}
}
return stable;
}
void solve(int tt)
{
ll n;
cin>>n;
vll a(n);
string s;
forl(i,0,n)cin>>a[i];
cin>>s;
vll aa = a;
forl(i,0,n)aa[i] = -a[i];
debug(n,a,s);
vector<pll> ranges;
forl(i,0,n){
ll j = i;
while(j<n && s[j]==s[i]){
j++;
}
j--;
if(s[j]=='0')
continue;
if(s[j]=='1'){
pll r1 = find_largest_range(a,s,i,j,n);
pll r2 = find_largest_range(aa,s,i,j,n);
if(r1.second - r1.first > r2.second - r2.first)
ranges.push_back(r1);
else{
if(r2.first < r2.second)
ranges.push_back(r2);
else{
print(-1);
return;
}
}
}
ll sz = ranges.size();
if(sz>5){
print(-1);
return;
}
i = ranges[sz-1].second-1;
}
print(ranges.size());
for(auto p: ranges){
print(p.first+1,p.second+1);
}
}
