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);
}
}
Auto comment: topic has been updated by elizabeth_zou_fanboi (previous revision, new revision, compare).
Maintain 4 stack call lmn,rmn,lmx,rmx. I’ll explain this one working with rmn and lmx and you can work the other case. After getting this stack, you can for each i, find the maximum r that the interval is valid by looking at the maximum r <= rmn[i] where lmx[r] <= i. Now you maintain this max pair {r,i} as you sweep the string and only use it when s[i] == 1 and it hasn’t been convered yet. With this approach you can find minimum intervals to cover the whole string
Auto comment: topic has been updated by elizabeth_zou_fanboi (previous revision, new revision, compare).