QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#498466#1281. Longest Common Subsequencec20150005WA 47ms16088kbC++141.5kb2024-07-30 15:11:462024-07-30 15:11:48

Judging History

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

  • [2024-07-30 15:11:48]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:16088kb
  • [2024-07-30 15:11:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=1e6+6;
int n,m;
int a[N],b[N];
int suma[N],sumb[N];
int la[N],lb[N];
int ra[N],rb[N];
int c[N<<1];
void upd(int x,int y){for(;x<=n+m+1;x+=(x&-x))c[x]=max(c[x],y);}
int ask(int x,int r=0){for(;x;x-=(x&-x))r=max(r,c[x]);return r;}
void solve(){
	n=rd(),m=rd();
	int tx1=0,ty1=0,tx2=0,ty2=0;
	for(int i=1;i<=n;i++){
		a[i]=rd();
		if(a[i]==1)la[++tx1]=i;
		suma[i]=suma[i-1];
		if(a[i]==2)suma[i]++;
	}suma[n+1]=suma[n];
	for(int i=n;i;i--)if(a[i]==3)ra[++ty1]=i;
	for(int i=1;i<=m;i++){
		b[i]=rd();
		if(b[i]==1)lb[++tx2]=i;
		sumb[i]=sumb[i-1];
		if(b[i]==2)sumb[i]++;
	}sumb[m+1]=sumb[m];
	for(int i=m;i;i--)if(b[i]==3)rb[++ty2]=i;
	ra[0]=n+1,rb[0]=m+1;
	int i=min(tx1,tx2),j=0;
	for(int i=1;i<=n+m-1;i++)c[i]=0; 
	int ans=0;
	for(;i>=0;i--){
		while(j<=min(ty1,ty2)&&ra[j]>la[i]&&rb[j]>lb[i])
		upd(suma[ra[j]]-sumb[rb[j]]+m+1,j+suma[ra[j]]),j++;
		ans=max(ans,ask(suma[la[i]]-sumb[lb[i]]+m+1)+i-suma[la[i]]);
	}for(int i=1;i<=n+m+1;i++)c[i]=0;i=min(tx1,tx2),j=0;
	for(;i>=0;i--){
		while(j<=min(ty1,ty2)&&ra[j]>la[i]&&rb[j]>lb[i])
		upd(n+1-suma[ra[j]]+sumb[rb[j]],j+sumb[rb[j]]),j++;
		ans=max(ans,ask(n+1-suma[la[i]]+sumb[lb[i]])+i-sumb[lb[i]]);
	}printf("%d\n",ans);
}
int main(){
	int t=rd();while(t--)solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16088kb

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: 47ms
memory: 14072kb

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
1
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
1
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
1
1
3
2
3
2
2
0
0
2
3
1
2
0
4
1
4
1
1
3
1
1
0
1
1
1
1
3
2
2
2
3
3
3
1
2
2
3
2
2
1
3
3
2
3
...

result:

wrong answer 145th words differ - expected: '1', found: '2'