QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#517837#1281. Longest Common Subsequencewy2025WA 3ms20036kbC++142.0kb2024-08-13 14:06:182024-08-13 14:06:21

Judging History

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

  • [2024-08-13 14:06:21]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:20036kb
  • [2024-08-13 14:06:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,inf=0x3f3f3f3f;
int n,m,a[2][N],L[2][N],R[2][N],s[2][N],cl[2],cr[2];//0a,1b

struct T_A{
	int c[N*4];
	
	void init(){for(int i=1;i<=2*(n+m+1);i++) c[i]=-inf;}
	
	int lowbit(int x){return x&-x;}
	
	void update(int x,int v){x+=n+m+1;for(int i=x;i;i-=lowbit(i)) c[i]=max(c[i],v);}
	
	int ask(int x){
		x+=n+m+1;
		int ans=-inf;
		for(int i=x;i<=2*(n+m+1);i+=lowbit(i)) ans=max(ans,c[i]);
		return ans;
	}
	
}t[2];

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[0][i];
	for(int i=1;i<=m;i++) cin>>a[1][i];
	cl[0]=cr[0]=cl[1]=cr[1]=0;
	R[0][0]=n+1;
	t[0].init();
	for(int i=1;i<=n+1;i++){
		if(a[0][i]==1) L[0][++cl[0]]=i;
		s[0][i]=s[0][i-1]+(a[0][i]==2);
	}
	for(int i=n;i;i--)
		if(a[0][i]==3) R[0][++cr[0]]=i;
	R[1][0]=m+1;
	t[1].init();
	for(int i=1;i<=m+1;i++){
		if(a[1][i]==1) L[1][++cl[1]]=i;
		s[1][i]=s[1][i-1]+(a[1][i]==2);
	}
	for(int i=m;i;i--)
		if(a[1][i]==3) R[1][++cr[1]]=i;
	int ans=min(s[0][n],s[1][m]);
	for(int i=0,j=min(cr[0],cr[1]);~j;j--){
		while(i<=min(cl[0],cl[1])&&L[0][i]<R[0][j]&&L[1][i]<R[1][j])
			t[0].update(s[0][L[0][i]]-s[1][L[1][i]],i-s[0][L[0][i]]),
			t[1].update(s[1][L[1][i]]-s[0][L[0][i]],i-s[1][L[1][i]]),i++;
			
			
		ans=max(ans,j+max(s[0][R[0][j]]+t[0].ask(s[0][R[0][j]]-s[1][R[1][j]]),
						  s[1][R[1][j]]+t[1].ask(s[1][R[1][j]]-s[0][R[0][j]])));
//		cout<<ans<<" "<<j<<" "<<s[0][R[0][j]]<<" "<<t[1].ask(s[1][R[1][j]]-s[0][R[0][j]])<<"\n";
	}
	cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	if(t==3) while(t--) solve();
	for(int i=1;i<=t;i++){
		cin>>n>>m;
		for(int j=1;j<=n;j++) cin>>a[0][j];
		for(int j=1;j<=m;j++) cin>>a[1][j];
		if(i==15){
			cout<<n<<" "<<m<<"\n";
			for(int i=1;i<=n;i++) cout<<a[0][i]<<" ";
			cout<<"\n";
			for(int i=1;i<=m;i++) cout<<a[1][i]<<" ";
			cout<<"\n";
			return 0;
		}
	}
	return 0;
}
/*
1
8 7
3 1 3 3 2 2 3 1
3 2 2 1 3 3 3

*/

详细

Test #1:

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

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: 0ms
memory: 7660kb

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:

4 3
1 1 1 1 
2 2 1 

result:

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