RT

思路大致就是把问题转化成矩阵 然后从$xmin$和$ymax$的点往左上和右下缩范围 缩到边界就说明有解

本地跑大样例5过不了 看返回值应该是segmentation fault

抱着试一试的心态交了一法结果过了

求问这是什么原因

submission

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int c,n,m,q,cnt=1;
bool dp[2005][2005];
int ans[65];
int tmpx[maxn],tmpy[maxn];
int xpre1[maxn],xpre2[maxn];//x前缀最大值/最小值下标 
int ypre1[maxn],ypre2[maxn];//y前缀最大值/最小值下标 
int xaft1[maxn],xaft2[maxn];//x后缀最大值/最小值下标 
int yaft1[maxn],yaft2[maxn];//y后缀最大值/最小值下标 
bool check(int x[],int y[],int nx,int ny){
	if(x[1]<=y[1]||x[nx]<=y[ny]) return false;
	memset(dp,0,sizeof(dp));
	dp[1][1]=true;
	for(int i=1;i<=nx;i++){
		for(int j=1;j<=ny;j++){
			if(dp[i][j]) continue;
			if(x[i]>y[j]){
				if(dp[i-1][j]||dp[i][j-1]||dp[i-1][j-1]){
					dp[i][j]=true;
				}
			}
		}
	}
	return dp[nx][ny];
}
bool check1(int l,int r){
	if(l==1||r==1) return true;
	int xmx=xpre1[l-1],xmn=xpre2[l-1];
	int ymx=ypre1[r-1],ymn=ypre2[r-1];
	if(tmpx[xmx]<tmpy[ymx]) return check1(l,ymx);
	if(tmpx[xmn]<tmpy[ymn]) return check1(xmn,r);
	return false;
}
bool check2(int l,int r,int n,int m){
	if(l==n||r==m) return true;
	int xmx=xaft1[l+1],xmn=xaft2[l+1];
	int ymx=yaft1[r+1],ymn=yaft2[r+1];
	if(tmpx[xmx]<tmpy[ymx]) return check2(l,ymx,n,m);
	if(tmpx[xmn]<tmpy[ymn]) return check2(xmn,r,n,m);
	return false;
}
bool solve(int x[],int y[],int nx,int ny){
	if(x[1]>=y[1]) return false;
	for(int i=1;i<=nx;i++) tmpx[i]=x[i];
	for(int i=1;i<=ny;i++) tmpy[i]=y[i];
	xpre1[1]=xpre2[1]=1;ypre1[1]=ypre2[1]=1;
	xaft1[nx]=xaft2[nx]=nx;yaft1[ny]=yaft2[ny]=ny;
	for(int i=2;i<=nx;i++){
		if(x[xpre1[i-1]]<x[i]) xpre1[i]=i;
		else xpre1[i]=xpre1[i-1];
		if(x[xpre2[i-1]]>x[i]) xpre2[i]=i;
		else xpre2[i]=xpre2[i-1];
	}
	for(int i=2;i<=ny;i++){
		if(y[ypre1[i-1]]<y[i]) ypre1[i]=i;
		else ypre1[i]=ypre1[i-1];
		if(y[ypre2[i-1]]>y[i]) ypre2[i]=i;
		else ypre2[i]=ypre2[i-1];
	}
	for(int i=nx-1;i>=1;i--){
		if(x[xaft1[i+1]]<x[i]) xaft1[i]=i;
		else xaft1[i]=xaft1[i+1];
		if(x[xaft2[i+1]]>x[i]) xaft2[i]=i;
		else xaft2[i]=xaft2[i+1];
	}
	for(int i=ny-1;i>=1;i--){
		if(y[yaft1[i+1]]<y[i]) yaft1[i]=i;
		else yaft1[i]=yaft1[i+1];
		if(y[yaft2[i+1]]>y[i]) yaft2[i]=i;
		else yaft2[i]=yaft2[i+1];
	}
	int xmx=xpre1[nx],xmn=xpre2[nx],ymx=ypre1[ny],ymn=ypre2[ny];
	if(x[xmn]>=y[ymn]||x[xmx]>=y[ymx]) return false;
	return check1(xmn,ymx)&&check2(xmn,ymx,nx,ny);
}
int x[maxn],y[maxn],tx[maxn],ty[maxn];
void sol1(){
	if(check(x,y,n,m)||check(y,x,m,n)) ans[1]=1;
	while(q--){
		cnt++;
		for(int i=1;i<=n;i++) tx[i]=x[i];
		for(int i=1;i<=m;i++) ty[i]=y[i];
		int kx,ky,p,v;
		cin>>kx>>ky;
		for(int i=1;i<=kx;i++){
			cin>>p>>v;tx[p]=v;
		}
		for(int i=1;i<=ky;i++){
			cin>>p>>v;ty[p]=v;
		}
		if(check(tx,ty,n,m)||check(ty,tx,m,n)) ans[cnt]=1;
	}
	for(int i=1;i<=cnt;i++) cout<<ans[i];
	return ;
}
void sol2(){
	if(solve(x,y,n,m)||solve(y,x,m,n)) ans[1]=1;
	while(q--){
		cnt++;
		for(int i=1;i<=n;i++) tx[i]=x[i];
		for(int i=1;i<=m;i++) ty[i]=y[i];
		int kx,ky,p,v;
		cin>>kx>>ky;
		for(int i=1;i<=kx;i++){
			cin>>p>>v;tx[p]=v;
		}
		for(int i=1;i<=ky;i++){
			cin>>p>>v;ty[p]=v;
		}
		if(solve(tx,ty,n,m)||solve(ty,tx,m,n)) ans[cnt]=1;
	}
	for(int i=1;i<=cnt;i++) cout<<ans[i];
	return ;
}
int main(){
	//freopen("expand5.in","r",stdin);
	cin>>c>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>x[i];
	for(int i=1;i<=m;i++) cin>>y[i];
	//if(c<=7) sol1();
	//else sol2();
	sol2();
	return 0;
}

sol1是打的O(Tmn)的dp 可以忽略