QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468505#1281. Longest Common SubsequencezWA 115ms19948kbC++141.7kb2024-07-08 21:11:192024-07-08 21:11:20

Judging History

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

  • [2024-07-08 21:11:20]
  • 评测
  • 测评结果:WA
  • 用时:115ms
  • 内存:19948kb
  • [2024-07-08 21:11:19]
  • 提交

answer

/* 值域 1-3,求最长公共上升子序列 

i + j + min( sumb[rb[j]]-sumb[lb[i]] , suma[ra[j]]-suma[la[i]] )

1^ sumb[rb[j]]-sumb[lb[i]] <= suma[ra[j]]-suma[la[i]]

=>  sumb[rb[j]] - suma[ra[j]] <= sumb[lb[i]]-suma[la[i]]

2^ sumb[rb[j]]-sumb[lb[i]] >= suma[ra[j]]-suma[la[i]]

=> suma[ra[j]] - sumb[rb[j]] <= suma[la[i]]-sumb[lb[i]]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,m,LIM;
int a[N],b[N];
int la[N],lb[N],ra[N],rb[N],suma[N],sumb[N];
int k1,k2,k3,k4;
struct BIT{
	int S[N*2];
	void clear(){
		for(int i=1;i<=LIM*2;i++) S[i]=0;
	}
	void update(int x,int v){
		for(x+=LIM;x<=LIM*2;x+=x&-x)
			S[x]=max(S[x],v);
	}
	int ask(int x){
		int ret=0;
		for(x+=LIM;x;x-=x&-x)
			ret=max(ret,S[x]);
		return ret;
	}
}T1,T2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ra[0]=rb[0]=0x3f3f3f3f;
	cin>>T;
	while(T--){
		k1=k2=k3=k4=0;
		int ans=0;
		cin>>n>>m;
		LIM=max(n,m);
		T1.clear();T2.clear();
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==1) la[++k1]=i;
			suma[i]=suma[i-1]+(a[i]==2);
		}
		for(int i=1;i<=m;i++){
			cin>>b[i];
			if(b[i]==1) lb[++k2]=i;
			sumb[i]=sumb[i-1]+(b[i]==2);
		}
		for(int i=n;i>=1;i--) if(a[i]==3) ra[++k3]=i;
		for(int i=m;i>=1;i--) if(b[i]==3) rb[++k4]=i;
		for(int i=0,j=min(k1,k2);j>=0;j--){
			for(;i<=k3&&i<=k4&&la[i]<ra[j]&&lb[i]<rb[j];i++){
				if(i==0) continue;
				T1.update(sumb[rb[i]]-suma[ra[i]],i+sumb[rb[i]]);
				T2.update(suma[ra[i]]-sumb[rb[i]],i+suma[ra[i]]);
			}
			ans=max(ans,max(j-sumb[lb[j]]+T1.ask(sumb[lb[j]]-suma[la[j]]),j-suma[la[j]]+T2.ask(suma[la[j]]-sumb[lb[j]])));
		}
		cout<<max(ans,min(suma[n],sumb[m]))<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 115ms
memory: 17980kb

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

result:

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