QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498593#1281. Longest Common SubsequencexinhaowenWA 36ms13572kbC++142.0kb2024-07-30 16:28:032024-07-30 16:28:04

Judging History

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

  • [2024-07-30 16:28:04]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:13572kb
  • [2024-07-30 16:28:03]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
template<typename T>void read(T &x){
	x=0;bool f=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f)x=-x;
}
void write(char x){putchar(x);}
template<typename T>void write(T x){
	if(x<0)putchar('-'),x=-x;
	char stk[24];int cnt=0;
	do stk[++cnt]=x%10+48,x/=10;while(x);
	for(;cnt;)putchar(stk[cnt--]);
}
template<typename T,typename ...Args>void read(T &x,Args &...args){read(x);read(args...);}
template<typename T,typename ...Args>void write(T x,Args ...args){write(x);write(args...);}
template<typename T>T min(T x,T y){return x<y?x:y;}
template<typename T>T max(T x,T y){return x>y?x:y;}
const int maxn=1e6+4;int T,n,m,a[maxn],b[maxn],la[maxn],lb[maxn],ra[maxn],rb[maxn],suma[maxn],sumb[maxn];
int maxx[maxn<<1],ca1,ca3,cb1,cb3,ans;
void update(int x,int val){for(;x<=n+m-1;x+=(x&(-x)))maxx[x]=max(maxx[x],val);}
int query(int x){int ans=0;for(;x;x-=(x&(-x)))ans=max(ans,maxx[x]);return ans;}
signed main(){
	read(T);
	for(;T--;){
		read(n,m);ca1=ca3=cb1=cb3=ans=0;
		for(int i=1;i<=n;++i)read(a[i]),a[i]==1&&(la[++ca1]=i),suma[i]=suma[i-1]+(a[i]==2);
		for(int i=1;i<=m;++i)read(b[i]),b[i]==1&&(lb[++cb1]=i),sumb[i]=sumb[i-1]+(b[i]==2);
		for(int i=n;i;--i)a[i]==3&&(ra[++ca3]=i);
		for(int i=m;i;--i)b[i]==3&&(rb[++cb3]=i);
		int i=min(ca1,cb1),j=0;suma[n+1]=suma[n];sumb[m+1]=sumb[m];ra[0]=n+1;rb[0]=m+1;
		for(;i>=0;--i){
			for(;j<=min(ca3,cb3)&&ra[j]>la[i]&&rb[j]>lb[i];update(m+1+suma[ra[j]]-sumb[rb[j]],j+suma[ra[j]]),++j);
			ans=max(ans,i-suma[la[i]]+query(m+1+suma[la[i]]-sumb[lb[i]]));
		}
		for(int i=1;i<=n+m+1;++i)maxx[i]=0;
		i=min(ca1,cb1),j=0;
		for(;i>=0;--i){
			for(;j<=min(ca3,cb3)&&ra[j]>la[i]&&rb[j]>lb[i];update(n+1+sumb[rb[j]]-suma[ra[j]],j+sumb[rb[j]]),++j);
			ans=max(ans,i-sumb[lb[i]]+query(n+1+sumb[lb[i]]-suma[la[i]]));
		}
		for(int i=1;i<=n+m+1;++i)maxx[i]=0;
		write(ans,'\n');
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 13572kb

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:

3
2
2

result:

ok 3 tokens

Test #2:

score: -100
Wrong Answer
time: 36ms
memory: 11548kb

input:

139889
1 10
2
2 1 2 2 3 1 1 2 3 3
7 1
3 2 3 3 1 1 2
2
6 1
2 1 3 1 1 1
1
8 7
3 1 3 3 2 2 3 1
3 2 2 1 3 3 3
10 3
3 2 1 1 2 2 1 1 1 1
3 1 1
5 2
1 2 1 3 1
1 2
1 4
1
3 3 3 3
7 2
3 1 2 1 2 2 3
3 2
6 2
3 1 1 2 1 3
1 3
1 4
1
3 1 1 3
4 2
2 3 2 3
1 3
1 8
1
1 1 3 1 3 3 3 1
4 1
1 3 3 3
1
10 10
3 1 2 1 2 2 2 2 1...

output:

1
0
1
4
2
2
0
1
2
1
1
1
1
6
1
0
1
2
2
3
4
4
1
1
1
0
2
2
3
4
4
1
1
3
2
1
2
1
3
1
1
1
3
1
0
2
3
2
1
3
1
4
1
2
2
1
3
1
1
2
3
1
2
4
4
2
2
1
1
1
2
4
3
2
1
1
2
3
1
2
2
1
5
2
4
2
1
2
3
2
5
2
1
3
1
3
1
2
1
2
2
4
3
2
0
0
1
3
2
3
2
2
0
0
2
3
1
2
0
4
0
4
1
1
3
1
1
0
1
1
0
1
3
2
2
2
3
3
3
1
2
2
3
2
1
1
3
3
2
3
...

result:

wrong answer 2nd words differ - expected: '1', found: '0'