58个点有4个WA了...

对拍了1000+组数据没出锅。

#include<bits/stdc++.h>
using namespace std;
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)
#define N 400005
int val,n,s[N],mx[2][N<<2],gg,m,a[N],v[N],mx1,mx2,c1,c2;
int query(int typ,int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return mx[typ][k];
	if(y<l||r<x)return -1;
	return max(query(typ,ls,l,mid,x,y),query(typ,rs,mid+1,r,x,y));
}
void modify(int typ,int k,int l,int r,int x,int y){
	if(l==r){mx[typ][k]=y;return ;}
	if(x<=mid)modify(typ,ls,l,mid,x,y);
	else modify(typ,rs,mid+1,r,x,y);
	mx[typ][k]=max(mx[typ][ls],mx[typ][rs]);
}
int check(int now){
	val=c1+(a[now]>mx1)-c2+gg;
	if(val>=0&&query(val&1,1,1,m,mx2,m)>=val)return 1;
	val=c2-c1-(a[now]>mx1)+gg;
	if(val>=0&&query(val&1,1,1,m,max(mx1,a[now]),m)>=val)return 1;
	return 0;
}int i,Mx;
int main(){
//	freopen("a.txt","r",stdin);
//	freopen("a.out","w",stdout);
	cin>>n;m=n+1;for(i=1;i<=n;++i)cin>>a[i];
	for(i=1;i<=n;++i){
		if(a[i]>Mx)Mx=a[i],v[i]=2,++gg;
		else v[i]=1;
	}
	memset(mx[1],-1,sizeof(mx[1]));
	for(i=n;i;--i){
		if(v[i]==2)modify(0,1,1,m,a[i],query(0,1,1,m,a[i]+1,m)+2),modify(1,1,1,m,a[i],query(1,1,1,m,a[i]+1,m)+2);
		else modify(0,1,1,m,a[i],query(1,1,1,m,a[i]+1,m)+1),modify(1,1,1,m,a[i],query(0,1,1,m,a[i]+1,m)+1);
	}
	for(i=1;i<=n;++i){
		modify(0,1,1,m,a[i],0);modify(1,1,1,m,a[i],-1);gg-=(v[i]==2);
		if(check(i))c1+=(mx1<a[i]),mx1=max(mx1,a[i]);
		else s[i]=1,c2+=(mx2<a[i]),mx2=max(mx2,a[i]);
	}
	if(c1==c2)for(i=1;i<=n;++i)cout<<s[i];else cout<<-1;
}