QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468595#1281. Longest Common Subsequencefree_windyWA 0ms22012kbC++171.8kb2024-07-08 21:46:322024-07-08 21:46:32

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 21:46:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22012kb
  • [2024-07-08 21:46:32]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int s=0,z=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')z=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);
		c=getchar();
	}
	return s*z;
}
const int N = 1e6+5;
int t,n,m,q;
int a[N],b[N],La[N],Ra[N],Lb[N],Rb[N],suma[N],sumb[N],ans,cnt1,dcnt1,dcnt2,cnt2;
int tr[3][N];
int find(int k,int x){
	int mx=-0x3f3f3f3f;
	x+=max(n,m);
	for(;x;x-=(x&-x)){
		mx=max(mx,tr[k][x]);
	}
	return mx;
}
void xg(int k,int x,int z){
	x+=max(n,m);
	for(;x<=max(n,m)*2;x+=x&(-x)) {
		tr[k][x]=max(tr[k][x],z);
	}
	return ;
}
signed main(){
	t=read();
	while(t--){
		n=read(),m=read();
		cnt1=dcnt1=0,cnt2=dcnt2=0;
		for(int i=1;i<=n+1;i++) La[i]=n+1,Ra[i]=0;
		for(int i=1;i<=m+1;i++) Lb[i]=m+1,Ra[i]=0;
		suma[0]=0;
		Ra[0]=n+1;
		for(int i=1;i<=n;i++) tr[1][i]=tr[2][i]=-0x3f3f3f3f;
		for(int i=1;i<=n;i++){
			a[i]=read();
			if(a[i]==1){
				La[++cnt1]=i;
			}
			if(b[i]==2){
				suma[i]=suma[i-1]+1;
			}
			else suma[i]=suma[i-1];
		}
		for(int i=n;i>=1;i--){
			if(a[i]==3){
				Ra[++dcnt1]=i;
			}
		}
		sumb[0]=0;
		Rb[0]=m+1;
		for(int i=1;i<=m;i++){
			b[i]=read();
			if(b[i]==1){
				Lb[++cnt2]=i;
			}
			if(b[i]==2){
				sumb[i]=sumb[i-1]+1;
			}
			else sumb[i]=sumb[i-1];
		}
		for(int i=m;i>=1;i--){
			if(b[i]==3){
				Rb[++dcnt2]=i;
			}
		}
		ans=0;
		for(int i=0,j=min(n,m);j>=0;j--){
			while(i<=min(n,m)&&La[i]<Ra[j]&&Lb[i]<Rb[j]){
				xg(1,suma[La[i]]-sumb[Lb[i]],i-sumb[Lb[i]]);
				xg(2,sumb[Lb[i]]-suma[La[i]],i-sumb[La[i]]);
				i++;
			}
			ans=max(ans,j+max(sumb[Rb[j]-1]+find(1,suma[Ra[j]-1]-sumb[Rb[j]-1]),suma[Ra[j]-1]+find(1,sumb[Rb[j]-1]-suma[Ra[j]-1])));
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 22012kb

input:

3
3 3
1 2 3
1 2 3
3 3
1 1 1
1 1 2
3 3
1 3 2
1 2 3

output:

2
2
3

result:

wrong answer 1st words differ - expected: '3', found: '2'