QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468609#1281. Longest Common SubsequencedczissbTL 3ms17976kbC++141.5kb2024-07-08 21:49:422024-07-08 21:49:43

Judging History

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

  • [2024-07-08 21:49:43]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:17976kb
  • [2024-07-08 21:49:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int a[1000001],b[1000001],ans,t,n,m,sa[1000001],la[1000001],ra[1000001],lb[1000001],rb[1000001],sb[1000001];
int lowbit(int x){return x&(-x);}
struct dcz{
	int c[2000001];
	void clear(){for(int i=1;i<=2*max(n,m);i++) c[i]=INT_MIN;}
	void update(int i,int x){ i+=max(n,m); while(i<=n+max(n,m)) c[i]=max(c[i],x),i+=lowbit(i); }
	int get(int i){int val=0xcfcfcfcf;i+=max(n,m);while(i) val=max(c[i],val),i-=lowbit(i); return val;}
}tr1,tr2;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		int tot=0;
		la[0]=lb[0]=0;
		ra[0]=n+1,rb[0]=m+1;
		tr1.clear(),tr2.clear();
		ans=0;
		for(int i=1;i<=n;i++) la[i]=n+1,ra[i]=0;
		for(int i=1;i<=m;i++) lb[i]=n+1,rb[i]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sa[i]=sa[i-1]+(a[i]==2);
			if(a[i]==1) la[++tot]=i;
		}
		tot=0;
		for(int i=n;i>=1;i--){
			if(a[i]==3) ra[++tot]=i;
		}
		tot=0;
		for(int i=1;i<=m;i++){
			cin>>b[i];
			sb[i]=sb[i-1]+(b[i]==2);
			if(b[i]==1) lb[++tot]=i;
		}
		tot=0;
		for(int i=m;i>=1;i--){
			if(b[i]==3) rb[++tot]=i;
		}
		for(int i=0,j=min(n,m);j>=0;j--){
			while(ra[j]>la[i]&&rb[j]>lb[i]&&i<=min(n,m)){
				tr1.update(sa[la[i]]-sb[lb[i]],i-sb[lb[i]]);
				tr2.update(sb[lb[i]]-sa[la[i]],i-sa[la[i]]);
				i++;
			}
			ans=max({ans,j+sb[rb[j]-1]+tr1.get(sa[ra[j]-1]-sb[rb[j]-1]),j+sa[ra[j]-1]+tr2.get(sb[rb[j]-1]-sa[ra[j]-1])});
		}
		cout<<ans<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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:


result: