QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472246#1281. Longest Common Subsequencelichenyu_acWA 122ms18224kbC++141.6kb2024-07-11 15:14:572024-07-11 15:14:57

Judging History

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

  • [2024-07-11 15:14:57]
  • 评测
  • 测评结果:WA
  • 用时:122ms
  • 内存:18224kb
  • [2024-07-11 15:14:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;

int n,m,a[N],b[N],top;
int lA[N],rA[N],sumA[N];
int lB[N],rB[N],sumB[N];

int t1[N],t2[N];
void add1(int x,int k){
	for(int i=x+n+m+1;i<=(n+m)*3+1;i+=i&-i){
		t1[i]=max(t1[i],k);
	}
}

void add2(int x,int k){
	for(int i=x+n+m+1;i;i-=i&-i){
		t2[i]=max(t2[i],k);
	}
}

int ask1(int x){
	int ret=-1e9;
	for(int i=x+n+m+1;i>=1;i-=i&-i){
		ret=max(ret,t1[i]);
	}
	return ret;
}

int ask2(int x){
	int ret=-1e9;
	for(int i=x+n+m+1;i<=(n+m)*3+1;i+=i&-i){
		ret=max(ret,t2[i]);
	}
	return ret;
}

void solve(){
	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&b[i]);

	for(int i=-n-m;i<=(n+m)*2;i++)
		t1[i+n+m+1]=t2[i+n+m+1]=-1e9;

	rA[0]=n+1,rB[0]=m+1;
	for(int i=1;i<=n;i++)lA[i]=n+1,rA[i]=0;
	for(int i=1;i<=m;i++)lB[i]=m+1,rB[i]=0;

	top=0;
	for(int i=1;i<=n;i++)
		if(a[i]==1)lA[++top]=i;
	top=0;
	for(int i=n;i>=1;i--)
		if(a[i]==3)rA[++top]=i;
	for(int i=1;i<=n;i++)
		sumA[i]=sumA[i-1]+(a[i]==2);
	
	top=0;
	for(int i=1;i<=m;i++)
		if(b[i]==1)lB[++top]=i;
	top=0;
	for(int i=m;i>=1;i--)
		if(b[i]==3)rB[++top]=i;
	for(int i=1;i<=m;i++)
		sumB[i]=sumB[i-1]+(b[i]==2);
	
	int ans=0;
	for(int i=min(n,m),j=0;i>=0;i--){
		while(j<=min(n,m)&&lA[i]<rA[j]&&lB[i]<rB[j]){
			add1(sumA[rA[j]-1]-sumB[rB[j]-1],j+sumA[rA[j]-1]);
			add2(sumA[rA[j]-1]-sumB[rB[j]-1],j+sumB[rB[j]-1]);
			j++;
		}
		ans=max({ans,ask1(sumA[rA[i]]-sumB[rB[i]])+i-sumA[lA[i]],ask2(sumA[lA[i]]-sumB[lB[i]])+i-sumB[lB[i]]});
	}
	printf("%d\n",ans);
}

int main(){
	int T;scanf("%d",&T);
	while(T--)solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 18224kb

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: 122ms
memory: 18208kb

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

result:

wrong answer 8th words differ - expected: '1', found: '4'