Variation of problem B in div2 round 1063
Difference between en5 and en6, changed 1720 character(s)
If the operation in this [question](https://codeforces.me/contest/2163/problem/B) (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:↵
↵
<spoiler summary="my code">↵
↵
~~~~~↵
↵
pll find_largest_range(vll& a,string& s,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]<maxx){(maxx,a[right])){//bug↵
                minn = min(minn,a[ind_left+1]);↵
if(a[ind_left]<=minn){↵
                    if(a[ind_left]<minn)↵
                    next_left = ind_left;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;↵
            right++;↵
            while(right<n && a[ind_right-1]>minn){↵
                maxx = max(maxx,a[ind_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 = indnext_right;↵
↵
                if(a[left]<minn){↵
                stable = make_pair(left,right)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);↵
    }↵
} ↵
~~~~~↵
↵
↵
</spoiler>↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English elizabeth_zou_fanboi 2025-11-11 12:11:21 1720
en5 English elizabeth_zou_fanboi 2025-11-10 22:19:30 8 (published)
en4 English elizabeth_zou_fanboi 2025-11-10 22:17:21 5 Tiny change: '+1]<maxx){//bug\n ' -> '+1]<maxx){\n '
en3 English elizabeth_zou_fanboi 2025-11-10 22:16:31 39
en2 English elizabeth_zou_fanboi 2025-11-10 22:14:52 2863 Tiny change: 's correct:' -> 's correct:\n<spoiler summary="my code">\n...\n\nhello \n</spoiler>'
en1 English elizabeth_zou_fanboi 2025-11-10 22:01:00 911 Initial revision (saved to drafts)